Line data Source code
1 : #include "./fd_bn254.h"
2 :
3 : /* Extension Fields Fp2, Fp6, Fp12.
4 :
5 : Mostly based on https://eprint.iacr.org/2010/354, Appendix A.
6 : See also, as a reference implementation:
7 : https://github.com/Consensys/gnark-crypto/tree/v0.12.1/ecc/bn254/internal/fptower
8 :
9 : Elements are in Montgomery form, unless otherwise specified. */
10 :
11 : /* Constants */
12 :
13 : /* const B=3/(i+9), in twist curve equation y^2 = x^3 + b'. Montgomery.
14 : 0x2514c6324384a86d26b7edf049755260020b1b273633535d3bf938e377b802a8
15 : 0x0141b9ce4a688d4dd749d0dd22ac00aa65f0b37d93ce0d3e38e7ecccd1dcff67 */
16 : const fd_bn254_fp2_t fd_bn254_const_twist_b_mont[1] = {{{
17 : {{ 0x3bf938e377b802a8, 0x020b1b273633535d, 0x26b7edf049755260, 0x2514c6324384a86d, }},
18 : {{ 0x38e7ecccd1dcff67, 0x65f0b37d93ce0d3e, 0xd749d0dd22ac00aa, 0x0141b9ce4a688d4d, }},
19 : }}};
20 :
21 : /* fd_bn254_const_frob_gamma1_mont for frob. Montgomery.
22 : gamma_1,1 = 0x02f34d751a1f3a7c11bded5ef08a2087ca6b1d7387afb78aaf9ba69633144907
23 : 0x10a75716b3899551dc2ff3a253dfc926d00f02a4565de15ba222ae234c492d72
24 : gamma_1,2 = 0x1956bcd8118214ec7a007127242e0991347f91c8a9aa6454b5773b104563ab30
25 : 0x26694fbb4e82ebc3b6e713cdfae0ca3aaa1c7b6d89f891416e849f1ea0aa4757
26 : gamma_1,3 = 0x253570bea500f8dd31a9d1b6f9645366bb30f162e133bacbe4bbdd0c2936b629
27 : 0x2c87200285defecc6d16bd27bb7edc6b07affd117826d1dba1d77ce45ffe77c7
28 : gamma_1,4 = 0x15df9cddbb9fd3ec9c941f314b3e2399a5bb2bd3273411fb7361d77f843abe92
29 : 0x24830a9d3171f0fd37bc870a0c7dd2b962cb29a5a4445b605dddfd154bd8c949
30 : gamma_1,5 = 0x12aabced0ab0884132bee66b83c459e8e240342127694b0bc970692f41690fe7
31 : 0x2f21ebb535d2925ad3b0a40b8a4910f505193418ab2fcc570d485d2340aebfa9 */
32 : const fd_bn254_fp2_t fd_bn254_const_frob_gamma1_mont[5] = {
33 : {{
34 : {{ 0xaf9ba69633144907, 0xca6b1d7387afb78a, 0x11bded5ef08a2087, 0x02f34d751a1f3a7c, }},
35 : {{ 0xa222ae234c492d72, 0xd00f02a4565de15b, 0xdc2ff3a253dfc926, 0x10a75716b3899551, }},
36 : }},
37 : {{
38 : {{ 0xb5773b104563ab30, 0x347f91c8a9aa6454, 0x7a007127242e0991, 0x1956bcd8118214ec, }},
39 : {{ 0x6e849f1ea0aa4757, 0xaa1c7b6d89f89141, 0xb6e713cdfae0ca3a, 0x26694fbb4e82ebc3, }},
40 : }},
41 : {{
42 : {{ 0xe4bbdd0c2936b629, 0xbb30f162e133bacb, 0x31a9d1b6f9645366, 0x253570bea500f8dd, }},
43 : {{ 0xa1d77ce45ffe77c7, 0x07affd117826d1db, 0x6d16bd27bb7edc6b, 0x2c87200285defecc, }},
44 : }},
45 : {{
46 : {{ 0x7361d77f843abe92, 0xa5bb2bd3273411fb, 0x9c941f314b3e2399, 0x15df9cddbb9fd3ec, }},
47 : {{ 0x5dddfd154bd8c949, 0x62cb29a5a4445b60, 0x37bc870a0c7dd2b9, 0x24830a9d3171f0fd, }},
48 : }},
49 : {{
50 : {{ 0xc970692f41690fe7, 0xe240342127694b0b, 0x32bee66b83c459e8, 0x12aabced0ab08841, }},
51 : {{ 0x0d485d2340aebfa9, 0x05193418ab2fcc57, 0xd3b0a40b8a4910f5, 0x2f21ebb535d2925a, }},
52 : }},
53 : };
54 :
55 : /* fd_bn254_const_frob_gamma2_mont for frob^2. Montgomery.
56 : gamma_2,1 = 0x04290f65bad856e60e201271ad0d4418f0c5d61468b39769ca8d800500fa1bf2
57 : gamma_2,2 = 0x2682e617020217e06001b4b8b615564a7dce557cdb5e56b93350c88e13e80b9c
58 : gamma_2,3 = 0x2259d6b14729c0fa51e1a247090812318d087f6872aabf4f68c3488912edefaa
59 : gamma_2,4 = 0x2c3b3f0d26594943aa303344d4741444a6bb947cffbe332371930c11d782e155
60 : gamma_2,5 = 0x09e1685bdf2f8849584e90fdcb6c021319b315148d1373d408cfc388c494f1ab */
61 : const fd_bn254_fp_t fd_bn254_const_frob_gamma2_mont[5] = {
62 : {{ 0xca8d800500fa1bf2, 0xf0c5d61468b39769, 0x0e201271ad0d4418, 0x04290f65bad856e6, }}, /* gamma_2,1 */
63 : {{ 0x3350c88e13e80b9c, 0x7dce557cdb5e56b9, 0x6001b4b8b615564a, 0x2682e617020217e0, }}, /* gamma_2,2 */
64 : {{ 0x68c3488912edefaa, 0x8d087f6872aabf4f, 0x51e1a24709081231, 0x2259d6b14729c0fa, }}, /* gamma_2,3 */
65 : {{ 0x71930c11d782e155, 0xa6bb947cffbe3323, 0xaa303344d4741444, 0x2c3b3f0d26594943, }}, /* gamma_2,4 */
66 : {{ 0x08cfc388c494f1ab, 0x19b315148d1373d4, 0x584e90fdcb6c0213, 0x09e1685bdf2f8849, }}, /* gamma_2,5 */
67 : };
68 :
69 : /* Fp2 */
70 :
71 : static inline fd_bn254_fp2_t *
72 : fd_bn254_fp2_frombytes_nm( fd_bn254_fp2_t * r,
73 : uchar const buf[64],
74 : int big_endian,
75 : int * is_inf,
76 185754 : int * is_neg ) {
77 : /* validate fp2.el[0] without flags */
78 185754 : if( FD_UNLIKELY( !fd_bn254_fp_frombytes_nm( &r->el[0], &buf[ big_endian ? 32 : 0 ], big_endian, NULL, NULL ) ) ) {
79 0 : return NULL;
80 0 : }
81 : /* validate fp2.el[1] with flags */
82 185754 : if( FD_UNLIKELY( !fd_bn254_fp_frombytes_nm( &r->el[1], &buf[ big_endian ? 0 : 32 ], big_endian, is_inf, is_neg ) ) ) {
83 0 : return NULL;
84 0 : }
85 185754 : return r;
86 185754 : }
87 :
88 : static inline uchar *
89 : fd_bn254_fp2_tobytes_nm( uchar buf[64],
90 : fd_bn254_fp2_t * const a,
91 96951 : int big_endian ) {
92 96951 : fd_bn254_fp_tobytes_nm( &buf[ 0], &a->el[ big_endian ? 1 : 0 ], big_endian );
93 96951 : fd_bn254_fp_tobytes_nm( &buf[32], &a->el[ big_endian ? 0 : 1 ], big_endian );
94 96951 : return buf;
95 96951 : }
96 :
97 : /* fd_bn254_fp2_is_neg_nm checks whether x < 0 in Fp2.
98 : Note: x is NON Montgomery.
99 : Returns 1 if x < 0, 0 otherwise. */
100 : static inline int
101 33186 : fd_bn254_fp2_is_neg_nm( fd_bn254_fp2_t * x ) {
102 33186 : if( FD_UNLIKELY( fd_bn254_fp_is_zero( &x->el[1] ) ) ) {
103 0 : return fd_bn254_fp_is_neg_nm( &x->el[0] );
104 0 : }
105 33186 : return fd_bn254_fp_is_neg_nm( &x->el[1] );
106 33186 : }
107 :
108 : /* fd_bn254_fp2_is_minus_one checks whether a == -1 in Fp2.
109 : Returns 1 if a==-1, 0 otherwise. */
110 : static inline int
111 6186 : fd_bn254_fp2_is_minus_one( fd_bn254_fp2_t const * a ) {
112 6186 : return fd_uint256_eq( &a->el[0], fd_bn254_const_p_minus_one_mont )
113 6186 : && fd_uint256_eq( &a->el[1], fd_bn254_const_zero );
114 6186 : }
115 :
116 : /* fd_bn254_fp2_eq checks whether a == b in Fp2.
117 : Returns 1 if a == b, 0 otherwise. */
118 : static inline int
119 : fd_bn254_fp2_eq( fd_bn254_fp2_t const * a,
120 155196 : fd_bn254_fp2_t const * b ) {
121 155196 : return fd_bn254_fp_eq( &a->el[0], &b->el[0] )
122 155196 : && fd_bn254_fp_eq( &a->el[1], &b->el[1] );
123 155196 : }
124 :
125 : /* fd_bn254_fp2_set sets r = a. */
126 : static inline fd_bn254_fp2_t *
127 : fd_bn254_fp2_set( fd_bn254_fp2_t * r,
128 1722357 : fd_bn254_fp2_t const * a ) {
129 1722357 : fd_bn254_fp_set( &r->el[0], &a->el[0] );
130 1722357 : fd_bn254_fp_set( &r->el[1], &a->el[1] );
131 1722357 : return r;
132 1722357 : }
133 :
134 : /* fd_bn254_fp2_from_mont sets r = a, coverting into NON Mongomery form. */
135 : static inline fd_bn254_fp2_t *
136 : fd_bn254_fp2_from_mont( fd_bn254_fp2_t * r,
137 63765 : fd_bn254_fp2_t const * a ) {
138 63765 : fd_bn254_fp_from_mont( &r->el[0], &a->el[0] );
139 63765 : fd_bn254_fp_from_mont( &r->el[1], &a->el[1] );
140 63765 : return r;
141 63765 : }
142 :
143 : /* fd_bn254_fp2_to_mont sets r = a, coverting into Mongomery form. */
144 : static inline fd_bn254_fp2_t *
145 : fd_bn254_fp2_to_mont( fd_bn254_fp2_t * r,
146 125553 : fd_bn254_fp2_t const * a ) {
147 125553 : fd_bn254_fp_to_mont( &r->el[0], &a->el[0] );
148 125553 : fd_bn254_fp_to_mont( &r->el[1], &a->el[1] );
149 125553 : return r;
150 125553 : }
151 :
152 : /* fd_bn254_fp2_neg_nm sets r = -x in Fp2.
153 : Note: x is NON Montgomery. */
154 : static inline fd_bn254_fp2_t *
155 : fd_bn254_fp2_neg_nm( fd_bn254_fp2_t * r,
156 3060 : fd_bn254_fp2_t const * x ) {
157 3060 : fd_bn254_fp_neg_nm( &r->el[0], &x->el[0] );
158 3060 : fd_bn254_fp_neg_nm( &r->el[1], &x->el[1] );
159 3060 : return r;
160 3060 : }
161 :
162 : /* fd_bn254_fp2_neg sets r = -a in Fp2. */
163 : static inline fd_bn254_fp2_t *
164 : fd_bn254_fp2_neg( fd_bn254_fp2_t * r,
165 102132 : fd_bn254_fp2_t const * a ) {
166 102132 : fd_bn254_fp_neg( &r->el[0], &a->el[0] );
167 102132 : fd_bn254_fp_neg( &r->el[1], &a->el[1] );
168 102132 : return r;
169 102132 : }
170 :
171 : /* fd_bn254_fp2_neg sets r = a/2 in Fp2. */
172 : static inline fd_bn254_fp2_t *
173 : fd_bn254_fp2_halve( fd_bn254_fp2_t * r,
174 112128 : fd_bn254_fp2_t const * a ) {
175 112128 : fd_bn254_fp_halve( &r->el[0], &a->el[0] );
176 112128 : fd_bn254_fp_halve( &r->el[1], &a->el[1] );
177 112128 : return r;
178 112128 : }
179 :
180 : /* fd_bn254_fp2_add computes r = a + b in Fp2. */
181 : static inline fd_bn254_fp2_t *
182 : fd_bn254_fp2_add( fd_bn254_fp2_t * r,
183 : fd_bn254_fp2_t const * a,
184 8208009 : fd_bn254_fp2_t const * b ) {
185 8208009 : fd_bn254_fp_add( &r->el[0], &a->el[0], &b->el[0] );
186 8208009 : fd_bn254_fp_add( &r->el[1], &a->el[1], &b->el[1] );
187 8208009 : return r;
188 8208009 : }
189 :
190 : /* fd_bn254_fp2_sub computes r = a - b in Fp2. */
191 : static inline fd_bn254_fp2_t *
192 : fd_bn254_fp2_sub( fd_bn254_fp2_t * r,
193 : fd_bn254_fp2_t const * a,
194 5136297 : fd_bn254_fp2_t const * b ) {
195 5136297 : fd_bn254_fp_sub( &r->el[0], &a->el[0], &b->el[0] );
196 5136297 : fd_bn254_fp_sub( &r->el[1], &a->el[1], &b->el[1] );
197 5136297 : return r;
198 5136297 : }
199 :
200 : /* fd_bn254_fp2_conj computes r = conj(a) in Fp2.
201 : If a = a0 + a1*i, conj(a) = a0 - a1*i. */
202 : static inline fd_bn254_fp2_t *
203 : fd_bn254_fp2_conj( fd_bn254_fp2_t * r,
204 21273 : fd_bn254_fp2_t const * a ) {
205 21273 : fd_bn254_fp_set( &r->el[0], &a->el[0] );
206 21273 : fd_bn254_fp_neg( &r->el[1], &a->el[1] );
207 21273 : return r;
208 21273 : }
209 :
210 : /* fd_bn254_fp2_mul computes r = a * b in Fp2.
211 : Karatsuba mul + reduction given that i^2 = -1.
212 : Note: this can probably be optimized, see for ideas:
213 : https://eprint.iacr.org/2010/354 */
214 : static inline fd_bn254_fp2_t *
215 : fd_bn254_fp2_mul( fd_bn254_fp2_t * r,
216 : fd_bn254_fp2_t const * a,
217 4179435 : fd_bn254_fp2_t const * b ) {
218 4179435 : fd_bn254_fp_t const * a0 = &a->el[0];
219 4179435 : fd_bn254_fp_t const * a1 = &a->el[1];
220 4179435 : fd_bn254_fp_t const * b0 = &b->el[0];
221 4179435 : fd_bn254_fp_t const * b1 = &b->el[1];
222 4179435 : fd_bn254_fp_t * r0 = &r->el[0];
223 4179435 : fd_bn254_fp_t * r1 = &r->el[1];
224 4179435 : fd_bn254_fp_t a0b0[1], a1b1[1], sa[1], sb[1];
225 :
226 4179435 : fd_bn254_fp_add( sa, a0, a1 );
227 4179435 : fd_bn254_fp_add( sb, b0, b1 );
228 :
229 4179435 : fd_bn254_fp_mul( a0b0, a0, b0 );
230 4179435 : fd_bn254_fp_mul( a1b1, a1, b1 );
231 4179435 : fd_bn254_fp_mul( r1, sa, sb );
232 :
233 4179435 : fd_bn254_fp_sub( r0, a0b0, a1b1 ); /* i^2 = -1 */
234 4179435 : fd_bn254_fp_sub( r1, r1, a0b0 );
235 4179435 : fd_bn254_fp_sub( r1, r1, a1b1 );
236 4179435 : return r;
237 4179435 : }
238 :
239 : /* fd_bn254_fp2_mul computes r = a^2 in Fp2.
240 : https://eprint.iacr.org/2010/354, Alg. 3.
241 : This is done with 2mul in Fp, instead of 2sqr+1mul. */
242 : static inline fd_bn254_fp2_t *
243 : fd_bn254_fp2_sqr( fd_bn254_fp2_t * r,
244 3992055 : fd_bn254_fp2_t const * a ) {
245 3992055 : fd_bn254_fp_t p[1], m[1];
246 3992055 : fd_bn254_fp_add( p, &a->el[0], &a->el[1] );
247 3992055 : fd_bn254_fp_sub( m, &a->el[0], &a->el[1] );
248 : /* r1 = 2 a0*a1 */
249 3992055 : fd_bn254_fp_mul( &r->el[1], &a->el[0], &a->el[1] );
250 3992055 : fd_bn254_fp_add( &r->el[1], &r->el[1], &r->el[1] );
251 : /* r0 = (a0-a1)*(a0+a1) */
252 3992055 : fd_bn254_fp_mul( &r->el[0], p, m );
253 3992055 : return r;
254 3992055 : }
255 :
256 : /* fd_bn254_fp2_mul_by_i computes r = a * i in Fp2. */
257 : static inline fd_bn254_fp2_t *
258 : fd_bn254_fp2_mul_by_i( fd_bn254_fp2_t * r,
259 0 : fd_bn254_fp2_t const * a ) {
260 0 : fd_bn254_fp_t t[1];
261 0 : fd_bn254_fp_neg( t, &a->el[1] );
262 0 : fd_bn254_fp_set( &r->el[1], &a->el[0] );
263 0 : fd_bn254_fp_set( &r->el[0], t );
264 0 : return r;
265 0 : }
266 :
267 : /* fd_bn254_fp2_inv computes r = 1 / a in Fp2.
268 : a MUST not be 0.
269 : https://eprint.iacr.org/2010/354, Alg. 8. */
270 : static inline fd_bn254_fp2_t *
271 : fd_bn254_fp2_inv( fd_bn254_fp2_t * r,
272 32517 : fd_bn254_fp2_t const * a ) {
273 32517 : fd_bn254_fp_t t0[1], t1[1];
274 32517 : fd_bn254_fp_sqr( t0, &a->el[0] );
275 32517 : fd_bn254_fp_sqr( t1, &a->el[1] );
276 32517 : fd_bn254_fp_add( t0, t0, t1 );
277 32517 : fd_bn254_fp_inv( t1, t0 );
278 32517 : fd_bn254_fp_mul( &r->el[0], &a->el[0], t1 );
279 32517 : fd_bn254_fp_mul( &r->el[1], &a->el[1], t1 );
280 32517 : fd_bn254_fp_neg( &r->el[1], &r->el[1] );
281 32517 : return r;
282 32517 : }
283 :
284 : /* fd_bn254_fp2_pow computes r = a ^ b in Fp2. */
285 : fd_bn254_fp2_t *
286 : fd_bn254_fp2_pow( fd_bn254_fp2_t * restrict r,
287 : fd_bn254_fp2_t const * a,
288 6186 : fd_uint256_t const * b ) {
289 6186 : fd_bn254_fp2_set_one( r );
290 6186 : if( fd_uint256_is_zero( b ) ) return r; /* x^0 = 1 */
291 :
292 : /* There must be a bit set, as b>0, so if we reach i==0, it must be set. */
293 6186 : int i = 255;
294 27837 : while( !fd_uint256_bit( b, i ) ) i--;
295 :
296 1568151 : for( ; i>=0; i--) {
297 1561965 : fd_bn254_fp2_sqr( r, r );
298 1561965 : if( fd_uint256_bit( b, i ) ) {
299 677367 : fd_bn254_fp2_mul( r, r, a );
300 677367 : }
301 1561965 : }
302 6186 : return r;
303 6186 : }
304 :
305 : /* fd_bn254_fp2_sqrt computes r = sqrt(a) in Fp2.
306 : https://eprint.iacr.org/2012/685, Alg. 9.
307 : Note: r is one of the two sqrt, the other is -r. This function
308 : can return either the positive or negative one, no assumptions/promises.
309 : Returns r if a is a square (sqrt exists), or NULL otherwise. */
310 : static inline fd_bn254_fp2_t *
311 : fd_bn254_fp2_sqrt( fd_bn254_fp2_t * r,
312 3093 : fd_bn254_fp2_t const * a ) {
313 3093 : fd_bn254_fp2_t a0[1], a1[1], alpha[1], x0[1];
314 :
315 3093 : fd_bn254_fp2_pow( a1, a, fd_bn254_const_sqrt_exp );
316 :
317 3093 : fd_bn254_fp2_sqr( alpha, a1 );
318 3093 : fd_bn254_fp2_mul( alpha, alpha, a );
319 :
320 3093 : fd_bn254_fp2_conj( a0, alpha );
321 3093 : fd_bn254_fp2_mul( a0, a0, alpha );
322 :
323 3093 : if( FD_UNLIKELY( fd_bn254_fp2_is_minus_one( a0 ) ) ) {
324 0 : return NULL;
325 0 : }
326 :
327 3093 : fd_bn254_fp2_mul( x0, a1, a );
328 3093 : if( fd_bn254_fp2_is_minus_one( alpha ) ) {
329 : /* COV: I don't know if there's a point that hits this condition.
330 : sqrt(-1) hits this, but doesn't correspond to a valid point.
331 : Tried with some other possible values, nothing corresponds to a point. */
332 0 : fd_bn254_fp2_mul_by_i( r, x0 );
333 3093 : } else {
334 3093 : fd_bn254_fp2_set_one( a1 );
335 3093 : fd_bn254_fp2_add( a0, alpha, a1 ); /* 1 + alpha */
336 3093 : fd_bn254_fp2_pow( a1, a0, fd_bn254_const_p_minus_one_half ); /* b */
337 3093 : fd_bn254_fp2_mul( r, a1, x0 );
338 3093 : }
339 3093 : return r;
340 3093 : }
341 :
342 : /* fd_bn254_fp2_mul_by_xi computes r = a * (9+i) in Fp2.
343 : xi = (9+i) is the const used to build Fp6.
344 : Note: this can probably be optimized (less reductions mod p). */
345 : static inline fd_bn254_fp2_t *
346 : fd_bn254_fp2_mul_by_xi( fd_bn254_fp2_t * r,
347 1221111 : fd_bn254_fp2_t const * a ) {
348 : /* xi = 9 + i
349 : r = (9*a0 - a1) + (9*a1 + a0) i */
350 1221111 : fd_bn254_fp_t r0[1], r1[1];
351 :
352 1221111 : fd_bn254_fp_add( r0, &a->el[0], &a->el[0] );
353 1221111 : fd_bn254_fp_add( r0, r0, r0 );
354 1221111 : fd_bn254_fp_add( r0, r0, r0 );
355 1221111 : fd_bn254_fp_add( r0, r0, &a->el[0] );
356 1221111 : fd_bn254_fp_sub( r0, r0, &a->el[1] );
357 :
358 1221111 : fd_bn254_fp_add( r1, &a->el[1], &a->el[1] );
359 1221111 : fd_bn254_fp_add( r1, r1, r1 );
360 1221111 : fd_bn254_fp_add( r1, r1, r1 );
361 1221111 : fd_bn254_fp_add( r1, r1, &a->el[1] );
362 1221111 : fd_bn254_fp_add( &r->el[1], r1, &a->el[0] );
363 :
364 1221111 : fd_bn254_fp_set( &r->el[0], r0 );
365 1221111 : return r;
366 1221111 : }
367 :
368 : /* Fp6 */
369 :
370 : static inline fd_bn254_fp6_t *
371 : fd_bn254_fp6_set( fd_bn254_fp6_t * r,
372 3465 : fd_bn254_fp6_t const * a ) {
373 3465 : fd_bn254_fp2_set( &r->el[0], &a->el[0] );
374 3465 : fd_bn254_fp2_set( &r->el[1], &a->el[1] );
375 3465 : fd_bn254_fp2_set( &r->el[2], &a->el[2] );
376 3465 : return r;
377 3465 : }
378 :
379 : static inline fd_bn254_fp6_t *
380 : fd_bn254_fp6_neg( fd_bn254_fp6_t * r,
381 4158 : fd_bn254_fp6_t const * a ) {
382 4158 : fd_bn254_fp2_neg( &r->el[0], &a->el[0] );
383 4158 : fd_bn254_fp2_neg( &r->el[1], &a->el[1] );
384 4158 : fd_bn254_fp2_neg( &r->el[2], &a->el[2] );
385 4158 : return r;
386 4158 : }
387 :
388 : static inline fd_bn254_fp6_t *
389 : fd_bn254_fp6_add( fd_bn254_fp6_t * r,
390 : fd_bn254_fp6_t const * a,
391 360618 : fd_bn254_fp6_t const * b ) {
392 360618 : fd_bn254_fp2_add( &r->el[0], &a->el[0], &b->el[0] );
393 360618 : fd_bn254_fp2_add( &r->el[1], &a->el[1], &b->el[1] );
394 360618 : fd_bn254_fp2_add( &r->el[2], &a->el[2], &b->el[2] );
395 360618 : return r;
396 360618 : }
397 :
398 : static inline fd_bn254_fp6_t *
399 : fd_bn254_fp6_sub( fd_bn254_fp6_t * r,
400 : fd_bn254_fp6_t const * a,
401 292497 : fd_bn254_fp6_t const * b ) {
402 292497 : fd_bn254_fp2_sub( &r->el[0], &a->el[0], &b->el[0] );
403 292497 : fd_bn254_fp2_sub( &r->el[1], &a->el[1], &b->el[1] );
404 292497 : fd_bn254_fp2_sub( &r->el[2], &a->el[2], &b->el[2] );
405 292497 : return r;
406 292497 : }
407 :
408 : static inline fd_bn254_fp6_t *
409 : fd_bn254_fp6_mul_by_gamma( fd_bn254_fp6_t * r,
410 171363 : fd_bn254_fp6_t const * a ) {
411 : /* https://eprint.iacr.org/2010/354, Alg. 12 */
412 171363 : fd_bn254_fp2_t t[1];
413 171363 : fd_bn254_fp2_mul_by_xi( t, &a->el[2] );
414 171363 : fd_bn254_fp2_set( &r->el[2], &a->el[1] );
415 171363 : fd_bn254_fp2_set( &r->el[1], &a->el[0] );
416 171363 : fd_bn254_fp2_set( &r->el[0], t );
417 171363 : return r;
418 171363 : }
419 :
420 : static inline fd_bn254_fp6_t *
421 : fd_bn254_fp6_mul( fd_bn254_fp6_t * r,
422 : fd_bn254_fp6_t const * a,
423 183060 : fd_bn254_fp6_t const * b ) {
424 : /* https://eprint.iacr.org/2010/354, Alg. 13 */
425 183060 : fd_bn254_fp2_t const * a0 = &a->el[0];
426 183060 : fd_bn254_fp2_t const * a1 = &a->el[1];
427 183060 : fd_bn254_fp2_t const * a2 = &a->el[2];
428 183060 : fd_bn254_fp2_t const * b0 = &b->el[0];
429 183060 : fd_bn254_fp2_t const * b1 = &b->el[1];
430 183060 : fd_bn254_fp2_t const * b2 = &b->el[2];
431 183060 : fd_bn254_fp2_t a0b0[1], a1b1[1], a2b2[1];
432 183060 : fd_bn254_fp2_t sa[1], sb[1];
433 183060 : fd_bn254_fp2_t r0[1], r1[1], r2[1];
434 :
435 183060 : fd_bn254_fp2_mul( a0b0, a0, b0 );
436 183060 : fd_bn254_fp2_mul( a1b1, a1, b1 );
437 183060 : fd_bn254_fp2_mul( a2b2, a2, b2 );
438 :
439 183060 : fd_bn254_fp2_add( sa, a1, a2 );
440 183060 : fd_bn254_fp2_add( sb, b1, b2 );
441 183060 : fd_bn254_fp2_mul( r0, sa, sb );
442 183060 : fd_bn254_fp2_sub( r0, r0, a1b1 );
443 183060 : fd_bn254_fp2_sub( r0, r0, a2b2 );
444 183060 : fd_bn254_fp2_mul_by_xi( r0, r0 );
445 183060 : fd_bn254_fp2_add( r0, r0, a0b0 );
446 :
447 183060 : fd_bn254_fp2_add( sa, a0, a2 );
448 183060 : fd_bn254_fp2_add( sb, b0, b2 );
449 183060 : fd_bn254_fp2_mul( r2, sa, sb );
450 183060 : fd_bn254_fp2_sub( r2, r2, a0b0 );
451 183060 : fd_bn254_fp2_sub( r2, r2, a2b2 );
452 183060 : fd_bn254_fp2_add( r2, r2, a1b1 );
453 :
454 183060 : fd_bn254_fp2_add( sa, a0, a1 );
455 183060 : fd_bn254_fp2_add( sb, b0, b1 );
456 183060 : fd_bn254_fp2_mul( r1, sa, sb );
457 183060 : fd_bn254_fp2_sub( r1, r1, a0b0 );
458 183060 : fd_bn254_fp2_sub( r1, r1, a1b1 );
459 183060 : fd_bn254_fp2_mul_by_xi( a2b2, a2b2 );
460 183060 : fd_bn254_fp2_add( r1, r1, a2b2 );
461 :
462 183060 : fd_bn254_fp2_set( &r->el[0], r0 );
463 183060 : fd_bn254_fp2_set( &r->el[1], r1 );
464 183060 : fd_bn254_fp2_set( &r->el[2], r2 );
465 183060 : return r;
466 183060 : }
467 :
468 : static inline fd_bn254_fp6_t *
469 : fd_bn254_fp6_sqr( fd_bn254_fp6_t * r,
470 1386 : fd_bn254_fp6_t const * a ) {
471 : /* https://eprint.iacr.org/2010/354, Alg. 16 */
472 1386 : fd_bn254_fp2_t const * a0 = &a->el[0];
473 1386 : fd_bn254_fp2_t const * a1 = &a->el[1];
474 1386 : fd_bn254_fp2_t const * a2 = &a->el[2];
475 1386 : fd_bn254_fp2_t c0[1], c1[1], c2[1];
476 1386 : fd_bn254_fp2_t c3[1], c4[1], c5[1];
477 :
478 1386 : fd_bn254_fp2_mul( c4, a0, a1 );
479 1386 : fd_bn254_fp2_add( c4, c4, c4 );
480 1386 : fd_bn254_fp2_sqr( c5, a2 );
481 :
482 1386 : fd_bn254_fp2_sub( c2, c4, c5 );
483 1386 : fd_bn254_fp2_mul_by_xi( c5, c5 );
484 1386 : fd_bn254_fp2_add( c1, c4, c5 );
485 :
486 1386 : fd_bn254_fp2_sqr( c3, a0 );
487 1386 : fd_bn254_fp2_sub( c4, a0, a1 );
488 1386 : fd_bn254_fp2_add( c4, c4, a2 );
489 :
490 1386 : fd_bn254_fp2_mul( c5, a1, a2 );
491 1386 : fd_bn254_fp2_add( c5, c5, c5 );
492 1386 : fd_bn254_fp2_sqr( c4, c4 );
493 :
494 1386 : fd_bn254_fp2_add( c2, c2, c4 );
495 1386 : fd_bn254_fp2_add( c2, c2, c5 );
496 1386 : fd_bn254_fp2_sub( c2, c2, c3 );
497 1386 : fd_bn254_fp2_mul_by_xi( c5, c5 );
498 1386 : fd_bn254_fp2_add( c0, c3, c5 );
499 :
500 1386 : fd_bn254_fp2_set( &r->el[0], c0 );
501 1386 : fd_bn254_fp2_set( &r->el[1], c1 );
502 1386 : fd_bn254_fp2_set( &r->el[2], c2 );
503 1386 : return r;
504 1386 : }
505 :
506 : static inline fd_bn254_fp6_t *
507 : fd_bn254_fp6_inv( fd_bn254_fp6_t * r,
508 693 : fd_bn254_fp6_t const * a ) {
509 : /* https://eprint.iacr.org/2010/354, Alg. 17 */
510 693 : fd_bn254_fp2_t t[6];
511 693 : fd_bn254_fp2_sqr( &t[0], &a->el[0] );
512 693 : fd_bn254_fp2_sqr( &t[1], &a->el[1] );
513 693 : fd_bn254_fp2_sqr( &t[2], &a->el[2] );
514 693 : fd_bn254_fp2_mul( &t[3], &a->el[0], &a->el[1] );
515 693 : fd_bn254_fp2_mul( &t[4], &a->el[0], &a->el[2] );
516 693 : fd_bn254_fp2_mul( &t[5], &a->el[1], &a->el[2] );
517 : /* t0 := c0 = t0 - xi * t5 */
518 693 : fd_bn254_fp2_mul_by_xi( &t[5], &t[5] );
519 693 : fd_bn254_fp2_sub( &t[0], &t[0], &t[5] );
520 : /* t2 := c1 = xi * t2 - t3 */
521 693 : fd_bn254_fp2_mul_by_xi( &t[2], &t[2] );
522 693 : fd_bn254_fp2_sub( &t[2], &t[2], &t[3] );
523 : /* t1 := c2 = t1 - t4 (note: paper says t1*t4, but that's a misprint) */
524 693 : fd_bn254_fp2_sub( &t[1], &t[1], &t[4] );
525 : /* t3 := t6 = a0 * c0 */
526 693 : fd_bn254_fp2_mul( &t[3], &a->el[0], &t[0] );
527 : /* t3 := t6 = t6 + (xi * a2 * c1 =: t4) */
528 693 : fd_bn254_fp2_mul( &t[4], &a->el[2], &t[2] );
529 693 : fd_bn254_fp2_mul_by_xi( &t[4], &t[4] );
530 693 : fd_bn254_fp2_add( &t[3], &t[3], &t[4] );
531 : /* t3 := t6 = t6 + (xi * a2 * c1 =: t4) */
532 693 : fd_bn254_fp2_mul( &t[5], &a->el[1], &t[1] );
533 693 : fd_bn254_fp2_mul_by_xi( &t[5], &t[5] );
534 693 : fd_bn254_fp2_add( &t[3], &t[3], &t[5] );
535 : /* t4 := t6^-1 */
536 693 : fd_bn254_fp2_inv( &t[4], &t[3] );
537 :
538 693 : fd_bn254_fp2_mul( &r->el[0], &t[0], &t[4] );
539 693 : fd_bn254_fp2_mul( &r->el[1], &t[2], &t[4] );
540 693 : fd_bn254_fp2_mul( &r->el[2], &t[1], &t[4] );
541 693 : return r;
542 693 : }
543 :
544 : /* Fp12 */
545 :
546 : static inline fd_bn254_fp12_t *
547 : fd_bn254_fp12_conj( fd_bn254_fp12_t * r,
548 3465 : fd_bn254_fp12_t const * a ) {
549 3465 : fd_bn254_fp6_set( &r->el[0], &a->el[0] );
550 3465 : fd_bn254_fp6_neg( &r->el[1], &a->el[1] );
551 3465 : return r;
552 3465 : }
553 :
554 : /*
555 : static inline fd_bn254_fp12_t *
556 : fd_bn254_fp12_add( fd_bn254_fp12_t * r,
557 : fd_bn254_fp12_t const * a,
558 : fd_bn254_fp12_t const * b ) {
559 : fd_bn254_fp6_add( &r->el[0], &a->el[0], &b->el[0] );
560 : fd_bn254_fp6_add( &r->el[1], &a->el[1], &b->el[1] );
561 : return r;
562 : }
563 :
564 : static inline fd_bn254_fp12_t *
565 : fd_bn254_fp12_sub( fd_bn254_fp12_t * r,
566 : fd_bn254_fp12_t const * a,
567 : fd_bn254_fp12_t const * b ) {
568 : fd_bn254_fp6_sub( &r->el[0], &a->el[0], &b->el[0] );
569 : fd_bn254_fp6_sub( &r->el[1], &a->el[1], &b->el[1] );
570 : return r;
571 : }
572 : */
573 :
574 : /* fd_bn254_fp6_mul_by_fp2 computes r = a * (b, 0, 0) in Fp6.
575 : Simply (a0*b, a1*b, a2*b).
576 : Cost: 3 Fp2_mul (vs 6 for full Fp6_mul). */
577 : static inline fd_bn254_fp6_t *
578 : fd_bn254_fp6_mul_by_fp2( fd_bn254_fp6_t * r,
579 : fd_bn254_fp6_t const * a,
580 77088 : fd_bn254_fp2_t const * b ) {
581 77088 : fd_bn254_fp2_mul( &r->el[0], &a->el[0], b );
582 77088 : fd_bn254_fp2_mul( &r->el[1], &a->el[1], b );
583 77088 : fd_bn254_fp2_mul( &r->el[2], &a->el[2], b );
584 77088 : return r;
585 77088 : }
586 :
587 : /* fd_bn254_fp6_mul_by_01 computes r = a * (b0, b1, 0) in Fp6.
588 : Karatsuba with b2=0.
589 : Cost: 5 Fp2_mul (vs 6 for full Fp6_mul). */
590 : static inline fd_bn254_fp6_t *
591 : fd_bn254_fp6_mul_by_01( fd_bn254_fp6_t * r,
592 : fd_bn254_fp6_t const * a,
593 : fd_bn254_fp2_t const * b0,
594 154176 : fd_bn254_fp2_t const * b1 ) {
595 154176 : fd_bn254_fp2_t const * a0 = &a->el[0];
596 154176 : fd_bn254_fp2_t const * a1 = &a->el[1];
597 154176 : fd_bn254_fp2_t const * a2 = &a->el[2];
598 154176 : fd_bn254_fp2_t a0b0[1], a1b1[1];
599 154176 : fd_bn254_fp2_t sa[1], sb[1];
600 154176 : fd_bn254_fp2_t r0[1], r1[1], r2[1];
601 :
602 154176 : fd_bn254_fp2_mul( a0b0, a0, b0 );
603 154176 : fd_bn254_fp2_mul( a1b1, a1, b1 );
604 :
605 : /* r0 = a0b0 + xi * a2*b1 */
606 154176 : fd_bn254_fp2_mul( r0, a2, b1 );
607 154176 : fd_bn254_fp2_mul_by_xi( r0, r0 );
608 154176 : fd_bn254_fp2_add( r0, r0, a0b0 );
609 :
610 : /* r1 = (a0+a1)*(b0+b1) - a0b0 - a1b1 */
611 154176 : fd_bn254_fp2_add( sa, a0, a1 );
612 154176 : fd_bn254_fp2_add( sb, b0, b1 );
613 154176 : fd_bn254_fp2_mul( r1, sa, sb );
614 154176 : fd_bn254_fp2_sub( r1, r1, a0b0 );
615 154176 : fd_bn254_fp2_sub( r1, r1, a1b1 );
616 :
617 : /* r2 = (a0+a2)*b0 - a0b0 + a1b1 */
618 154176 : fd_bn254_fp2_add( sa, a0, a2 );
619 154176 : fd_bn254_fp2_mul( r2, sa, b0 );
620 154176 : fd_bn254_fp2_sub( r2, r2, a0b0 );
621 154176 : fd_bn254_fp2_add( r2, r2, a1b1 );
622 :
623 154176 : fd_bn254_fp2_set( &r->el[0], r0 );
624 154176 : fd_bn254_fp2_set( &r->el[1], r1 );
625 154176 : fd_bn254_fp2_set( &r->el[2], r2 );
626 154176 : return r;
627 154176 : }
628 :
629 : /* fd_bn254_fp12_mul_sparse computes r = a * b in Fp12,
630 : where b has the "034" sparse pattern:
631 : b.el[0] = (c0, 0, 0)
632 : b.el[1] = (c3, c4, 0)
633 : This is the pattern produced by line evaluation functions.
634 : Cost: 13 Fp2_mul (vs 18 for full Fp12_mul). */
635 : static inline fd_bn254_fp12_t *
636 : fd_bn254_fp12_mul_sparse( fd_bn254_fp12_t * r,
637 : fd_bn254_fp12_t const * a,
638 77088 : fd_bn254_fp12_t const * b ) {
639 77088 : fd_bn254_fp2_t const * c0 = &b->el[0].el[0];
640 77088 : fd_bn254_fp2_t const * c3 = &b->el[1].el[0];
641 77088 : fd_bn254_fp2_t const * c4 = &b->el[1].el[1];
642 77088 : fd_bn254_fp6_t a0b0[1], a1b1[1], sa[1];
643 77088 : fd_bn254_fp2_t sc0[1];
644 :
645 : /* a0*b0 = a.el[0] * (c0, 0, 0) : 3 Fp2_mul */
646 77088 : fd_bn254_fp6_mul_by_fp2( a0b0, &a->el[0], c0 );
647 :
648 : /* a1*b1 = a.el[1] * (c3, c4, 0) : 5 Fp2_mul */
649 77088 : fd_bn254_fp6_mul_by_01( a1b1, &a->el[1], c3, c4 );
650 :
651 : /* r1 = (a0+a1) * (c0+c3, c4, 0) - a0b0 - a1b1 : 5 Fp2_mul */
652 77088 : fd_bn254_fp6_add( sa, &a->el[0], &a->el[1] );
653 77088 : fd_bn254_fp2_add( sc0, c0, c3 );
654 77088 : fd_bn254_fp6_mul_by_01( &r->el[1], sa, sc0, c4 );
655 77088 : fd_bn254_fp6_sub( &r->el[1], &r->el[1], a0b0 );
656 77088 : fd_bn254_fp6_sub( &r->el[1], &r->el[1], a1b1 );
657 :
658 : /* r0 = a0b0 + gamma * a1b1 */
659 77088 : fd_bn254_fp6_mul_by_gamma( a1b1, a1b1 );
660 77088 : fd_bn254_fp6_add( &r->el[0], a0b0, a1b1 );
661 77088 : return r;
662 77088 : }
663 :
664 : fd_bn254_fp12_t *
665 : fd_bn254_fp12_mul( fd_bn254_fp12_t * r,
666 : fd_bn254_fp12_t const * a,
667 44046 : fd_bn254_fp12_t const * b ) {
668 : /* https://eprint.iacr.org/2010/354, Alg. 20 */
669 44046 : fd_bn254_fp6_t const * a0 = &a->el[0];
670 44046 : fd_bn254_fp6_t const * a1 = &a->el[1];
671 44046 : fd_bn254_fp6_t const * b0 = &b->el[0];
672 44046 : fd_bn254_fp6_t const * b1 = &b->el[1];
673 44046 : fd_bn254_fp6_t * r0 = &r->el[0];
674 44046 : fd_bn254_fp6_t * r1 = &r->el[1];
675 44046 : fd_bn254_fp6_t a0b0[1], a1b1[1], sa[1], sb[1];
676 :
677 44046 : fd_bn254_fp6_add( sa, a0, a1 );
678 44046 : fd_bn254_fp6_add( sb, b0, b1 );
679 :
680 44046 : fd_bn254_fp6_mul( a0b0, a0, b0 );
681 44046 : fd_bn254_fp6_mul( a1b1, a1, b1 );
682 44046 : fd_bn254_fp6_mul( r1, sa, sb );
683 :
684 44046 : fd_bn254_fp6_sub( r1, r1, a0b0 );
685 44046 : fd_bn254_fp6_sub( r1, r1, a1b1 );
686 :
687 44046 : fd_bn254_fp6_mul_by_gamma( a1b1, a1b1 );
688 44046 : fd_bn254_fp6_add( r0, a0b0, a1b1 );
689 44046 : return r;
690 44046 : }
691 :
692 : static inline fd_bn254_fp12_t *
693 : fd_bn254_fp12_sqr( fd_bn254_fp12_t * r,
694 24768 : fd_bn254_fp12_t const * a ) {
695 : /* https://eprint.iacr.org/2010/354, Alg. 22. */
696 24768 : fd_bn254_fp6_t c0[1], c2[1], c3[1];
697 24768 : fd_bn254_fp6_sub( c0, &a->el[0], &a->el[1] );
698 24768 : fd_bn254_fp6_mul_by_gamma( c3, &a->el[1] );
699 24768 : fd_bn254_fp6_sub( c3, &a->el[0], c3 );
700 24768 : fd_bn254_fp6_mul( c2, &a->el[0], &a->el[1] );
701 24768 : fd_bn254_fp6_mul( c0, c0, c3 );
702 24768 : fd_bn254_fp6_add( c0, c0, c2 );
703 24768 : fd_bn254_fp6_add( &r->el[1], c2, c2 );
704 24768 : fd_bn254_fp6_mul_by_gamma( &r->el[0], c2 );
705 24768 : fd_bn254_fp6_add( &r->el[0], &r->el[0], c0 );
706 24768 : return r;
707 24768 : }
708 :
709 : static inline fd_bn254_fp12_t *
710 : fd_bn254_fp12_sqr_fast( fd_bn254_fp12_t * r,
711 130977 : fd_bn254_fp12_t const * a ) {
712 : /* Cyclotomic sqr, https://eprint.iacr.org/2009/565, Sec. 3.2.
713 : Variant of https://eprint.iacr.org/2010/354, Alg. 24.
714 : This works when a^(p^6+1)=1, e.g. during pairing final exp. */
715 130977 : fd_bn254_fp2_t t[9];
716 :
717 130977 : fd_bn254_fp2_sqr( &t[0], &a->el[1].el[1] );
718 130977 : fd_bn254_fp2_sqr( &t[1], &a->el[0].el[0] );
719 130977 : fd_bn254_fp2_add( &t[6], &a->el[1].el[1], &a->el[0].el[0] );
720 130977 : fd_bn254_fp2_sqr( &t[6], &t[6] );
721 130977 : fd_bn254_fp2_sub( &t[6], &t[6], &t[0] );
722 130977 : fd_bn254_fp2_sub( &t[6], &t[6], &t[1] );
723 :
724 130977 : fd_bn254_fp2_sqr( &t[2], &a->el[0].el[2] );
725 130977 : fd_bn254_fp2_sqr( &t[3], &a->el[1].el[0] );
726 130977 : fd_bn254_fp2_add( &t[7], &a->el[0].el[2], &a->el[1].el[0] );
727 130977 : fd_bn254_fp2_sqr( &t[7], &t[7] );
728 130977 : fd_bn254_fp2_sub( &t[7], &t[7], &t[2] );
729 130977 : fd_bn254_fp2_sub( &t[7], &t[7], &t[3] );
730 :
731 130977 : fd_bn254_fp2_sqr( &t[4], &a->el[1].el[2] );
732 130977 : fd_bn254_fp2_sqr( &t[5], &a->el[0].el[1] );
733 130977 : fd_bn254_fp2_add( &t[8], &a->el[1].el[2], &a->el[0].el[1] );
734 130977 : fd_bn254_fp2_sqr( &t[8], &t[8] );
735 130977 : fd_bn254_fp2_sub( &t[8], &t[8], &t[4] );
736 130977 : fd_bn254_fp2_sub( &t[8], &t[8], &t[5] );
737 130977 : fd_bn254_fp2_mul_by_xi( &t[8], &t[8] );
738 :
739 130977 : fd_bn254_fp2_mul_by_xi( &t[0], &t[0] );
740 130977 : fd_bn254_fp2_add( &t[0], &t[0], &t[1] );
741 130977 : fd_bn254_fp2_mul_by_xi( &t[2], &t[2] );
742 130977 : fd_bn254_fp2_add( &t[2], &t[2], &t[3] );
743 130977 : fd_bn254_fp2_mul_by_xi( &t[4], &t[4] );
744 130977 : fd_bn254_fp2_add( &t[4], &t[4], &t[5] );
745 :
746 130977 : fd_bn254_fp2_sub( &r->el[0].el[0], &t[0], &a->el[0].el[0] );
747 130977 : fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &r->el[0].el[0] );
748 130977 : fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &t[0] );
749 130977 : fd_bn254_fp2_sub( &r->el[0].el[1], &t[2], &a->el[0].el[1] );
750 130977 : fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &r->el[0].el[1] );
751 130977 : fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &t[2] );
752 130977 : fd_bn254_fp2_sub( &r->el[0].el[2], &t[4], &a->el[0].el[2] );
753 130977 : fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &r->el[0].el[2] );
754 130977 : fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &t[4] );
755 :
756 130977 : fd_bn254_fp2_add( &r->el[1].el[0], &t[8], &a->el[1].el[0] );
757 130977 : fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &r->el[1].el[0] );
758 130977 : fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &t[8] );
759 130977 : fd_bn254_fp2_add( &r->el[1].el[1], &t[6], &a->el[1].el[1] );
760 130977 : fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &r->el[1].el[1] );
761 130977 : fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &t[6] );
762 130977 : fd_bn254_fp2_add( &r->el[1].el[2], &t[7], &a->el[1].el[2] );
763 130977 : fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &r->el[1].el[2] );
764 130977 : fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &t[7] );
765 130977 : return r;
766 130977 : }
767 :
768 : fd_bn254_fp12_t *
769 : fd_bn254_fp12_inv( fd_bn254_fp12_t * r,
770 693 : fd_bn254_fp12_t const * a ) {
771 : /* https://eprint.iacr.org/2010/354, Alg. 23 */
772 693 : fd_bn254_fp6_t t0[1], t1[1];
773 693 : fd_bn254_fp6_sqr( t0, &a->el[0] );
774 693 : fd_bn254_fp6_sqr( t1, &a->el[1] );
775 693 : fd_bn254_fp6_mul_by_gamma( t1, t1 );
776 693 : fd_bn254_fp6_sub( t0, t0, t1 );
777 693 : fd_bn254_fp6_inv( t1, t0 );
778 693 : fd_bn254_fp6_mul( &r->el[0], &a->el[0], t1 );
779 693 : fd_bn254_fp6_mul( &r->el[1], &a->el[1], t1 );
780 693 : fd_bn254_fp6_neg( &r->el[1], &r->el[1] );
781 693 : return r;
782 693 : }
783 :
784 : static inline fd_bn254_fp12_t *
785 : fd_bn254_fp12_frob( fd_bn254_fp12_t * r,
786 1386 : fd_bn254_fp12_t const * a ) {
787 : /* https://eprint.iacr.org/2010/354, Alg. 28 */
788 1386 : fd_bn254_fp2_t t[5];
789 :
790 : /* conj(g0) */
791 1386 : fd_bn254_fp2_conj( &r->el[0].el[0], &a->el[0].el[0] );
792 1386 : fd_bn254_fp2_conj( &t[0], &a->el[0].el[1] );
793 1386 : fd_bn254_fp2_conj( &t[1], &a->el[0].el[2] );
794 1386 : fd_bn254_fp2_conj( &t[2], &a->el[1].el[0] );
795 1386 : fd_bn254_fp2_conj( &t[3], &a->el[1].el[1] );
796 1386 : fd_bn254_fp2_conj( &t[4], &a->el[1].el[2] );
797 :
798 : /* conj(g1) * gamma_1,2 */
799 1386 : fd_bn254_fp2_mul( &r->el[0].el[1], &t[0], &fd_bn254_const_frob_gamma1_mont[1] );
800 :
801 : /* conj(g2) * gamma_1,4 */
802 1386 : fd_bn254_fp2_mul( &r->el[0].el[2], &t[1], &fd_bn254_const_frob_gamma1_mont[3] );
803 :
804 : /* conj(h0) * gamma_1,1 */
805 1386 : fd_bn254_fp2_mul( &r->el[1].el[0], &t[2], &fd_bn254_const_frob_gamma1_mont[0] );
806 :
807 : /* conj(h1) * gamma_1,3 */
808 1386 : fd_bn254_fp2_mul( &r->el[1].el[1], &t[3], &fd_bn254_const_frob_gamma1_mont[2] );
809 :
810 : /* conj(h2) * gamma_1,5 */
811 1386 : fd_bn254_fp2_mul( &r->el[1].el[2], &t[4], &fd_bn254_const_frob_gamma1_mont[4] );
812 1386 : return r;
813 1386 : }
814 :
815 : static inline fd_bn254_fp12_t *
816 : fd_bn254_fp12_frob2( fd_bn254_fp12_t * r,
817 2079 : fd_bn254_fp12_t const * a ) {
818 : /* https://eprint.iacr.org/2010/354, Alg. 29 */
819 :
820 : /* g0 */
821 2079 : fd_bn254_fp2_set( &r->el[0].el[0], &a->el[0].el[0] );
822 :
823 : /* g1 * gamma_2,2 */
824 2079 : fd_bn254_fp_mul( &r->el[0].el[1].el[0], &a->el[0].el[1].el[0], &fd_bn254_const_frob_gamma2_mont[1] );
825 2079 : fd_bn254_fp_mul( &r->el[0].el[1].el[1], &a->el[0].el[1].el[1], &fd_bn254_const_frob_gamma2_mont[1] );
826 :
827 : /* g2 * gamma_2,4 */
828 2079 : fd_bn254_fp_mul( &r->el[0].el[2].el[0], &a->el[0].el[2].el[0], &fd_bn254_const_frob_gamma2_mont[3] );
829 2079 : fd_bn254_fp_mul( &r->el[0].el[2].el[1], &a->el[0].el[2].el[1], &fd_bn254_const_frob_gamma2_mont[3] );
830 :
831 : /* h0 * gamma_2,1 */
832 2079 : fd_bn254_fp_mul( &r->el[1].el[0].el[0], &a->el[1].el[0].el[0], &fd_bn254_const_frob_gamma2_mont[0] );
833 2079 : fd_bn254_fp_mul( &r->el[1].el[0].el[1], &a->el[1].el[0].el[1], &fd_bn254_const_frob_gamma2_mont[0] );
834 :
835 : /* h1 * gamma_2,3 */
836 2079 : fd_bn254_fp_mul( &r->el[1].el[1].el[0], &a->el[1].el[1].el[0], &fd_bn254_const_frob_gamma2_mont[2] );
837 2079 : fd_bn254_fp_mul( &r->el[1].el[1].el[1], &a->el[1].el[1].el[1], &fd_bn254_const_frob_gamma2_mont[2] );
838 :
839 : /* h2 * gamma_2,5 */
840 2079 : fd_bn254_fp_mul( &r->el[1].el[2].el[0], &a->el[1].el[2].el[0], &fd_bn254_const_frob_gamma2_mont[4] );
841 2079 : fd_bn254_fp_mul( &r->el[1].el[2].el[1], &a->el[1].el[2].el[1], &fd_bn254_const_frob_gamma2_mont[4] );
842 2079 : return r;
843 2079 : }
|
