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_be_nm( fd_bn254_fp2_t * r,
73 : uchar const buf[64],
74 : int * is_inf,
75 64596 : int * is_neg ) {
76 : /* validate fp2.el[0] without flags */
77 64596 : if( FD_UNLIKELY( !fd_bn254_fp_frombytes_be_nm( &r->el[0], &buf[32], NULL, NULL ) ) ) {
78 0 : return NULL;
79 0 : }
80 : /* validate fp2.el[1] with flags */
81 64596 : if( FD_UNLIKELY( !fd_bn254_fp_frombytes_be_nm( &r->el[1], &buf[0], is_inf, is_neg ) ) ) {
82 0 : return NULL;
83 0 : }
84 64596 : return r;
85 64596 : }
86 :
87 : static inline uchar *
88 : fd_bn254_fp2_tobytes_be_nm( uchar buf[64],
89 3042 : fd_bn254_fp2_t * const a ) {
90 3042 : fd_bn254_fp_tobytes_be_nm( &buf[ 0], &a->el[1] );
91 3042 : fd_bn254_fp_tobytes_be_nm( &buf[32], &a->el[0] );
92 3042 : return buf;
93 3042 : }
94 :
95 : /* fd_bn254_fp2_is_neg_nm checks wheather x < 0 in Fp2.
96 : Note: x is NON Montgomery.
97 : Returns 1 if x < 0, 0 otherwise. */
98 : static inline int
99 33084 : fd_bn254_fp2_is_neg_nm( fd_bn254_fp2_t * x ) {
100 33084 : if( FD_UNLIKELY( fd_bn254_fp_is_zero( &x->el[1] ) ) ) {
101 0 : return fd_bn254_fp_is_neg_nm( &x->el[0] );
102 0 : }
103 33084 : return fd_bn254_fp_is_neg_nm( &x->el[1] );
104 33084 : }
105 :
106 : /* fd_bn254_fp2_is_minus_one checks wheather a == -1 in Fp2.
107 : Returns 1 if a==-1, 0 otherwise. */
108 : static inline int
109 6084 : fd_bn254_fp2_is_minus_one( fd_bn254_fp2_t const * a ) {
110 6084 : return fd_uint256_eq( &a->el[0], fd_bn254_const_p_minus_one_mont )
111 6084 : && fd_uint256_eq( &a->el[1], fd_bn254_const_zero );
112 6084 : }
113 :
114 : /* fd_bn254_fp2_eq checks wheather a == b in Fp2.
115 : Returns 1 if a == b, 0 otherwise. */
116 : static inline int
117 : fd_bn254_fp2_eq( fd_bn254_fp2_t const * a,
118 22785 : fd_bn254_fp2_t const * b ) {
119 22785 : return fd_bn254_fp_eq( &a->el[0], &b->el[0] )
120 22785 : && fd_bn254_fp_eq( &a->el[1], &b->el[1] );
121 22785 : }
122 :
123 : /* fd_bn254_fp2_set sets r = a. */
124 : static inline fd_bn254_fp2_t *
125 : fd_bn254_fp2_set( fd_bn254_fp2_t * r,
126 1567260 : fd_bn254_fp2_t const * a ) {
127 1567260 : fd_bn254_fp_set( &r->el[0], &a->el[0] );
128 1567260 : fd_bn254_fp_set( &r->el[1], &a->el[1] );
129 1567260 : return r;
130 1567260 : }
131 :
132 : /* fd_bn254_fp2_from_mont sets r = a, coverting into Mongomery form. */
133 : static inline fd_bn254_fp2_t *
134 : fd_bn254_fp2_from_mont( fd_bn254_fp2_t * r,
135 3042 : fd_bn254_fp2_t const * a ) {
136 3042 : fd_bn254_fp_from_mont( &r->el[0], &a->el[0] );
137 3042 : fd_bn254_fp_from_mont( &r->el[1], &a->el[1] );
138 3042 : return r;
139 3042 : }
140 :
141 : /* fd_bn254_fp2_to_mont sets r = a, coverting into NON Mongomery form. */
142 : static inline fd_bn254_fp2_t *
143 : fd_bn254_fp2_to_mont( fd_bn254_fp2_t * r,
144 4512 : fd_bn254_fp2_t const * a ) {
145 4512 : fd_bn254_fp_to_mont( &r->el[0], &a->el[0] );
146 4512 : fd_bn254_fp_to_mont( &r->el[1], &a->el[1] );
147 4512 : return r;
148 4512 : }
149 :
150 : /* fd_bn254_fp2_neg_nm sets r = -x in Fp2.
151 : Note: x is NON Montgomery. */
152 : static inline fd_bn254_fp2_t *
153 : fd_bn254_fp2_neg_nm( fd_bn254_fp2_t * r,
154 27 : fd_bn254_fp2_t const * x ) {
155 27 : fd_bn254_fp_neg_nm( &r->el[0], &x->el[0] );
156 27 : fd_bn254_fp_neg_nm( &r->el[1], &x->el[1] );
157 27 : return r;
158 27 : }
159 :
160 : /* fd_bn254_fp2_neg sets r = -a in Fp2. */
161 : static inline fd_bn254_fp2_t *
162 : fd_bn254_fp2_neg( fd_bn254_fp2_t * r,
163 86580 : fd_bn254_fp2_t const * a ) {
164 86580 : fd_bn254_fp_neg( &r->el[0], &a->el[0] );
165 86580 : fd_bn254_fp_neg( &r->el[1], &a->el[1] );
166 86580 : return r;
167 86580 : }
168 :
169 : /* fd_bn254_fp2_neg sets r = a/2 in Fp2. */
170 : static inline fd_bn254_fp2_t *
171 : fd_bn254_fp2_halve( fd_bn254_fp2_t * r,
172 94080 : fd_bn254_fp2_t const * a ) {
173 94080 : fd_bn254_fp_halve( &r->el[0], &a->el[0] );
174 94080 : fd_bn254_fp_halve( &r->el[1], &a->el[1] );
175 94080 : return r;
176 94080 : }
177 :
178 : /* fd_bn254_fp2_add computes r = a + b in Fp2. */
179 : static inline fd_bn254_fp2_t *
180 : fd_bn254_fp2_add( fd_bn254_fp2_t * r,
181 : fd_bn254_fp2_t const * a,
182 7855092 : fd_bn254_fp2_t const * b ) {
183 7855092 : fd_bn254_fp_add( &r->el[0], &a->el[0], &b->el[0] );
184 7855092 : fd_bn254_fp_add( &r->el[1], &a->el[1], &b->el[1] );
185 7855092 : return r;
186 7855092 : }
187 :
188 : /* fd_bn254_fp2_sub computes r = a - b in Fp2. */
189 : static inline fd_bn254_fp2_t *
190 : fd_bn254_fp2_sub( fd_bn254_fp2_t * r,
191 : fd_bn254_fp2_t const * a,
192 4964067 : fd_bn254_fp2_t const * b ) {
193 4964067 : fd_bn254_fp_sub( &r->el[0], &a->el[0], &b->el[0] );
194 4964067 : fd_bn254_fp_sub( &r->el[1], &a->el[1], &b->el[1] );
195 4964067 : return r;
196 4964067 : }
197 :
198 : /* fd_bn254_fp2_conj computes r = conj(a) in Fp2.
199 : If a = a0 + a1*i, conj(a) = a0 - a1*i. */
200 : static inline fd_bn254_fp2_t *
201 : fd_bn254_fp2_conj( fd_bn254_fp2_t * r,
202 17397 : fd_bn254_fp2_t const * a ) {
203 17397 : fd_bn254_fp_set( &r->el[0], &a->el[0] );
204 17397 : fd_bn254_fp_neg( &r->el[1], &a->el[1] );
205 17397 : return r;
206 17397 : }
207 :
208 : /* fd_bn254_fp2_mul computes r = a * b in Fp2.
209 : Karatsuba mul + reduction given that i^2 = -1.
210 : Note: this can probably be optimized, see for ideas:
211 : https://eprint.iacr.org/2010/354 */
212 : static inline fd_bn254_fp2_t *
213 : fd_bn254_fp2_mul( fd_bn254_fp2_t * r,
214 : fd_bn254_fp2_t const * a,
215 3456465 : fd_bn254_fp2_t const * b ) {
216 3456465 : fd_bn254_fp_t const * a0 = &a->el[0];
217 3456465 : fd_bn254_fp_t const * a1 = &a->el[1];
218 3456465 : fd_bn254_fp_t const * b0 = &b->el[0];
219 3456465 : fd_bn254_fp_t const * b1 = &b->el[1];
220 3456465 : fd_bn254_fp_t * r0 = &r->el[0];
221 3456465 : fd_bn254_fp_t * r1 = &r->el[1];
222 3456465 : fd_bn254_fp_t a0b0[1], a1b1[1], sa[1], sb[1];
223 :
224 3456465 : fd_bn254_fp_add( sa, a0, a1 );
225 3456465 : fd_bn254_fp_add( sb, b0, b1 );
226 :
227 3456465 : fd_bn254_fp_mul( a0b0, a0, b0 );
228 3456465 : fd_bn254_fp_mul( a1b1, a1, b1 );
229 3456465 : fd_bn254_fp_mul( r1, sa, sb );
230 :
231 3456465 : fd_bn254_fp_sub( r0, a0b0, a1b1 ); /* i^2 = -1 */
232 3456465 : fd_bn254_fp_sub( r1, r1, a0b0 );
233 3456465 : fd_bn254_fp_sub( r1, r1, a1b1 );
234 3456465 : return r;
235 3456465 : }
236 :
237 : /* fd_bn254_fp2_mul computes r = a^2 in Fp2.
238 : https://eprint.iacr.org/2010/354, Alg. 3.
239 : This is done with 2mul in Fp, instead of 2sqr+1mul. */
240 : static inline fd_bn254_fp2_t *
241 : fd_bn254_fp2_sqr( fd_bn254_fp2_t * r,
242 3376569 : fd_bn254_fp2_t const * a ) {
243 3376569 : fd_bn254_fp_t p[1], m[1];
244 3376569 : fd_bn254_fp_add( p, &a->el[0], &a->el[1] );
245 3376569 : fd_bn254_fp_sub( m, &a->el[0], &a->el[1] );
246 : /* r1 = 2 a0*a1 */
247 3376569 : fd_bn254_fp_mul( &r->el[1], &a->el[0], &a->el[1] );
248 3376569 : fd_bn254_fp_add( &r->el[1], &r->el[1], &r->el[1] );
249 : /* r0 = (a0-a1)*(a0+a1) */
250 3376569 : fd_bn254_fp_mul( &r->el[0], p, m );
251 3376569 : return r;
252 3376569 : }
253 :
254 : /* fd_bn254_fp2_mul_by_i computes r = a * i in Fp2. */
255 : static inline fd_bn254_fp2_t *
256 : fd_bn254_fp2_mul_by_i( fd_bn254_fp2_t * r,
257 0 : fd_bn254_fp2_t const * a ) {
258 0 : fd_bn254_fp_t t[1];
259 0 : fd_bn254_fp_neg( t, &a->el[1] );
260 0 : fd_bn254_fp_set( &r->el[1], &a->el[0] );
261 0 : fd_bn254_fp_set( &r->el[0], t );
262 0 : return r;
263 0 : }
264 :
265 : /* fd_bn254_fp2_inv computes r = 1 / a in Fp2.
266 : https://eprint.iacr.org/2010/354, Alg. 8. */
267 : static inline fd_bn254_fp2_t *
268 : fd_bn254_fp2_inv( fd_bn254_fp2_t * r,
269 645 : fd_bn254_fp2_t const * a ) {
270 645 : fd_bn254_fp_t t0[1], t1[1];
271 645 : fd_bn254_fp_sqr( t0, &a->el[0] );
272 645 : fd_bn254_fp_sqr( t1, &a->el[1] );
273 645 : fd_bn254_fp_add( t0, t0, t1 );
274 645 : fd_bn254_fp_inv( t1, t0 );
275 645 : fd_bn254_fp_mul( &r->el[0], &a->el[0], t1 );
276 645 : fd_bn254_fp_mul( &r->el[1], &a->el[1], t1 );
277 645 : fd_bn254_fp_neg( &r->el[1], &r->el[1] );
278 645 : return r;
279 645 : }
280 :
281 : /* fd_bn254_fp2_pow computes r = a ^ b in Fp2. */
282 : fd_bn254_fp2_t *
283 : fd_bn254_fp2_pow( fd_bn254_fp2_t * restrict r,
284 : fd_bn254_fp2_t const * a,
285 6084 : fd_uint256_t const * b ) {
286 6084 : fd_bn254_fp2_set_one( r );
287 :
288 6084 : int i = 255;
289 27378 : while( !fd_uint256_bit( b, i) ) i--;
290 1542294 : for( ; i>=0; i--) {
291 1536210 : fd_bn254_fp2_sqr( r, r );
292 1536210 : if( fd_uint256_bit( b, i ) ) {
293 666198 : fd_bn254_fp2_mul( r, r, a );
294 666198 : }
295 1536210 : }
296 6084 : return r;
297 6084 : }
298 :
299 : /* fd_bn254_fp2_sqrt computes r = sqrt(a) in Fp2.
300 : https://eprint.iacr.org/2012/685, Alg. 9.
301 : Note: r is one of the two sqrt, the other is -r. This function
302 : can return either the positive or negative one, no assumptions/promises.
303 : Returns r if a is a square (sqrt exists), or NULL otherwise. */
304 : static inline fd_bn254_fp2_t *
305 : fd_bn254_fp2_sqrt( fd_bn254_fp2_t * r,
306 3042 : fd_bn254_fp2_t const * a ) {
307 3042 : fd_bn254_fp2_t a0[1], a1[1], alpha[1], x0[1];
308 :
309 3042 : fd_bn254_fp2_pow( a1, a, fd_bn254_const_sqrt_exp );
310 :
311 3042 : fd_bn254_fp2_sqr( alpha, a1 );
312 3042 : fd_bn254_fp2_mul( alpha, alpha, a );
313 :
314 3042 : fd_bn254_fp2_conj( a0, alpha );
315 3042 : fd_bn254_fp2_mul( a0, a0, alpha );
316 :
317 3042 : if( FD_UNLIKELY( fd_bn254_fp2_is_minus_one( a0 ) ) ) {
318 0 : return NULL;
319 0 : }
320 :
321 3042 : fd_bn254_fp2_mul( x0, a1, a );
322 3042 : if( fd_bn254_fp2_is_minus_one( alpha ) ) {
323 : /* COV: I don't know if there's a point that hits this condition.
324 : sqrt(-1) hits this, but doesn't correspond to a valid point.
325 : Tried with some other possible values, nothing corresponds to a point. */
326 0 : fd_bn254_fp2_mul_by_i( r, x0 );
327 3042 : } else {
328 3042 : fd_bn254_fp2_set_one( a1 );
329 3042 : fd_bn254_fp2_add( a0, alpha, a1 ); /* 1 + alpha */
330 3042 : fd_bn254_fp2_pow( a1, a0, fd_bn254_const_p_minus_one_half ); /* b */
331 3042 : fd_bn254_fp2_mul( r, a1, x0 );
332 3042 : }
333 3042 : return r;
334 3042 : }
335 :
336 : /* fd_bn254_fp2_mul_by_xi computes r = a * (9+i) in Fp2.
337 : xi = (9+i) is the const used to build Fp6.
338 : Note: this can probably be optimized (less reductions mod p). */
339 : static inline fd_bn254_fp2_t *
340 : fd_bn254_fp2_mul_by_xi( fd_bn254_fp2_t * r,
341 1366932 : fd_bn254_fp2_t const * a ) {
342 : /* xi = 9 + i
343 : r = (9*a0 - a1) + (9*a1 + a0) i */
344 1366932 : fd_bn254_fp_t r0[1], r1[1];
345 :
346 1366932 : fd_bn254_fp_add( r0, &a->el[0], &a->el[0] );
347 1366932 : fd_bn254_fp_add( r0, r0, r0 );
348 1366932 : fd_bn254_fp_add( r0, r0, r0 );
349 1366932 : fd_bn254_fp_add( r0, r0, &a->el[0] );
350 1366932 : fd_bn254_fp_sub( r0, r0, &a->el[1] );
351 :
352 1366932 : fd_bn254_fp_add( r1, &a->el[1], &a->el[1] );
353 1366932 : fd_bn254_fp_add( r1, r1, r1 );
354 1366932 : fd_bn254_fp_add( r1, r1, r1 );
355 1366932 : fd_bn254_fp_add( r1, r1, &a->el[1] );
356 1366932 : fd_bn254_fp_add( &r->el[1], r1, &a->el[0] );
357 :
358 1366932 : fd_bn254_fp_set( &r->el[0], r0 );
359 1366932 : return r;
360 1366932 : }
361 :
362 : /* Fp6 */
363 :
364 : static inline fd_bn254_fp6_t *
365 : fd_bn254_fp6_set( fd_bn254_fp6_t * r,
366 3225 : fd_bn254_fp6_t const * a ) {
367 3225 : fd_bn254_fp2_set( &r->el[0], &a->el[0] );
368 3225 : fd_bn254_fp2_set( &r->el[1], &a->el[1] );
369 3225 : fd_bn254_fp2_set( &r->el[2], &a->el[2] );
370 3225 : return r;
371 3225 : }
372 :
373 : static inline fd_bn254_fp6_t *
374 : fd_bn254_fp6_neg( fd_bn254_fp6_t * r,
375 3870 : fd_bn254_fp6_t const * a ) {
376 3870 : fd_bn254_fp2_neg( &r->el[0], &a->el[0] );
377 3870 : fd_bn254_fp2_neg( &r->el[1], &a->el[1] );
378 3870 : fd_bn254_fp2_neg( &r->el[2], &a->el[2] );
379 3870 : return r;
380 3870 : }
381 :
382 : static inline fd_bn254_fp6_t *
383 : fd_bn254_fp6_add( fd_bn254_fp6_t * r,
384 : fd_bn254_fp6_t const * a,
385 382635 : fd_bn254_fp6_t const * b ) {
386 382635 : fd_bn254_fp2_add( &r->el[0], &a->el[0], &b->el[0] );
387 382635 : fd_bn254_fp2_add( &r->el[1], &a->el[1], &b->el[1] );
388 382635 : fd_bn254_fp2_add( &r->el[2], &a->el[2], &b->el[2] );
389 382635 : return r;
390 382635 : }
391 :
392 : static inline fd_bn254_fp6_t *
393 : fd_bn254_fp6_sub( fd_bn254_fp6_t * r,
394 : fd_bn254_fp6_t const * a,
395 255735 : fd_bn254_fp6_t const * b ) {
396 255735 : fd_bn254_fp2_sub( &r->el[0], &a->el[0], &b->el[0] );
397 255735 : fd_bn254_fp2_sub( &r->el[1], &a->el[1], &b->el[1] );
398 255735 : fd_bn254_fp2_sub( &r->el[2], &a->el[2], &b->el[2] );
399 255735 : return r;
400 255735 : }
401 :
402 : static inline fd_bn254_fp6_t *
403 : fd_bn254_fp6_mul_by_gamma( fd_bn254_fp6_t * r,
404 150078 : fd_bn254_fp6_t const * a ) {
405 : /* https://eprint.iacr.org/2010/354, Alg. 12 */
406 150078 : fd_bn254_fp2_t t[1];
407 150078 : fd_bn254_fp2_mul_by_xi( t, &a->el[2] );
408 150078 : fd_bn254_fp2_set( &r->el[2], &a->el[1] );
409 150078 : fd_bn254_fp2_set( &r->el[1], &a->el[0] );
410 150078 : fd_bn254_fp2_set( &r->el[0], t );
411 150078 : return r;
412 150078 : }
413 :
414 : static inline fd_bn254_fp6_t *
415 : fd_bn254_fp6_mul( fd_bn254_fp6_t * r,
416 : fd_bn254_fp6_t const * a,
417 362037 : fd_bn254_fp6_t const * b ) {
418 : /* https://eprint.iacr.org/2010/354, Alg. 13 */
419 362037 : fd_bn254_fp2_t const * a0 = &a->el[0];
420 362037 : fd_bn254_fp2_t const * a1 = &a->el[1];
421 362037 : fd_bn254_fp2_t const * a2 = &a->el[2];
422 362037 : fd_bn254_fp2_t const * b0 = &b->el[0];
423 362037 : fd_bn254_fp2_t const * b1 = &b->el[1];
424 362037 : fd_bn254_fp2_t const * b2 = &b->el[2];
425 362037 : fd_bn254_fp2_t a0b0[1], a1b1[1], a2b2[1];
426 362037 : fd_bn254_fp2_t sa[1], sb[1];
427 362037 : fd_bn254_fp2_t r0[1], r1[1], r2[1];
428 :
429 362037 : fd_bn254_fp2_mul( a0b0, a0, b0 );
430 362037 : fd_bn254_fp2_mul( a1b1, a1, b1 );
431 362037 : fd_bn254_fp2_mul( a2b2, a2, b2 );
432 :
433 362037 : fd_bn254_fp2_add( sa, a1, a2 );
434 362037 : fd_bn254_fp2_add( sb, b1, b2 );
435 362037 : fd_bn254_fp2_mul( r0, sa, sb );
436 362037 : fd_bn254_fp2_sub( r0, r0, a1b1 );
437 362037 : fd_bn254_fp2_sub( r0, r0, a2b2 );
438 362037 : fd_bn254_fp2_mul_by_xi( r0, r0 );
439 362037 : fd_bn254_fp2_add( r0, r0, a0b0 );
440 :
441 362037 : fd_bn254_fp2_add( sa, a0, a2 );
442 362037 : fd_bn254_fp2_add( sb, b0, b2 );
443 362037 : fd_bn254_fp2_mul( r2, sa, sb );
444 362037 : fd_bn254_fp2_sub( r2, r2, a0b0 );
445 362037 : fd_bn254_fp2_sub( r2, r2, a2b2 );
446 362037 : fd_bn254_fp2_add( r2, r2, a1b1 );
447 :
448 362037 : fd_bn254_fp2_add( sa, a0, a1 );
449 362037 : fd_bn254_fp2_add( sb, b0, b1 );
450 362037 : fd_bn254_fp2_mul( r1, sa, sb );
451 362037 : fd_bn254_fp2_sub( r1, r1, a0b0 );
452 362037 : fd_bn254_fp2_sub( r1, r1, a1b1 );
453 362037 : fd_bn254_fp2_mul_by_xi( a2b2, a2b2 );
454 362037 : fd_bn254_fp2_add( r1, r1, a2b2 );
455 :
456 362037 : fd_bn254_fp2_set( &r->el[0], r0 );
457 362037 : fd_bn254_fp2_set( &r->el[1], r1 );
458 362037 : fd_bn254_fp2_set( &r->el[2], r2 );
459 362037 : return r;
460 362037 : }
461 :
462 : static inline fd_bn254_fp6_t *
463 : fd_bn254_fp6_sqr( fd_bn254_fp6_t * r,
464 1290 : fd_bn254_fp6_t const * a ) {
465 : /* https://eprint.iacr.org/2010/354, Alg. 16 */
466 1290 : fd_bn254_fp2_t const * a0 = &a->el[0];
467 1290 : fd_bn254_fp2_t const * a1 = &a->el[1];
468 1290 : fd_bn254_fp2_t const * a2 = &a->el[2];
469 1290 : fd_bn254_fp2_t c0[1], c1[1], c2[1];
470 1290 : fd_bn254_fp2_t c3[1], c4[1], c5[1];
471 :
472 1290 : fd_bn254_fp2_mul( c4, a0, a1 );
473 1290 : fd_bn254_fp2_add( c4, c4, c4 );
474 1290 : fd_bn254_fp2_sqr( c5, a2 );
475 :
476 1290 : fd_bn254_fp2_sub( c2, c4, c5 );
477 1290 : fd_bn254_fp2_mul_by_xi( c5, c5 );
478 1290 : fd_bn254_fp2_add( c1, c4, c5 );
479 :
480 1290 : fd_bn254_fp2_sqr( c3, a0 );
481 1290 : fd_bn254_fp2_sub( c4, a0, a1 );
482 1290 : fd_bn254_fp2_add( c4, c4, a2 );
483 :
484 1290 : fd_bn254_fp2_mul( c5, a1, a2 );
485 1290 : fd_bn254_fp2_add( c5, c5, c5 );
486 1290 : fd_bn254_fp2_sqr( c4, c4 );
487 :
488 1290 : fd_bn254_fp2_add( c2, c2, c4 );
489 1290 : fd_bn254_fp2_add( c2, c2, c5 );
490 1290 : fd_bn254_fp2_sub( c2, c2, c3 );
491 1290 : fd_bn254_fp2_mul_by_xi( c5, c5 );
492 1290 : fd_bn254_fp2_add( c0, c3, c5 );
493 :
494 1290 : fd_bn254_fp2_set( &r->el[0], c0 );
495 1290 : fd_bn254_fp2_set( &r->el[1], c1 );
496 1290 : fd_bn254_fp2_set( &r->el[2], c2 );
497 1290 : return r;
498 1290 : }
499 :
500 : static inline fd_bn254_fp6_t *
501 : fd_bn254_fp6_inv( fd_bn254_fp6_t * r,
502 645 : fd_bn254_fp6_t const * a ) {
503 : /* https://eprint.iacr.org/2010/354, Alg. 17 */
504 645 : fd_bn254_fp2_t t[6];
505 645 : fd_bn254_fp2_sqr( &t[0], &a->el[0] );
506 645 : fd_bn254_fp2_sqr( &t[1], &a->el[1] );
507 645 : fd_bn254_fp2_sqr( &t[2], &a->el[2] );
508 645 : fd_bn254_fp2_mul( &t[3], &a->el[0], &a->el[1] );
509 645 : fd_bn254_fp2_mul( &t[4], &a->el[0], &a->el[2] );
510 645 : fd_bn254_fp2_mul( &t[5], &a->el[1], &a->el[2] );
511 : /* t0 := c0 = t0 - xi * t5 */
512 645 : fd_bn254_fp2_mul_by_xi( &t[5], &t[5] );
513 645 : fd_bn254_fp2_sub( &t[0], &t[0], &t[5] );
514 : /* t2 := c1 = xi * t2 - t3 */
515 645 : fd_bn254_fp2_mul_by_xi( &t[2], &t[2] );
516 645 : fd_bn254_fp2_sub( &t[2], &t[2], &t[3] );
517 : /* t1 := c2 = t1 - t4 (note: paper says t1*t4, but that's a misprint) */
518 645 : fd_bn254_fp2_sub( &t[1], &t[1], &t[4] );
519 : /* t3 := t6 = a0 * c0 */
520 645 : fd_bn254_fp2_mul( &t[3], &a->el[0], &t[0] );
521 : /* t3 := t6 = t6 + (xi * a2 * c1 =: t4) */
522 645 : fd_bn254_fp2_mul( &t[4], &a->el[2], &t[2] );
523 645 : fd_bn254_fp2_mul_by_xi( &t[4], &t[4] );
524 645 : fd_bn254_fp2_add( &t[3], &t[3], &t[4] );
525 : /* t3 := t6 = t6 + (xi * a2 * c1 =: t4) */
526 645 : fd_bn254_fp2_mul( &t[5], &a->el[1], &t[1] );
527 645 : fd_bn254_fp2_mul_by_xi( &t[5], &t[5] );
528 645 : fd_bn254_fp2_add( &t[3], &t[3], &t[5] );
529 : /* t4 := t6^-1 */
530 645 : fd_bn254_fp2_inv( &t[4], &t[3] );
531 :
532 645 : fd_bn254_fp2_mul( &r->el[0], &t[0], &t[4] );
533 645 : fd_bn254_fp2_mul( &r->el[1], &t[2], &t[4] );
534 645 : fd_bn254_fp2_mul( &r->el[2], &t[1], &t[4] );
535 645 : return r;
536 645 : }
537 :
538 : /* Fp12 */
539 :
540 : static inline fd_bn254_fp12_t *
541 : fd_bn254_fp12_conj( fd_bn254_fp12_t * r,
542 3225 : fd_bn254_fp12_t const * a ) {
543 3225 : fd_bn254_fp6_set( &r->el[0], &a->el[0] );
544 3225 : fd_bn254_fp6_neg( &r->el[1], &a->el[1] );
545 3225 : return r;
546 3225 : }
547 :
548 : /*
549 : static inline fd_bn254_fp12_t *
550 : fd_bn254_fp12_add( fd_bn254_fp12_t * r,
551 : fd_bn254_fp12_t const * a,
552 : fd_bn254_fp12_t const * b ) {
553 : fd_bn254_fp6_add( &r->el[0], &a->el[0], &b->el[0] );
554 : fd_bn254_fp6_add( &r->el[1], &a->el[1], &b->el[1] );
555 : return r;
556 : }
557 :
558 : static inline fd_bn254_fp12_t *
559 : fd_bn254_fp12_sub( fd_bn254_fp12_t * r,
560 : fd_bn254_fp12_t const * a,
561 : fd_bn254_fp12_t const * b ) {
562 : fd_bn254_fp6_sub( &r->el[0], &a->el[0], &b->el[0] );
563 : fd_bn254_fp6_sub( &r->el[1], &a->el[1], &b->el[1] );
564 : return r;
565 : }
566 : */
567 :
568 : fd_bn254_fp12_t *
569 : fd_bn254_fp12_mul( fd_bn254_fp12_t * r,
570 : fd_bn254_fp12_t const * a,
571 105657 : fd_bn254_fp12_t const * b ) {
572 : /* https://eprint.iacr.org/2010/354, Alg. 20 */
573 105657 : fd_bn254_fp6_t const * a0 = &a->el[0];
574 105657 : fd_bn254_fp6_t const * a1 = &a->el[1];
575 105657 : fd_bn254_fp6_t const * b0 = &b->el[0];
576 105657 : fd_bn254_fp6_t const * b1 = &b->el[1];
577 105657 : fd_bn254_fp6_t * r0 = &r->el[0];
578 105657 : fd_bn254_fp6_t * r1 = &r->el[1];
579 105657 : fd_bn254_fp6_t a0b0[1], a1b1[1], sa[1], sb[1];
580 :
581 105657 : fd_bn254_fp6_add( sa, a0, a1 );
582 105657 : fd_bn254_fp6_add( sb, b0, b1 );
583 :
584 105657 : fd_bn254_fp6_mul( a0b0, a0, b0 );
585 105657 : fd_bn254_fp6_mul( a1b1, a1, b1 );
586 105657 : fd_bn254_fp6_mul( r1, sa, sb );
587 :
588 105657 : fd_bn254_fp6_sub( r1, r1, a0b0 );
589 105657 : fd_bn254_fp6_sub( r1, r1, a1b1 );
590 :
591 105657 : fd_bn254_fp6_mul_by_gamma( a1b1, a1b1 );
592 105657 : fd_bn254_fp6_add( r0, a0b0, a1b1 );
593 105657 : return r;
594 105657 : }
595 :
596 : static inline fd_bn254_fp12_t *
597 : fd_bn254_fp12_sqr( fd_bn254_fp12_t * r,
598 21888 : fd_bn254_fp12_t const * a ) {
599 : /* https://eprint.iacr.org/2010/354, Alg. 22. */
600 21888 : fd_bn254_fp6_t c0[1], c2[1], c3[1];
601 21888 : fd_bn254_fp6_sub( c0, &a->el[0], &a->el[1] );
602 21888 : fd_bn254_fp6_mul_by_gamma( c3, &a->el[1] );
603 21888 : fd_bn254_fp6_sub( c3, &a->el[0], c3 );
604 21888 : fd_bn254_fp6_mul( c2, &a->el[0], &a->el[1] );
605 21888 : fd_bn254_fp6_mul( c0, c0, c3 );
606 21888 : fd_bn254_fp6_add( c0, c0, c2 );
607 21888 : fd_bn254_fp6_add( &r->el[1], c2, c2 );
608 21888 : fd_bn254_fp6_mul_by_gamma( &r->el[0], c2 );
609 21888 : fd_bn254_fp6_add( &r->el[0], &r->el[0], c0 );
610 21888 : return r;
611 21888 : }
612 :
613 : static inline fd_bn254_fp12_t *
614 : fd_bn254_fp12_sqr_fast( fd_bn254_fp12_t * r,
615 121905 : fd_bn254_fp12_t const * a ) {
616 : /* Cyclotomic sqr, https://eprint.iacr.org/2009/565, Sec. 3.2.
617 : Variant of https://eprint.iacr.org/2010/354, Alg. 24.
618 : This works when a^(p^6+1)=1, e.g. during pairing final exp. */
619 121905 : fd_bn254_fp2_t t[9];
620 :
621 121905 : fd_bn254_fp2_sqr( &t[0], &a->el[1].el[1] );
622 121905 : fd_bn254_fp2_sqr( &t[1], &a->el[0].el[0] );
623 121905 : fd_bn254_fp2_add( &t[6], &a->el[1].el[1], &a->el[0].el[0] );
624 121905 : fd_bn254_fp2_sqr( &t[6], &t[6] );
625 121905 : fd_bn254_fp2_sub( &t[6], &t[6], &t[0] );
626 121905 : fd_bn254_fp2_sub( &t[6], &t[6], &t[1] );
627 :
628 121905 : fd_bn254_fp2_sqr( &t[2], &a->el[0].el[2] );
629 121905 : fd_bn254_fp2_sqr( &t[3], &a->el[1].el[0] );
630 121905 : fd_bn254_fp2_add( &t[7], &a->el[0].el[2], &a->el[1].el[0] );
631 121905 : fd_bn254_fp2_sqr( &t[7], &t[7] );
632 121905 : fd_bn254_fp2_sub( &t[7], &t[7], &t[2] );
633 121905 : fd_bn254_fp2_sub( &t[7], &t[7], &t[3] );
634 :
635 121905 : fd_bn254_fp2_sqr( &t[4], &a->el[1].el[2] );
636 121905 : fd_bn254_fp2_sqr( &t[5], &a->el[0].el[1] );
637 121905 : fd_bn254_fp2_add( &t[8], &a->el[1].el[2], &a->el[0].el[1] );
638 121905 : fd_bn254_fp2_sqr( &t[8], &t[8] );
639 121905 : fd_bn254_fp2_sub( &t[8], &t[8], &t[4] );
640 121905 : fd_bn254_fp2_sub( &t[8], &t[8], &t[5] );
641 121905 : fd_bn254_fp2_mul_by_xi( &t[8], &t[8] );
642 :
643 121905 : fd_bn254_fp2_mul_by_xi( &t[0], &t[0] );
644 121905 : fd_bn254_fp2_add( &t[0], &t[0], &t[1] );
645 121905 : fd_bn254_fp2_mul_by_xi( &t[2], &t[2] );
646 121905 : fd_bn254_fp2_add( &t[2], &t[2], &t[3] );
647 121905 : fd_bn254_fp2_mul_by_xi( &t[4], &t[4] );
648 121905 : fd_bn254_fp2_add( &t[4], &t[4], &t[5] );
649 :
650 121905 : fd_bn254_fp2_sub( &r->el[0].el[0], &t[0], &a->el[0].el[0] );
651 121905 : fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &r->el[0].el[0] );
652 121905 : fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &t[0] );
653 121905 : fd_bn254_fp2_sub( &r->el[0].el[1], &t[2], &a->el[0].el[1] );
654 121905 : fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &r->el[0].el[1] );
655 121905 : fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &t[2] );
656 121905 : fd_bn254_fp2_sub( &r->el[0].el[2], &t[4], &a->el[0].el[2] );
657 121905 : fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &r->el[0].el[2] );
658 121905 : fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &t[4] );
659 :
660 121905 : fd_bn254_fp2_add( &r->el[1].el[0], &t[8], &a->el[1].el[0] );
661 121905 : fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &r->el[1].el[0] );
662 121905 : fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &t[8] );
663 121905 : fd_bn254_fp2_add( &r->el[1].el[1], &t[6], &a->el[1].el[1] );
664 121905 : fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &r->el[1].el[1] );
665 121905 : fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &t[6] );
666 121905 : fd_bn254_fp2_add( &r->el[1].el[2], &t[7], &a->el[1].el[2] );
667 121905 : fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &r->el[1].el[2] );
668 121905 : fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &t[7] );
669 121905 : return r;
670 121905 : }
671 :
672 : fd_bn254_fp12_t *
673 : fd_bn254_fp12_inv( fd_bn254_fp12_t * r,
674 645 : fd_bn254_fp12_t const * a ) {
675 : /* https://eprint.iacr.org/2010/354, Alg. 23 */
676 645 : fd_bn254_fp6_t t0[1], t1[1];
677 645 : fd_bn254_fp6_sqr( t0, &a->el[0] );
678 645 : fd_bn254_fp6_sqr( t1, &a->el[1] );
679 645 : fd_bn254_fp6_mul_by_gamma( t1, t1 );
680 645 : fd_bn254_fp6_sub( t0, t0, t1 );
681 645 : fd_bn254_fp6_inv( t1, t0 );
682 645 : fd_bn254_fp6_mul( &r->el[0], &a->el[0], t1 );
683 645 : fd_bn254_fp6_mul( &r->el[1], &a->el[1], t1 );
684 645 : fd_bn254_fp6_neg( &r->el[1], &r->el[1] );
685 645 : return r;
686 645 : }
687 :
688 : static inline fd_bn254_fp12_t *
689 : fd_bn254_fp12_frob( fd_bn254_fp12_t * r,
690 1290 : fd_bn254_fp12_t const * a ) {
691 : /* https://eprint.iacr.org/2010/354, Alg. 28 */
692 1290 : fd_bn254_fp2_t t[5];
693 :
694 : /* conj(g0) */
695 1290 : fd_bn254_fp2_conj( &r->el[0].el[0], &a->el[0].el[0] );
696 1290 : fd_bn254_fp2_conj( &t[0], &a->el[0].el[1] );
697 1290 : fd_bn254_fp2_conj( &t[1], &a->el[0].el[2] );
698 1290 : fd_bn254_fp2_conj( &t[2], &a->el[1].el[0] );
699 1290 : fd_bn254_fp2_conj( &t[3], &a->el[1].el[1] );
700 1290 : fd_bn254_fp2_conj( &t[4], &a->el[1].el[2] );
701 :
702 : /* conj(g1) * gamma_1,2 */
703 1290 : fd_bn254_fp2_mul( &r->el[0].el[1], &t[0], &fd_bn254_const_frob_gamma1_mont[1] );
704 :
705 : /* conj(g2) * gamma_1,4 */
706 1290 : fd_bn254_fp2_mul( &r->el[0].el[2], &t[1], &fd_bn254_const_frob_gamma1_mont[3] );
707 :
708 : /* conj(h0) * gamma_1,1 */
709 1290 : fd_bn254_fp2_mul( &r->el[1].el[0], &t[2], &fd_bn254_const_frob_gamma1_mont[0] );
710 :
711 : /* conj(h1) * gamma_1,3 */
712 1290 : fd_bn254_fp2_mul( &r->el[1].el[1], &t[3], &fd_bn254_const_frob_gamma1_mont[2] );
713 :
714 : /* conj(h2) * gamma_1,5 */
715 1290 : fd_bn254_fp2_mul( &r->el[1].el[2], &t[4], &fd_bn254_const_frob_gamma1_mont[4] );
716 1290 : return r;
717 1290 : }
718 :
719 : static inline fd_bn254_fp12_t *
720 : fd_bn254_fp12_frob2( fd_bn254_fp12_t * r,
721 1935 : fd_bn254_fp12_t const * a ) {
722 : /* https://eprint.iacr.org/2010/354, Alg. 29 */
723 :
724 : /* g0 */
725 1935 : fd_bn254_fp2_set( &r->el[0].el[0], &a->el[0].el[0] );
726 :
727 : /* g1 * gamma_2,2 */
728 1935 : 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] );
729 1935 : 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] );
730 :
731 : /* g2 * gamma_2,4 */
732 1935 : 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] );
733 1935 : 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] );
734 :
735 : /* h0 * gamma_2,1 */
736 1935 : 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] );
737 1935 : 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] );
738 :
739 : /* h1 * gamma_2,3 */
740 1935 : 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] );
741 1935 : 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] );
742 :
743 : /* h2 * gamma_2,5 */
744 1935 : 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] );
745 1935 : 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] );
746 1935 : return r;
747 1935 : }
|
