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 1170 : int * is_neg ) {
77 : /* validate fp2.el[0] without flags */
78 1170 : if( FD_UNLIKELY( !fd_bn254_fp_frombytes_nm( &r->el[0], &buf[ big_endian ? 32 : 0 ], big_endian, NULL, NULL ) ) ) {
79 351 : return NULL;
80 351 : }
81 : /* validate fp2.el[1] with flags */
82 819 : if( FD_UNLIKELY( !fd_bn254_fp_frombytes_nm( &r->el[1], &buf[ big_endian ? 0 : 32 ], big_endian, is_inf, is_neg ) ) ) {
83 212 : return NULL;
84 212 : }
85 607 : return r;
86 819 : }
87 :
88 : static inline uchar *
89 : fd_bn254_fp2_tobytes_nm( uchar buf[64],
90 : fd_bn254_fp2_t * const a,
91 207 : int big_endian ) {
92 207 : fd_bn254_fp_tobytes_nm( &buf[ 0], &a->el[ big_endian ? 1 : 0 ], big_endian );
93 207 : fd_bn254_fp_tobytes_nm( &buf[32], &a->el[ big_endian ? 0 : 1 ], big_endian );
94 207 : return buf;
95 207 : }
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 116 : fd_bn254_fp2_is_neg_nm( fd_bn254_fp2_t * x ) {
102 116 : if( FD_UNLIKELY( fd_bn254_fp_is_zero( &x->el[1] ) ) ) {
103 23 : return fd_bn254_fp_is_neg_nm( &x->el[0] );
104 23 : }
105 93 : return fd_bn254_fp_is_neg_nm( &x->el[1] );
106 116 : }
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 194 : fd_bn254_fp2_is_minus_one( fd_bn254_fp2_t const * a ) {
112 194 : return fd_uint256_eq( &a->el[0], fd_bn254_const_p_minus_one_mont )
113 194 : && fd_uint256_eq( &a->el[1], fd_bn254_const_zero );
114 194 : }
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 3608 : fd_bn254_fp2_t const * b ) {
121 3608 : return fd_bn254_fp_eq( &a->el[0], &b->el[0] )
122 3608 : && fd_bn254_fp_eq( &a->el[1], &b->el[1] );
123 3608 : }
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 150338 : fd_bn254_fp2_t const * a ) {
129 150338 : fd_bn254_fp_set( &r->el[0], &a->el[0] );
130 150338 : fd_bn254_fp_set( &r->el[1], &a->el[1] );
131 150338 : return r;
132 150338 : }
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 91 : fd_bn254_fp2_t const * a ) {
138 91 : fd_bn254_fp_from_mont( &r->el[0], &a->el[0] );
139 91 : fd_bn254_fp_from_mont( &r->el[1], &a->el[1] );
140 91 : return r;
141 91 : }
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 346 : fd_bn254_fp2_t const * a ) {
147 346 : fd_bn254_fp_to_mont( &r->el[0], &a->el[0] );
148 346 : fd_bn254_fp_to_mont( &r->el[1], &a->el[1] );
149 346 : return r;
150 346 : }
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 13 : fd_bn254_fp2_t const * x ) {
157 13 : fd_bn254_fp_neg_nm( &r->el[0], &x->el[0] );
158 13 : fd_bn254_fp_neg_nm( &r->el[1], &x->el[1] );
159 13 : return r;
160 13 : }
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 10090 : fd_bn254_fp2_t const * a ) {
166 10090 : fd_bn254_fp_neg( &r->el[0], &a->el[0] );
167 10090 : fd_bn254_fp_neg( &r->el[1], &a->el[1] );
168 10090 : return r;
169 10090 : }
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 10604 : fd_bn254_fp2_t const * a ) {
175 10604 : fd_bn254_fp_halve( &r->el[0], &a->el[0] );
176 10604 : fd_bn254_fp_halve( &r->el[1], &a->el[1] );
177 10604 : return r;
178 10604 : }
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 397506 : fd_bn254_fp2_t const * b ) {
185 397506 : fd_bn254_fp_add( &r->el[0], &a->el[0], &b->el[0] );
186 397506 : fd_bn254_fp_add( &r->el[1], &a->el[1], &b->el[1] );
187 397506 : return r;
188 397506 : }
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 305908 : fd_bn254_fp2_t const * b ) {
195 305908 : fd_bn254_fp_sub( &r->el[0], &a->el[0], &b->el[0] );
196 305908 : fd_bn254_fp_sub( &r->el[1], &a->el[1], &b->el[1] );
197 305908 : return r;
198 305908 : }
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 2203 : fd_bn254_fp2_t const * a ) {
205 2203 : fd_bn254_fp_set( &r->el[0], &a->el[0] );
206 2203 : fd_bn254_fp_neg( &r->el[1], &a->el[1] );
207 2203 : return r;
208 2203 : }
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 249113 : fd_bn254_fp2_t const * b ) {
218 249113 : fd_bn254_fp_t const * a0 = &a->el[0];
219 249113 : fd_bn254_fp_t const * a1 = &a->el[1];
220 249113 : fd_bn254_fp_t const * b0 = &b->el[0];
221 249113 : fd_bn254_fp_t const * b1 = &b->el[1];
222 249113 : fd_bn254_fp_t * r0 = &r->el[0];
223 249113 : fd_bn254_fp_t * r1 = &r->el[1];
224 249113 : fd_bn254_fp_t a0b0[1], a1b1[1], sa[1], sb[1];
225 :
226 249113 : fd_bn254_fp_add( sa, a0, a1 );
227 249113 : fd_bn254_fp_add( sb, b0, b1 );
228 :
229 249113 : fd_bn254_fp_mul( a0b0, a0, b0 );
230 249113 : fd_bn254_fp_mul( a1b1, a1, b1 );
231 249113 : fd_bn254_fp_mul( r1, sa, sb );
232 :
233 249113 : fd_bn254_fp_sub( r0, a0b0, a1b1 ); /* i^2 = -1 */
234 249113 : fd_bn254_fp_sub( r1, r1, a0b0 );
235 249113 : fd_bn254_fp_sub( r1, r1, a1b1 );
236 249113 : return r;
237 249113 : }
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 210543 : fd_bn254_fp2_t const * a ) {
245 210543 : fd_bn254_fp_t p[1], m[1];
246 210543 : fd_bn254_fp_add( p, &a->el[0], &a->el[1] );
247 210543 : fd_bn254_fp_sub( m, &a->el[0], &a->el[1] );
248 : /* r1 = 2 a0*a1 */
249 210543 : fd_bn254_fp_mul( &r->el[1], &a->el[0], &a->el[1] );
250 210543 : fd_bn254_fp_add( &r->el[1], &r->el[1], &r->el[1] );
251 : /* r0 = (a0-a1)*(a0+a1) */
252 210543 : fd_bn254_fp_mul( &r->el[0], p, m );
253 210543 : return r;
254 210543 : }
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 : https://eprint.iacr.org/2010/354, Alg. 8. */
269 : static inline fd_bn254_fp2_t *
270 : fd_bn254_fp2_inv( fd_bn254_fp2_t * r,
271 205 : fd_bn254_fp2_t const * a ) {
272 205 : fd_bn254_fp_t t0[1], t1[1];
273 205 : fd_bn254_fp_sqr( t0, &a->el[0] );
274 205 : fd_bn254_fp_sqr( t1, &a->el[1] );
275 205 : fd_bn254_fp_add( t0, t0, t1 );
276 205 : fd_bn254_fp_inv( t1, t0 );
277 205 : fd_bn254_fp_mul( &r->el[0], &a->el[0], t1 );
278 205 : fd_bn254_fp_mul( &r->el[1], &a->el[1], t1 );
279 205 : fd_bn254_fp_neg( &r->el[1], &r->el[1] );
280 205 : return r;
281 205 : }
282 :
283 : /* fd_bn254_fp2_pow computes r = a ^ b in Fp2. */
284 : fd_bn254_fp2_t *
285 : fd_bn254_fp2_pow( fd_bn254_fp2_t * restrict r,
286 : fd_bn254_fp2_t const * a,
287 194 : fd_uint256_t const * b ) {
288 194 : fd_bn254_fp2_set_one( r );
289 :
290 194 : int i = 255;
291 879 : while( !fd_uint256_bit( b, i) ) i--;
292 44863 : for( ; i>=0; i--) {
293 44669 : fd_bn254_fp2_sqr( r, r );
294 44669 : if( fd_uint256_bit( b, i ) ) {
295 20087 : fd_bn254_fp2_mul( r, r, a );
296 20087 : }
297 44669 : }
298 194 : return r;
299 194 : }
300 :
301 : /* fd_bn254_fp2_sqrt computes r = sqrt(a) in Fp2.
302 : https://eprint.iacr.org/2012/685, Alg. 9.
303 : Note: r is one of the two sqrt, the other is -r. This function
304 : can return either the positive or negative one, no assumptions/promises.
305 : Returns r if a is a square (sqrt exists), or NULL otherwise. */
306 : static inline fd_bn254_fp2_t *
307 : fd_bn254_fp2_sqrt( fd_bn254_fp2_t * r,
308 103 : fd_bn254_fp2_t const * a ) {
309 103 : fd_bn254_fp2_t a0[1], a1[1], alpha[1], x0[1];
310 :
311 103 : fd_bn254_fp2_pow( a1, a, fd_bn254_const_sqrt_exp );
312 :
313 103 : fd_bn254_fp2_sqr( alpha, a1 );
314 103 : fd_bn254_fp2_mul( alpha, alpha, a );
315 :
316 103 : fd_bn254_fp2_conj( a0, alpha );
317 103 : fd_bn254_fp2_mul( a0, a0, alpha );
318 :
319 103 : if( FD_UNLIKELY( fd_bn254_fp2_is_minus_one( a0 ) ) ) {
320 12 : return NULL;
321 12 : }
322 :
323 91 : fd_bn254_fp2_mul( x0, a1, a );
324 91 : if( fd_bn254_fp2_is_minus_one( alpha ) ) {
325 : /* COV: I don't know if there's a point that hits this condition.
326 : sqrt(-1) hits this, but doesn't correspond to a valid point.
327 : Tried with some other possible values, nothing corresponds to a point. */
328 0 : fd_bn254_fp2_mul_by_i( r, x0 );
329 91 : } else {
330 91 : fd_bn254_fp2_set_one( a1 );
331 91 : fd_bn254_fp2_add( a0, alpha, a1 ); /* 1 + alpha */
332 91 : fd_bn254_fp2_pow( a1, a0, fd_bn254_const_p_minus_one_half ); /* b */
333 91 : fd_bn254_fp2_mul( r, a1, x0 );
334 91 : }
335 91 : return r;
336 103 : }
337 :
338 : /* fd_bn254_fp2_mul_by_xi computes r = a * (9+i) in Fp2.
339 : xi = (9+i) is the const used to build Fp6.
340 : Note: this can probably be optimized (less reductions mod p). */
341 : static inline fd_bn254_fp2_t *
342 : fd_bn254_fp2_mul_by_xi( fd_bn254_fp2_t * r,
343 110829 : fd_bn254_fp2_t const * a ) {
344 : /* xi = 9 + i
345 : r = (9*a0 - a1) + (9*a1 + a0) i */
346 110829 : fd_bn254_fp_t r0[1], r1[1];
347 :
348 110829 : fd_bn254_fp_add( r0, &a->el[0], &a->el[0] );
349 110829 : fd_bn254_fp_add( r0, r0, r0 );
350 110829 : fd_bn254_fp_add( r0, r0, r0 );
351 110829 : fd_bn254_fp_add( r0, r0, &a->el[0] );
352 110829 : fd_bn254_fp_sub( r0, r0, &a->el[1] );
353 :
354 110829 : fd_bn254_fp_add( r1, &a->el[1], &a->el[1] );
355 110829 : fd_bn254_fp_add( r1, r1, r1 );
356 110829 : fd_bn254_fp_add( r1, r1, r1 );
357 110829 : fd_bn254_fp_add( r1, r1, &a->el[1] );
358 110829 : fd_bn254_fp_add( &r->el[1], r1, &a->el[0] );
359 :
360 110829 : fd_bn254_fp_set( &r->el[0], r0 );
361 110829 : return r;
362 110829 : }
363 :
364 : /* Fp6 */
365 :
366 : static inline fd_bn254_fp6_t *
367 : fd_bn254_fp6_set( fd_bn254_fp6_t * r,
368 455 : fd_bn254_fp6_t const * a ) {
369 455 : fd_bn254_fp2_set( &r->el[0], &a->el[0] );
370 455 : fd_bn254_fp2_set( &r->el[1], &a->el[1] );
371 455 : fd_bn254_fp2_set( &r->el[2], &a->el[2] );
372 455 : return r;
373 455 : }
374 :
375 : static inline fd_bn254_fp6_t *
376 : fd_bn254_fp6_neg( fd_bn254_fp6_t * r,
377 546 : fd_bn254_fp6_t const * a ) {
378 546 : fd_bn254_fp2_neg( &r->el[0], &a->el[0] );
379 546 : fd_bn254_fp2_neg( &r->el[1], &a->el[1] );
380 546 : fd_bn254_fp2_neg( &r->el[2], &a->el[2] );
381 546 : return r;
382 546 : }
383 :
384 : static inline fd_bn254_fp6_t *
385 : fd_bn254_fp6_add( fd_bn254_fp6_t * r,
386 : fd_bn254_fp6_t const * a,
387 39740 : fd_bn254_fp6_t const * b ) {
388 39740 : fd_bn254_fp2_add( &r->el[0], &a->el[0], &b->el[0] );
389 39740 : fd_bn254_fp2_add( &r->el[1], &a->el[1], &b->el[1] );
390 39740 : fd_bn254_fp2_add( &r->el[2], &a->el[2], &b->el[2] );
391 39740 : return r;
392 39740 : }
393 :
394 : static inline fd_bn254_fp6_t *
395 : fd_bn254_fp6_sub( fd_bn254_fp6_t * r,
396 : fd_bn254_fp6_t const * a,
397 31894 : fd_bn254_fp6_t const * b ) {
398 31894 : fd_bn254_fp2_sub( &r->el[0], &a->el[0], &b->el[0] );
399 31894 : fd_bn254_fp2_sub( &r->el[1], &a->el[1], &b->el[1] );
400 31894 : fd_bn254_fp2_sub( &r->el[2], &a->el[2], &b->el[2] );
401 31894 : return r;
402 31894 : }
403 :
404 : static inline fd_bn254_fp6_t *
405 : fd_bn254_fp6_mul_by_gamma( fd_bn254_fp6_t * r,
406 19618 : fd_bn254_fp6_t const * a ) {
407 : /* https://eprint.iacr.org/2010/354, Alg. 12 */
408 19618 : fd_bn254_fp2_t t[1];
409 19618 : fd_bn254_fp2_mul_by_xi( t, &a->el[2] );
410 19618 : fd_bn254_fp2_set( &r->el[2], &a->el[1] );
411 19618 : fd_bn254_fp2_set( &r->el[1], &a->el[0] );
412 19618 : fd_bn254_fp2_set( &r->el[0], t );
413 19618 : return r;
414 19618 : }
415 :
416 : static inline fd_bn254_fp6_t *
417 : fd_bn254_fp6_mul( fd_bn254_fp6_t * r,
418 : fd_bn254_fp6_t const * a,
419 23323 : fd_bn254_fp6_t const * b ) {
420 : /* https://eprint.iacr.org/2010/354, Alg. 13 */
421 23323 : fd_bn254_fp2_t const * a0 = &a->el[0];
422 23323 : fd_bn254_fp2_t const * a1 = &a->el[1];
423 23323 : fd_bn254_fp2_t const * a2 = &a->el[2];
424 23323 : fd_bn254_fp2_t const * b0 = &b->el[0];
425 23323 : fd_bn254_fp2_t const * b1 = &b->el[1];
426 23323 : fd_bn254_fp2_t const * b2 = &b->el[2];
427 23323 : fd_bn254_fp2_t a0b0[1], a1b1[1], a2b2[1];
428 23323 : fd_bn254_fp2_t sa[1], sb[1];
429 23323 : fd_bn254_fp2_t r0[1], r1[1], r2[1];
430 :
431 23323 : fd_bn254_fp2_mul( a0b0, a0, b0 );
432 23323 : fd_bn254_fp2_mul( a1b1, a1, b1 );
433 23323 : fd_bn254_fp2_mul( a2b2, a2, b2 );
434 :
435 23323 : fd_bn254_fp2_add( sa, a1, a2 );
436 23323 : fd_bn254_fp2_add( sb, b1, b2 );
437 23323 : fd_bn254_fp2_mul( r0, sa, sb );
438 23323 : fd_bn254_fp2_sub( r0, r0, a1b1 );
439 23323 : fd_bn254_fp2_sub( r0, r0, a2b2 );
440 23323 : fd_bn254_fp2_mul_by_xi( r0, r0 );
441 23323 : fd_bn254_fp2_add( r0, r0, a0b0 );
442 :
443 23323 : fd_bn254_fp2_add( sa, a0, a2 );
444 23323 : fd_bn254_fp2_add( sb, b0, b2 );
445 23323 : fd_bn254_fp2_mul( r2, sa, sb );
446 23323 : fd_bn254_fp2_sub( r2, r2, a0b0 );
447 23323 : fd_bn254_fp2_sub( r2, r2, a2b2 );
448 23323 : fd_bn254_fp2_add( r2, r2, a1b1 );
449 :
450 23323 : fd_bn254_fp2_add( sa, a0, a1 );
451 23323 : fd_bn254_fp2_add( sb, b0, b1 );
452 23323 : fd_bn254_fp2_mul( r1, sa, sb );
453 23323 : fd_bn254_fp2_sub( r1, r1, a0b0 );
454 23323 : fd_bn254_fp2_sub( r1, r1, a1b1 );
455 23323 : fd_bn254_fp2_mul_by_xi( a2b2, a2b2 );
456 23323 : fd_bn254_fp2_add( r1, r1, a2b2 );
457 :
458 23323 : fd_bn254_fp2_set( &r->el[0], r0 );
459 23323 : fd_bn254_fp2_set( &r->el[1], r1 );
460 23323 : fd_bn254_fp2_set( &r->el[2], r2 );
461 23323 : return r;
462 23323 : }
463 :
464 : static inline fd_bn254_fp6_t *
465 : fd_bn254_fp6_sqr( fd_bn254_fp6_t * r,
466 181 : fd_bn254_fp6_t const * a ) {
467 : /* https://eprint.iacr.org/2010/354, Alg. 16 */
468 181 : fd_bn254_fp2_t const * a0 = &a->el[0];
469 181 : fd_bn254_fp2_t const * a1 = &a->el[1];
470 181 : fd_bn254_fp2_t const * a2 = &a->el[2];
471 181 : fd_bn254_fp2_t c0[1], c1[1], c2[1];
472 181 : fd_bn254_fp2_t c3[1], c4[1], c5[1];
473 :
474 181 : fd_bn254_fp2_mul( c4, a0, a1 );
475 181 : fd_bn254_fp2_add( c4, c4, c4 );
476 181 : fd_bn254_fp2_sqr( c5, a2 );
477 :
478 181 : fd_bn254_fp2_sub( c2, c4, c5 );
479 181 : fd_bn254_fp2_mul_by_xi( c5, c5 );
480 181 : fd_bn254_fp2_add( c1, c4, c5 );
481 :
482 181 : fd_bn254_fp2_sqr( c3, a0 );
483 181 : fd_bn254_fp2_sub( c4, a0, a1 );
484 181 : fd_bn254_fp2_add( c4, c4, a2 );
485 :
486 181 : fd_bn254_fp2_mul( c5, a1, a2 );
487 181 : fd_bn254_fp2_add( c5, c5, c5 );
488 181 : fd_bn254_fp2_sqr( c4, c4 );
489 :
490 181 : fd_bn254_fp2_add( c2, c2, c4 );
491 181 : fd_bn254_fp2_add( c2, c2, c5 );
492 181 : fd_bn254_fp2_sub( c2, c2, c3 );
493 181 : fd_bn254_fp2_mul_by_xi( c5, c5 );
494 181 : fd_bn254_fp2_add( c0, c3, c5 );
495 :
496 181 : fd_bn254_fp2_set( &r->el[0], c0 );
497 181 : fd_bn254_fp2_set( &r->el[1], c1 );
498 181 : fd_bn254_fp2_set( &r->el[2], c2 );
499 181 : return r;
500 181 : }
501 :
502 : static inline fd_bn254_fp6_t *
503 : fd_bn254_fp6_inv( fd_bn254_fp6_t * r,
504 91 : fd_bn254_fp6_t const * a ) {
505 : /* https://eprint.iacr.org/2010/354, Alg. 17 */
506 91 : fd_bn254_fp2_t t[6];
507 91 : fd_bn254_fp2_sqr( &t[0], &a->el[0] );
508 91 : fd_bn254_fp2_sqr( &t[1], &a->el[1] );
509 91 : fd_bn254_fp2_sqr( &t[2], &a->el[2] );
510 91 : fd_bn254_fp2_mul( &t[3], &a->el[0], &a->el[1] );
511 91 : fd_bn254_fp2_mul( &t[4], &a->el[0], &a->el[2] );
512 91 : fd_bn254_fp2_mul( &t[5], &a->el[1], &a->el[2] );
513 : /* t0 := c0 = t0 - xi * t5 */
514 91 : fd_bn254_fp2_mul_by_xi( &t[5], &t[5] );
515 91 : fd_bn254_fp2_sub( &t[0], &t[0], &t[5] );
516 : /* t2 := c1 = xi * t2 - t3 */
517 91 : fd_bn254_fp2_mul_by_xi( &t[2], &t[2] );
518 91 : fd_bn254_fp2_sub( &t[2], &t[2], &t[3] );
519 : /* t1 := c2 = t1 - t4 (note: paper says t1*t4, but that's a misprint) */
520 91 : fd_bn254_fp2_sub( &t[1], &t[1], &t[4] );
521 : /* t3 := t6 = a0 * c0 */
522 91 : fd_bn254_fp2_mul( &t[3], &a->el[0], &t[0] );
523 : /* t3 := t6 = t6 + (xi * a2 * c1 =: t4) */
524 91 : fd_bn254_fp2_mul( &t[4], &a->el[2], &t[2] );
525 91 : fd_bn254_fp2_mul_by_xi( &t[4], &t[4] );
526 91 : fd_bn254_fp2_add( &t[3], &t[3], &t[4] );
527 : /* t3 := t6 = t6 + (xi * a2 * c1 =: t4) */
528 91 : fd_bn254_fp2_mul( &t[5], &a->el[1], &t[1] );
529 91 : fd_bn254_fp2_mul_by_xi( &t[5], &t[5] );
530 91 : fd_bn254_fp2_add( &t[3], &t[3], &t[5] );
531 : /* t4 := t6^-1 */
532 91 : fd_bn254_fp2_inv( &t[4], &t[3] );
533 :
534 91 : fd_bn254_fp2_mul( &r->el[0], &t[0], &t[4] );
535 91 : fd_bn254_fp2_mul( &r->el[1], &t[2], &t[4] );
536 91 : fd_bn254_fp2_mul( &r->el[2], &t[1], &t[4] );
537 91 : return r;
538 91 : }
539 :
540 : /* Fp12 */
541 :
542 : static inline fd_bn254_fp12_t *
543 : fd_bn254_fp12_conj( fd_bn254_fp12_t * r,
544 455 : fd_bn254_fp12_t const * a ) {
545 455 : fd_bn254_fp6_set( &r->el[0], &a->el[0] );
546 455 : fd_bn254_fp6_neg( &r->el[1], &a->el[1] );
547 455 : return r;
548 455 : }
549 :
550 : /*
551 : static inline fd_bn254_fp12_t *
552 : fd_bn254_fp12_add( fd_bn254_fp12_t * r,
553 : fd_bn254_fp12_t const * a,
554 : fd_bn254_fp12_t const * b ) {
555 : fd_bn254_fp6_add( &r->el[0], &a->el[0], &b->el[0] );
556 : fd_bn254_fp6_add( &r->el[1], &a->el[1], &b->el[1] );
557 : return r;
558 : }
559 :
560 : static inline fd_bn254_fp12_t *
561 : fd_bn254_fp12_sub( fd_bn254_fp12_t * r,
562 : fd_bn254_fp12_t const * a,
563 : fd_bn254_fp12_t const * b ) {
564 : fd_bn254_fp6_sub( &r->el[0], &a->el[0], &b->el[0] );
565 : fd_bn254_fp6_sub( &r->el[1], &a->el[1], &b->el[1] );
566 : return r;
567 : }
568 : */
569 :
570 : /* fd_bn254_fp6_mul_by_fp2 computes r = a * (b, 0, 0) in Fp6.
571 : Simply (a0*b, a1*b, a2*b).
572 : Cost: 3 Fp2_mul (vs 6 for full Fp6_mul). */
573 : static inline fd_bn254_fp6_t *
574 : fd_bn254_fp6_mul_by_fp2( fd_bn254_fp6_t * r,
575 : fd_bn254_fp6_t const * a,
576 7300 : fd_bn254_fp2_t const * b ) {
577 7300 : fd_bn254_fp2_mul( &r->el[0], &a->el[0], b );
578 7300 : fd_bn254_fp2_mul( &r->el[1], &a->el[1], b );
579 7300 : fd_bn254_fp2_mul( &r->el[2], &a->el[2], b );
580 7300 : return r;
581 7300 : }
582 :
583 : /* fd_bn254_fp6_mul_by_01 computes r = a * (b0, b1, 0) in Fp6.
584 : Karatsuba with b2=0.
585 : Cost: 5 Fp2_mul (vs 6 for full Fp6_mul). */
586 : static inline fd_bn254_fp6_t *
587 : fd_bn254_fp6_mul_by_01( fd_bn254_fp6_t * r,
588 : fd_bn254_fp6_t const * a,
589 : fd_bn254_fp2_t const * b0,
590 14549 : fd_bn254_fp2_t const * b1 ) {
591 14549 : fd_bn254_fp2_t const * a0 = &a->el[0];
592 14549 : fd_bn254_fp2_t const * a1 = &a->el[1];
593 14549 : fd_bn254_fp2_t const * a2 = &a->el[2];
594 14549 : fd_bn254_fp2_t a0b0[1], a1b1[1];
595 14549 : fd_bn254_fp2_t sa[1], sb[1];
596 14549 : fd_bn254_fp2_t r0[1], r1[1], r2[1];
597 :
598 14549 : fd_bn254_fp2_mul( a0b0, a0, b0 );
599 14549 : fd_bn254_fp2_mul( a1b1, a1, b1 );
600 :
601 : /* r0 = a0b0 + xi * a2*b1 */
602 14549 : fd_bn254_fp2_mul( r0, a2, b1 );
603 14549 : fd_bn254_fp2_mul_by_xi( r0, r0 );
604 14549 : fd_bn254_fp2_add( r0, r0, a0b0 );
605 :
606 : /* r1 = (a0+a1)*(b0+b1) - a0b0 - a1b1 */
607 14549 : fd_bn254_fp2_add( sa, a0, a1 );
608 14549 : fd_bn254_fp2_add( sb, b0, b1 );
609 14549 : fd_bn254_fp2_mul( r1, sa, sb );
610 14549 : fd_bn254_fp2_sub( r1, r1, a0b0 );
611 14549 : fd_bn254_fp2_sub( r1, r1, a1b1 );
612 :
613 : /* r2 = (a0+a2)*b0 - a0b0 + a1b1 */
614 14549 : fd_bn254_fp2_add( sa, a0, a2 );
615 14549 : fd_bn254_fp2_mul( r2, sa, b0 );
616 14549 : fd_bn254_fp2_sub( r2, r2, a0b0 );
617 14549 : fd_bn254_fp2_add( r2, r2, a1b1 );
618 :
619 14549 : fd_bn254_fp2_set( &r->el[0], r0 );
620 14549 : fd_bn254_fp2_set( &r->el[1], r1 );
621 14549 : fd_bn254_fp2_set( &r->el[2], r2 );
622 14549 : return r;
623 14549 : }
624 :
625 : /* fd_bn254_fp12_mul_sparse computes r = a * b in Fp12,
626 : where b has the "034" sparse pattern:
627 : b.el[0] = (c0, 0, 0)
628 : b.el[1] = (c3, c4, 0)
629 : This is the pattern produced by line evaluation functions.
630 : Cost: 13 Fp2_mul (vs 18 for full Fp12_mul). */
631 : static inline fd_bn254_fp12_t *
632 : fd_bn254_fp12_mul_sparse( fd_bn254_fp12_t * r,
633 : fd_bn254_fp12_t const * a,
634 7300 : fd_bn254_fp12_t const * b ) {
635 7300 : fd_bn254_fp2_t const * c0 = &b->el[0].el[0];
636 7300 : fd_bn254_fp2_t const * c3 = &b->el[1].el[0];
637 7300 : fd_bn254_fp2_t const * c4 = &b->el[1].el[1];
638 7300 : fd_bn254_fp6_t a0b0[1], a1b1[1], sa[1];
639 7300 : fd_bn254_fp2_t sc0[1];
640 :
641 : /* a0*b0 = a.el[0] * (c0, 0, 0) : 3 Fp2_mul */
642 7300 : fd_bn254_fp6_mul_by_fp2( a0b0, &a->el[0], c0 );
643 :
644 : /* a1*b1 = a.el[1] * (c3, c4, 0) : 5 Fp2_mul */
645 7300 : fd_bn254_fp6_mul_by_01( a1b1, &a->el[1], c3, c4 );
646 :
647 : /* r1 = (a0+a1) * (c0+c3, c4, 0) - a0b0 - a1b1 : 5 Fp2_mul */
648 7300 : fd_bn254_fp6_add( sa, &a->el[0], &a->el[1] );
649 7300 : fd_bn254_fp2_add( sc0, c0, c3 );
650 7300 : fd_bn254_fp6_mul_by_01( &r->el[1], sa, sc0, c4 );
651 7300 : fd_bn254_fp6_sub( &r->el[1], &r->el[1], a0b0 );
652 7300 : fd_bn254_fp6_sub( &r->el[1], &r->el[1], a1b1 );
653 :
654 : /* r0 = a0b0 + gamma * a1b1 */
655 7300 : fd_bn254_fp6_mul_by_gamma( a1b1, a1b1 );
656 7300 : fd_bn254_fp6_add( &r->el[0], a0b0, a1b1 );
657 7300 : return r;
658 7300 : }
659 :
660 : fd_bn254_fp12_t *
661 : fd_bn254_fp12_mul( fd_bn254_fp12_t * r,
662 : fd_bn254_fp12_t const * a,
663 5728 : fd_bn254_fp12_t const * b ) {
664 : /* https://eprint.iacr.org/2010/354, Alg. 20 */
665 5728 : fd_bn254_fp6_t const * a0 = &a->el[0];
666 5728 : fd_bn254_fp6_t const * a1 = &a->el[1];
667 5728 : fd_bn254_fp6_t const * b0 = &b->el[0];
668 5728 : fd_bn254_fp6_t const * b1 = &b->el[1];
669 5728 : fd_bn254_fp6_t * r0 = &r->el[0];
670 5728 : fd_bn254_fp6_t * r1 = &r->el[1];
671 5728 : fd_bn254_fp6_t a0b0[1], a1b1[1], sa[1], sb[1];
672 :
673 5728 : fd_bn254_fp6_add( sa, a0, a1 );
674 5728 : fd_bn254_fp6_add( sb, b0, b1 );
675 :
676 5728 : fd_bn254_fp6_mul( a0b0, a0, b0 );
677 5728 : fd_bn254_fp6_mul( a1b1, a1, b1 );
678 5728 : fd_bn254_fp6_mul( r1, sa, sb );
679 :
680 5728 : fd_bn254_fp6_sub( r1, r1, a0b0 );
681 5728 : fd_bn254_fp6_sub( r1, r1, a1b1 );
682 :
683 5728 : fd_bn254_fp6_mul_by_gamma( a1b1, a1b1 );
684 5728 : fd_bn254_fp6_add( r0, a0b0, a1b1 );
685 5728 : return r;
686 5728 : }
687 :
688 : static inline fd_bn254_fp12_t *
689 : fd_bn254_fp12_sqr( fd_bn254_fp12_t * r,
690 3308 : fd_bn254_fp12_t const * a ) {
691 : /* https://eprint.iacr.org/2010/354, Alg. 22. */
692 3308 : fd_bn254_fp6_t c0[1], c2[1], c3[1];
693 3308 : fd_bn254_fp6_sub( c0, &a->el[0], &a->el[1] );
694 3308 : fd_bn254_fp6_mul_by_gamma( c3, &a->el[1] );
695 3308 : fd_bn254_fp6_sub( c3, &a->el[0], c3 );
696 3308 : fd_bn254_fp6_mul( c2, &a->el[0], &a->el[1] );
697 3308 : fd_bn254_fp6_mul( c0, c0, c3 );
698 3308 : fd_bn254_fp6_add( c0, c0, c2 );
699 3308 : fd_bn254_fp6_add( &r->el[1], c2, c2 );
700 3308 : fd_bn254_fp6_mul_by_gamma( &r->el[0], c2 );
701 3308 : fd_bn254_fp6_add( &r->el[0], &r->el[0], c0 );
702 3308 : return r;
703 3308 : }
704 :
705 : static inline fd_bn254_fp12_t *
706 : fd_bn254_fp12_sqr_fast( fd_bn254_fp12_t * r,
707 16752 : fd_bn254_fp12_t const * a ) {
708 : /* Cyclotomic sqr, https://eprint.iacr.org/2009/565, Sec. 3.2.
709 : Variant of https://eprint.iacr.org/2010/354, Alg. 24.
710 : This works when a^(p^6+1)=1, e.g. during pairing final exp. */
711 16752 : fd_bn254_fp2_t t[9];
712 :
713 16752 : fd_bn254_fp2_sqr( &t[0], &a->el[1].el[1] );
714 16752 : fd_bn254_fp2_sqr( &t[1], &a->el[0].el[0] );
715 16752 : fd_bn254_fp2_add( &t[6], &a->el[1].el[1], &a->el[0].el[0] );
716 16752 : fd_bn254_fp2_sqr( &t[6], &t[6] );
717 16752 : fd_bn254_fp2_sub( &t[6], &t[6], &t[0] );
718 16752 : fd_bn254_fp2_sub( &t[6], &t[6], &t[1] );
719 :
720 16752 : fd_bn254_fp2_sqr( &t[2], &a->el[0].el[2] );
721 16752 : fd_bn254_fp2_sqr( &t[3], &a->el[1].el[0] );
722 16752 : fd_bn254_fp2_add( &t[7], &a->el[0].el[2], &a->el[1].el[0] );
723 16752 : fd_bn254_fp2_sqr( &t[7], &t[7] );
724 16752 : fd_bn254_fp2_sub( &t[7], &t[7], &t[2] );
725 16752 : fd_bn254_fp2_sub( &t[7], &t[7], &t[3] );
726 :
727 16752 : fd_bn254_fp2_sqr( &t[4], &a->el[1].el[2] );
728 16752 : fd_bn254_fp2_sqr( &t[5], &a->el[0].el[1] );
729 16752 : fd_bn254_fp2_add( &t[8], &a->el[1].el[2], &a->el[0].el[1] );
730 16752 : fd_bn254_fp2_sqr( &t[8], &t[8] );
731 16752 : fd_bn254_fp2_sub( &t[8], &t[8], &t[4] );
732 16752 : fd_bn254_fp2_sub( &t[8], &t[8], &t[5] );
733 16752 : fd_bn254_fp2_mul_by_xi( &t[8], &t[8] );
734 :
735 16752 : fd_bn254_fp2_mul_by_xi( &t[0], &t[0] );
736 16752 : fd_bn254_fp2_add( &t[0], &t[0], &t[1] );
737 16752 : fd_bn254_fp2_mul_by_xi( &t[2], &t[2] );
738 16752 : fd_bn254_fp2_add( &t[2], &t[2], &t[3] );
739 16752 : fd_bn254_fp2_mul_by_xi( &t[4], &t[4] );
740 16752 : fd_bn254_fp2_add( &t[4], &t[4], &t[5] );
741 :
742 16752 : fd_bn254_fp2_sub( &r->el[0].el[0], &t[0], &a->el[0].el[0] );
743 16752 : fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &r->el[0].el[0] );
744 16752 : fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &t[0] );
745 16752 : fd_bn254_fp2_sub( &r->el[0].el[1], &t[2], &a->el[0].el[1] );
746 16752 : fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &r->el[0].el[1] );
747 16752 : fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &t[2] );
748 16752 : fd_bn254_fp2_sub( &r->el[0].el[2], &t[4], &a->el[0].el[2] );
749 16752 : fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &r->el[0].el[2] );
750 16752 : fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &t[4] );
751 :
752 16752 : fd_bn254_fp2_add( &r->el[1].el[0], &t[8], &a->el[1].el[0] );
753 16752 : fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &r->el[1].el[0] );
754 16752 : fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &t[8] );
755 16752 : fd_bn254_fp2_add( &r->el[1].el[1], &t[6], &a->el[1].el[1] );
756 16752 : fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &r->el[1].el[1] );
757 16752 : fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &t[6] );
758 16752 : fd_bn254_fp2_add( &r->el[1].el[2], &t[7], &a->el[1].el[2] );
759 16752 : fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &r->el[1].el[2] );
760 16752 : fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &t[7] );
761 16752 : return r;
762 16752 : }
763 :
764 : fd_bn254_fp12_t *
765 : fd_bn254_fp12_inv( fd_bn254_fp12_t * r,
766 91 : fd_bn254_fp12_t const * a ) {
767 : /* https://eprint.iacr.org/2010/354, Alg. 23 */
768 91 : fd_bn254_fp6_t t0[1], t1[1];
769 91 : fd_bn254_fp6_sqr( t0, &a->el[0] );
770 91 : fd_bn254_fp6_sqr( t1, &a->el[1] );
771 91 : fd_bn254_fp6_mul_by_gamma( t1, t1 );
772 91 : fd_bn254_fp6_sub( t0, t0, t1 );
773 91 : fd_bn254_fp6_inv( t1, t0 );
774 91 : fd_bn254_fp6_mul( &r->el[0], &a->el[0], t1 );
775 91 : fd_bn254_fp6_mul( &r->el[1], &a->el[1], t1 );
776 91 : fd_bn254_fp6_neg( &r->el[1], &r->el[1] );
777 91 : return r;
778 91 : }
779 :
780 : static inline fd_bn254_fp12_t *
781 : fd_bn254_fp12_frob( fd_bn254_fp12_t * r,
782 182 : fd_bn254_fp12_t const * a ) {
783 : /* https://eprint.iacr.org/2010/354, Alg. 28 */
784 182 : fd_bn254_fp2_t t[5];
785 :
786 : /* conj(g0) */
787 182 : fd_bn254_fp2_conj( &r->el[0].el[0], &a->el[0].el[0] );
788 182 : fd_bn254_fp2_conj( &t[0], &a->el[0].el[1] );
789 182 : fd_bn254_fp2_conj( &t[1], &a->el[0].el[2] );
790 182 : fd_bn254_fp2_conj( &t[2], &a->el[1].el[0] );
791 182 : fd_bn254_fp2_conj( &t[3], &a->el[1].el[1] );
792 182 : fd_bn254_fp2_conj( &t[4], &a->el[1].el[2] );
793 :
794 : /* conj(g1) * gamma_1,2 */
795 182 : fd_bn254_fp2_mul( &r->el[0].el[1], &t[0], &fd_bn254_const_frob_gamma1_mont[1] );
796 :
797 : /* conj(g2) * gamma_1,4 */
798 182 : fd_bn254_fp2_mul( &r->el[0].el[2], &t[1], &fd_bn254_const_frob_gamma1_mont[3] );
799 :
800 : /* conj(h0) * gamma_1,1 */
801 182 : fd_bn254_fp2_mul( &r->el[1].el[0], &t[2], &fd_bn254_const_frob_gamma1_mont[0] );
802 :
803 : /* conj(h1) * gamma_1,3 */
804 182 : fd_bn254_fp2_mul( &r->el[1].el[1], &t[3], &fd_bn254_const_frob_gamma1_mont[2] );
805 :
806 : /* conj(h2) * gamma_1,5 */
807 182 : fd_bn254_fp2_mul( &r->el[1].el[2], &t[4], &fd_bn254_const_frob_gamma1_mont[4] );
808 182 : return r;
809 182 : }
810 :
811 : static inline fd_bn254_fp12_t *
812 : fd_bn254_fp12_frob2( fd_bn254_fp12_t * r,
813 273 : fd_bn254_fp12_t const * a ) {
814 : /* https://eprint.iacr.org/2010/354, Alg. 29 */
815 :
816 : /* g0 */
817 273 : fd_bn254_fp2_set( &r->el[0].el[0], &a->el[0].el[0] );
818 :
819 : /* g1 * gamma_2,2 */
820 273 : 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] );
821 273 : 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] );
822 :
823 : /* g2 * gamma_2,4 */
824 273 : 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] );
825 273 : 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] );
826 :
827 : /* h0 * gamma_2,1 */
828 273 : 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] );
829 273 : 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] );
830 :
831 : /* h1 * gamma_2,3 */
832 273 : 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] );
833 273 : 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] );
834 :
835 : /* h2 * gamma_2,5 */
836 273 : 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] );
837 273 : 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] );
838 273 : return r;
839 273 : }
|
