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 65739 : int * is_neg ) {
77 : /* validate fp2.el[0] without flags */
78 65739 : 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 65739 : 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 65739 : return r;
86 65739 : }
87 :
88 : static inline uchar *
89 : fd_bn254_fp2_tobytes_nm( uchar buf[64],
90 : fd_bn254_fp2_t * const a,
91 36951 : int big_endian ) {
92 36951 : fd_bn254_fp_tobytes_nm( &buf[ 0], &a->el[ big_endian ? 1 : 0 ], big_endian );
93 36951 : fd_bn254_fp_tobytes_nm( &buf[32], &a->el[ big_endian ? 0 : 1 ], big_endian );
94 36951 : return buf;
95 36951 : }
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 74706 : fd_bn254_fp2_t const * b ) {
121 74706 : return fd_bn254_fp_eq( &a->el[0], &b->el[0] )
122 74706 : && fd_bn254_fp_eq( &a->el[1], &b->el[1] );
123 74706 : }
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 1795398 : fd_bn254_fp2_t const * a ) {
129 1795398 : fd_bn254_fp_set( &r->el[0], &a->el[0] );
130 1795398 : fd_bn254_fp_set( &r->el[1], &a->el[1] );
131 1795398 : return r;
132 1795398 : }
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 3765 : fd_bn254_fp2_t const * a ) {
138 3765 : fd_bn254_fp_from_mont( &r->el[0], &a->el[0] );
139 3765 : fd_bn254_fp_from_mont( &r->el[1], &a->el[1] );
140 3765 : return r;
141 3765 : }
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 5553 : fd_bn254_fp2_t const * a ) {
147 5553 : fd_bn254_fp_to_mont( &r->el[0], &a->el[0] );
148 5553 : fd_bn254_fp_to_mont( &r->el[1], &a->el[1] );
149 5553 : return r;
150 5553 : }
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 101772 : fd_bn254_fp2_t const * a ) {
166 101772 : fd_bn254_fp_neg( &r->el[0], &a->el[0] );
167 101772 : fd_bn254_fp_neg( &r->el[1], &a->el[1] );
168 101772 : return r;
169 101772 : }
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 9993264 : fd_bn254_fp2_t const * b ) {
185 9993264 : fd_bn254_fp_add( &r->el[0], &a->el[0], &b->el[0] );
186 9993264 : fd_bn254_fp_add( &r->el[1], &a->el[1], &b->el[1] );
187 9993264 : return r;
188 9993264 : }
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 6076512 : fd_bn254_fp2_t const * b ) {
195 6076512 : fd_bn254_fp_sub( &r->el[0], &a->el[0], &b->el[0] );
196 6076512 : fd_bn254_fp_sub( &r->el[1], &a->el[1], &b->el[1] );
197 6076512 : return r;
198 6076512 : }
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 21237 : fd_bn254_fp2_t const * a ) {
205 21237 : fd_bn254_fp_set( &r->el[0], &a->el[0] );
206 21237 : fd_bn254_fp_neg( &r->el[1], &a->el[1] );
207 21237 : return r;
208 21237 : }
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 4630308 : fd_bn254_fp2_t const * b ) {
218 4630308 : fd_bn254_fp_t const * a0 = &a->el[0];
219 4630308 : fd_bn254_fp_t const * a1 = &a->el[1];
220 4630308 : fd_bn254_fp_t const * b0 = &b->el[0];
221 4630308 : fd_bn254_fp_t const * b1 = &b->el[1];
222 4630308 : fd_bn254_fp_t * r0 = &r->el[0];
223 4630308 : fd_bn254_fp_t * r1 = &r->el[1];
224 4630308 : fd_bn254_fp_t a0b0[1], a1b1[1], sa[1], sb[1];
225 :
226 4630308 : fd_bn254_fp_add( sa, a0, a1 );
227 4630308 : fd_bn254_fp_add( sb, b0, b1 );
228 :
229 4630308 : fd_bn254_fp_mul( a0b0, a0, b0 );
230 4630308 : fd_bn254_fp_mul( a1b1, a1, b1 );
231 4630308 : fd_bn254_fp_mul( r1, sa, sb );
232 :
233 4630308 : fd_bn254_fp_sub( r0, a0b0, a1b1 ); /* i^2 = -1 */
234 4630308 : fd_bn254_fp_sub( r1, r1, a0b0 );
235 4630308 : fd_bn254_fp_sub( r1, r1, a1b1 );
236 4630308 : return r;
237 4630308 : }
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 4032531 : fd_bn254_fp2_t const * a ) {
245 4032531 : fd_bn254_fp_t p[1], m[1];
246 4032531 : fd_bn254_fp_add( p, &a->el[0], &a->el[1] );
247 4032531 : fd_bn254_fp_sub( m, &a->el[0], &a->el[1] );
248 : /* r1 = 2 a0*a1 */
249 4032531 : fd_bn254_fp_mul( &r->el[1], &a->el[0], &a->el[1] );
250 4032531 : fd_bn254_fp_add( &r->el[1], &r->el[1], &r->el[1] );
251 : /* r0 = (a0-a1)*(a0+a1) */
252 4032531 : fd_bn254_fp_mul( &r->el[0], p, m );
253 4032531 : return r;
254 4032531 : }
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 1008 : fd_bn254_fp2_t const * a ) {
272 1008 : fd_bn254_fp_t t0[1], t1[1];
273 1008 : fd_bn254_fp_sqr( t0, &a->el[0] );
274 1008 : fd_bn254_fp_sqr( t1, &a->el[1] );
275 1008 : fd_bn254_fp_add( t0, t0, t1 );
276 1008 : fd_bn254_fp_inv( t1, t0 );
277 1008 : fd_bn254_fp_mul( &r->el[0], &a->el[0], t1 );
278 1008 : fd_bn254_fp_mul( &r->el[1], &a->el[1], t1 );
279 1008 : fd_bn254_fp_neg( &r->el[1], &r->el[1] );
280 1008 : return r;
281 1008 : }
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 6186 : fd_uint256_t const * b ) {
288 6186 : fd_bn254_fp2_set_one( r );
289 :
290 6186 : int i = 255;
291 27837 : while( !fd_uint256_bit( b, i) ) i--;
292 1568151 : for( ; i>=0; i--) {
293 1561965 : fd_bn254_fp2_sqr( r, r );
294 1561965 : if( fd_uint256_bit( b, i ) ) {
295 677367 : fd_bn254_fp2_mul( r, r, a );
296 677367 : }
297 1561965 : }
298 6186 : return r;
299 6186 : }
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 3093 : fd_bn254_fp2_t const * a ) {
309 3093 : fd_bn254_fp2_t a0[1], a1[1], alpha[1], x0[1];
310 :
311 3093 : fd_bn254_fp2_pow( a1, a, fd_bn254_const_sqrt_exp );
312 :
313 3093 : fd_bn254_fp2_sqr( alpha, a1 );
314 3093 : fd_bn254_fp2_mul( alpha, alpha, a );
315 :
316 3093 : fd_bn254_fp2_conj( a0, alpha );
317 3093 : fd_bn254_fp2_mul( a0, a0, alpha );
318 :
319 3093 : if( FD_UNLIKELY( fd_bn254_fp2_is_minus_one( a0 ) ) ) {
320 0 : return NULL;
321 0 : }
322 :
323 3093 : fd_bn254_fp2_mul( x0, a1, a );
324 3093 : 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 3093 : } else {
330 3093 : fd_bn254_fp2_set_one( a1 );
331 3093 : fd_bn254_fp2_add( a0, alpha, a1 ); /* 1 + alpha */
332 3093 : fd_bn254_fp2_pow( a1, a0, fd_bn254_const_p_minus_one_half ); /* b */
333 3093 : fd_bn254_fp2_mul( r, a1, x0 );
334 3093 : }
335 3093 : return r;
336 3093 : }
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 1525833 : fd_bn254_fp2_t const * a ) {
344 : /* xi = 9 + i
345 : r = (9*a0 - a1) + (9*a1 + a0) i */
346 1525833 : fd_bn254_fp_t r0[1], r1[1];
347 :
348 1525833 : fd_bn254_fp_add( r0, &a->el[0], &a->el[0] );
349 1525833 : fd_bn254_fp_add( r0, r0, r0 );
350 1525833 : fd_bn254_fp_add( r0, r0, r0 );
351 1525833 : fd_bn254_fp_add( r0, r0, &a->el[0] );
352 1525833 : fd_bn254_fp_sub( r0, r0, &a->el[1] );
353 :
354 1525833 : fd_bn254_fp_add( r1, &a->el[1], &a->el[1] );
355 1525833 : fd_bn254_fp_add( r1, r1, r1 );
356 1525833 : fd_bn254_fp_add( r1, r1, r1 );
357 1525833 : fd_bn254_fp_add( r1, r1, &a->el[1] );
358 1525833 : fd_bn254_fp_add( &r->el[1], r1, &a->el[0] );
359 :
360 1525833 : fd_bn254_fp_set( &r->el[0], r0 );
361 1525833 : return r;
362 1525833 : }
363 :
364 : /* Fp6 */
365 :
366 : static inline fd_bn254_fp6_t *
367 : fd_bn254_fp6_set( fd_bn254_fp6_t * r,
368 3450 : fd_bn254_fp6_t const * a ) {
369 3450 : fd_bn254_fp2_set( &r->el[0], &a->el[0] );
370 3450 : fd_bn254_fp2_set( &r->el[1], &a->el[1] );
371 3450 : fd_bn254_fp2_set( &r->el[2], &a->el[2] );
372 3450 : return r;
373 3450 : }
374 :
375 : static inline fd_bn254_fp6_t *
376 : fd_bn254_fp6_neg( fd_bn254_fp6_t * r,
377 4140 : fd_bn254_fp6_t const * a ) {
378 4140 : fd_bn254_fp2_neg( &r->el[0], &a->el[0] );
379 4140 : fd_bn254_fp2_neg( &r->el[1], &a->el[1] );
380 4140 : fd_bn254_fp2_neg( &r->el[2], &a->el[2] );
381 4140 : return r;
382 4140 : }
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 437139 : fd_bn254_fp6_t const * b ) {
388 437139 : fd_bn254_fp2_add( &r->el[0], &a->el[0], &b->el[0] );
389 437139 : fd_bn254_fp2_add( &r->el[1], &a->el[1], &b->el[1] );
390 437139 : fd_bn254_fp2_add( &r->el[2], &a->el[2], &b->el[2] );
391 437139 : return r;
392 437139 : }
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 292116 : fd_bn254_fp6_t const * b ) {
398 292116 : fd_bn254_fp2_sub( &r->el[0], &a->el[0], &b->el[0] );
399 292116 : fd_bn254_fp2_sub( &r->el[1], &a->el[1], &b->el[1] );
400 292116 : fd_bn254_fp2_sub( &r->el[2], &a->el[2], &b->el[2] );
401 292116 : return r;
402 292116 : }
403 :
404 : static inline fd_bn254_fp6_t *
405 : fd_bn254_fp6_mul_by_gamma( fd_bn254_fp6_t * r,
406 171171 : fd_bn254_fp6_t const * a ) {
407 : /* https://eprint.iacr.org/2010/354, Alg. 12 */
408 171171 : fd_bn254_fp2_t t[1];
409 171171 : fd_bn254_fp2_mul_by_xi( t, &a->el[2] );
410 171171 : fd_bn254_fp2_set( &r->el[2], &a->el[1] );
411 171171 : fd_bn254_fp2_set( &r->el[1], &a->el[0] );
412 171171 : fd_bn254_fp2_set( &r->el[0], t );
413 171171 : return r;
414 171171 : }
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 413751 : fd_bn254_fp6_t const * b ) {
420 : /* https://eprint.iacr.org/2010/354, Alg. 13 */
421 413751 : fd_bn254_fp2_t const * a0 = &a->el[0];
422 413751 : fd_bn254_fp2_t const * a1 = &a->el[1];
423 413751 : fd_bn254_fp2_t const * a2 = &a->el[2];
424 413751 : fd_bn254_fp2_t const * b0 = &b->el[0];
425 413751 : fd_bn254_fp2_t const * b1 = &b->el[1];
426 413751 : fd_bn254_fp2_t const * b2 = &b->el[2];
427 413751 : fd_bn254_fp2_t a0b0[1], a1b1[1], a2b2[1];
428 413751 : fd_bn254_fp2_t sa[1], sb[1];
429 413751 : fd_bn254_fp2_t r0[1], r1[1], r2[1];
430 :
431 413751 : fd_bn254_fp2_mul( a0b0, a0, b0 );
432 413751 : fd_bn254_fp2_mul( a1b1, a1, b1 );
433 413751 : fd_bn254_fp2_mul( a2b2, a2, b2 );
434 :
435 413751 : fd_bn254_fp2_add( sa, a1, a2 );
436 413751 : fd_bn254_fp2_add( sb, b1, b2 );
437 413751 : fd_bn254_fp2_mul( r0, sa, sb );
438 413751 : fd_bn254_fp2_sub( r0, r0, a1b1 );
439 413751 : fd_bn254_fp2_sub( r0, r0, a2b2 );
440 413751 : fd_bn254_fp2_mul_by_xi( r0, r0 );
441 413751 : fd_bn254_fp2_add( r0, r0, a0b0 );
442 :
443 413751 : fd_bn254_fp2_add( sa, a0, a2 );
444 413751 : fd_bn254_fp2_add( sb, b0, b2 );
445 413751 : fd_bn254_fp2_mul( r2, sa, sb );
446 413751 : fd_bn254_fp2_sub( r2, r2, a0b0 );
447 413751 : fd_bn254_fp2_sub( r2, r2, a2b2 );
448 413751 : fd_bn254_fp2_add( r2, r2, a1b1 );
449 :
450 413751 : fd_bn254_fp2_add( sa, a0, a1 );
451 413751 : fd_bn254_fp2_add( sb, b0, b1 );
452 413751 : fd_bn254_fp2_mul( r1, sa, sb );
453 413751 : fd_bn254_fp2_sub( r1, r1, a0b0 );
454 413751 : fd_bn254_fp2_sub( r1, r1, a1b1 );
455 413751 : fd_bn254_fp2_mul_by_xi( a2b2, a2b2 );
456 413751 : fd_bn254_fp2_add( r1, r1, a2b2 );
457 :
458 413751 : fd_bn254_fp2_set( &r->el[0], r0 );
459 413751 : fd_bn254_fp2_set( &r->el[1], r1 );
460 413751 : fd_bn254_fp2_set( &r->el[2], r2 );
461 413751 : return r;
462 413751 : }
463 :
464 : static inline fd_bn254_fp6_t *
465 : fd_bn254_fp6_sqr( fd_bn254_fp6_t * r,
466 1380 : fd_bn254_fp6_t const * a ) {
467 : /* https://eprint.iacr.org/2010/354, Alg. 16 */
468 1380 : fd_bn254_fp2_t const * a0 = &a->el[0];
469 1380 : fd_bn254_fp2_t const * a1 = &a->el[1];
470 1380 : fd_bn254_fp2_t const * a2 = &a->el[2];
471 1380 : fd_bn254_fp2_t c0[1], c1[1], c2[1];
472 1380 : fd_bn254_fp2_t c3[1], c4[1], c5[1];
473 :
474 1380 : fd_bn254_fp2_mul( c4, a0, a1 );
475 1380 : fd_bn254_fp2_add( c4, c4, c4 );
476 1380 : fd_bn254_fp2_sqr( c5, a2 );
477 :
478 1380 : fd_bn254_fp2_sub( c2, c4, c5 );
479 1380 : fd_bn254_fp2_mul_by_xi( c5, c5 );
480 1380 : fd_bn254_fp2_add( c1, c4, c5 );
481 :
482 1380 : fd_bn254_fp2_sqr( c3, a0 );
483 1380 : fd_bn254_fp2_sub( c4, a0, a1 );
484 1380 : fd_bn254_fp2_add( c4, c4, a2 );
485 :
486 1380 : fd_bn254_fp2_mul( c5, a1, a2 );
487 1380 : fd_bn254_fp2_add( c5, c5, c5 );
488 1380 : fd_bn254_fp2_sqr( c4, c4 );
489 :
490 1380 : fd_bn254_fp2_add( c2, c2, c4 );
491 1380 : fd_bn254_fp2_add( c2, c2, c5 );
492 1380 : fd_bn254_fp2_sub( c2, c2, c3 );
493 1380 : fd_bn254_fp2_mul_by_xi( c5, c5 );
494 1380 : fd_bn254_fp2_add( c0, c3, c5 );
495 :
496 1380 : fd_bn254_fp2_set( &r->el[0], c0 );
497 1380 : fd_bn254_fp2_set( &r->el[1], c1 );
498 1380 : fd_bn254_fp2_set( &r->el[2], c2 );
499 1380 : return r;
500 1380 : }
501 :
502 : static inline fd_bn254_fp6_t *
503 : fd_bn254_fp6_inv( fd_bn254_fp6_t * r,
504 690 : fd_bn254_fp6_t const * a ) {
505 : /* https://eprint.iacr.org/2010/354, Alg. 17 */
506 690 : fd_bn254_fp2_t t[6];
507 690 : fd_bn254_fp2_sqr( &t[0], &a->el[0] );
508 690 : fd_bn254_fp2_sqr( &t[1], &a->el[1] );
509 690 : fd_bn254_fp2_sqr( &t[2], &a->el[2] );
510 690 : fd_bn254_fp2_mul( &t[3], &a->el[0], &a->el[1] );
511 690 : fd_bn254_fp2_mul( &t[4], &a->el[0], &a->el[2] );
512 690 : fd_bn254_fp2_mul( &t[5], &a->el[1], &a->el[2] );
513 : /* t0 := c0 = t0 - xi * t5 */
514 690 : fd_bn254_fp2_mul_by_xi( &t[5], &t[5] );
515 690 : fd_bn254_fp2_sub( &t[0], &t[0], &t[5] );
516 : /* t2 := c1 = xi * t2 - t3 */
517 690 : fd_bn254_fp2_mul_by_xi( &t[2], &t[2] );
518 690 : 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 690 : fd_bn254_fp2_sub( &t[1], &t[1], &t[4] );
521 : /* t3 := t6 = a0 * c0 */
522 690 : fd_bn254_fp2_mul( &t[3], &a->el[0], &t[0] );
523 : /* t3 := t6 = t6 + (xi * a2 * c1 =: t4) */
524 690 : fd_bn254_fp2_mul( &t[4], &a->el[2], &t[2] );
525 690 : fd_bn254_fp2_mul_by_xi( &t[4], &t[4] );
526 690 : fd_bn254_fp2_add( &t[3], &t[3], &t[4] );
527 : /* t3 := t6 = t6 + (xi * a2 * c1 =: t4) */
528 690 : fd_bn254_fp2_mul( &t[5], &a->el[1], &t[1] );
529 690 : fd_bn254_fp2_mul_by_xi( &t[5], &t[5] );
530 690 : fd_bn254_fp2_add( &t[3], &t[3], &t[5] );
531 : /* t4 := t6^-1 */
532 690 : fd_bn254_fp2_inv( &t[4], &t[3] );
533 :
534 690 : fd_bn254_fp2_mul( &r->el[0], &t[0], &t[4] );
535 690 : fd_bn254_fp2_mul( &r->el[1], &t[2], &t[4] );
536 690 : fd_bn254_fp2_mul( &r->el[2], &t[1], &t[4] );
537 690 : return r;
538 690 : }
539 :
540 : /* Fp12 */
541 :
542 : static inline fd_bn254_fp12_t *
543 : fd_bn254_fp12_conj( fd_bn254_fp12_t * r,
544 3450 : fd_bn254_fp12_t const * a ) {
545 3450 : fd_bn254_fp6_set( &r->el[0], &a->el[0] );
546 3450 : fd_bn254_fp6_neg( &r->el[1], &a->el[1] );
547 3450 : return r;
548 3450 : }
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_fp12_t *
571 : fd_bn254_fp12_mul( fd_bn254_fp12_t * r,
572 : fd_bn254_fp12_t const * a,
573 120945 : fd_bn254_fp12_t const * b ) {
574 : /* https://eprint.iacr.org/2010/354, Alg. 20 */
575 120945 : fd_bn254_fp6_t const * a0 = &a->el[0];
576 120945 : fd_bn254_fp6_t const * a1 = &a->el[1];
577 120945 : fd_bn254_fp6_t const * b0 = &b->el[0];
578 120945 : fd_bn254_fp6_t const * b1 = &b->el[1];
579 120945 : fd_bn254_fp6_t * r0 = &r->el[0];
580 120945 : fd_bn254_fp6_t * r1 = &r->el[1];
581 120945 : fd_bn254_fp6_t a0b0[1], a1b1[1], sa[1], sb[1];
582 :
583 120945 : fd_bn254_fp6_add( sa, a0, a1 );
584 120945 : fd_bn254_fp6_add( sb, b0, b1 );
585 :
586 120945 : fd_bn254_fp6_mul( a0b0, a0, b0 );
587 120945 : fd_bn254_fp6_mul( a1b1, a1, b1 );
588 120945 : fd_bn254_fp6_mul( r1, sa, sb );
589 :
590 120945 : fd_bn254_fp6_sub( r1, r1, a0b0 );
591 120945 : fd_bn254_fp6_sub( r1, r1, a1b1 );
592 :
593 120945 : fd_bn254_fp6_mul_by_gamma( a1b1, a1b1 );
594 120945 : fd_bn254_fp6_add( r0, a0b0, a1b1 );
595 120945 : return r;
596 120945 : }
597 :
598 : static inline fd_bn254_fp12_t *
599 : fd_bn254_fp12_sqr( fd_bn254_fp12_t * r,
600 24768 : fd_bn254_fp12_t const * a ) {
601 : /* https://eprint.iacr.org/2010/354, Alg. 22. */
602 24768 : fd_bn254_fp6_t c0[1], c2[1], c3[1];
603 24768 : fd_bn254_fp6_sub( c0, &a->el[0], &a->el[1] );
604 24768 : fd_bn254_fp6_mul_by_gamma( c3, &a->el[1] );
605 24768 : fd_bn254_fp6_sub( c3, &a->el[0], c3 );
606 24768 : fd_bn254_fp6_mul( c2, &a->el[0], &a->el[1] );
607 24768 : fd_bn254_fp6_mul( c0, c0, c3 );
608 24768 : fd_bn254_fp6_add( c0, c0, c2 );
609 24768 : fd_bn254_fp6_add( &r->el[1], c2, c2 );
610 24768 : fd_bn254_fp6_mul_by_gamma( &r->el[0], c2 );
611 24768 : fd_bn254_fp6_add( &r->el[0], &r->el[0], c0 );
612 24768 : return r;
613 24768 : }
614 :
615 : static inline fd_bn254_fp12_t *
616 : fd_bn254_fp12_sqr_fast( fd_bn254_fp12_t * r,
617 130410 : fd_bn254_fp12_t const * a ) {
618 : /* Cyclotomic sqr, https://eprint.iacr.org/2009/565, Sec. 3.2.
619 : Variant of https://eprint.iacr.org/2010/354, Alg. 24.
620 : This works when a^(p^6+1)=1, e.g. during pairing final exp. */
621 130410 : fd_bn254_fp2_t t[9];
622 :
623 130410 : fd_bn254_fp2_sqr( &t[0], &a->el[1].el[1] );
624 130410 : fd_bn254_fp2_sqr( &t[1], &a->el[0].el[0] );
625 130410 : fd_bn254_fp2_add( &t[6], &a->el[1].el[1], &a->el[0].el[0] );
626 130410 : fd_bn254_fp2_sqr( &t[6], &t[6] );
627 130410 : fd_bn254_fp2_sub( &t[6], &t[6], &t[0] );
628 130410 : fd_bn254_fp2_sub( &t[6], &t[6], &t[1] );
629 :
630 130410 : fd_bn254_fp2_sqr( &t[2], &a->el[0].el[2] );
631 130410 : fd_bn254_fp2_sqr( &t[3], &a->el[1].el[0] );
632 130410 : fd_bn254_fp2_add( &t[7], &a->el[0].el[2], &a->el[1].el[0] );
633 130410 : fd_bn254_fp2_sqr( &t[7], &t[7] );
634 130410 : fd_bn254_fp2_sub( &t[7], &t[7], &t[2] );
635 130410 : fd_bn254_fp2_sub( &t[7], &t[7], &t[3] );
636 :
637 130410 : fd_bn254_fp2_sqr( &t[4], &a->el[1].el[2] );
638 130410 : fd_bn254_fp2_sqr( &t[5], &a->el[0].el[1] );
639 130410 : fd_bn254_fp2_add( &t[8], &a->el[1].el[2], &a->el[0].el[1] );
640 130410 : fd_bn254_fp2_sqr( &t[8], &t[8] );
641 130410 : fd_bn254_fp2_sub( &t[8], &t[8], &t[4] );
642 130410 : fd_bn254_fp2_sub( &t[8], &t[8], &t[5] );
643 130410 : fd_bn254_fp2_mul_by_xi( &t[8], &t[8] );
644 :
645 130410 : fd_bn254_fp2_mul_by_xi( &t[0], &t[0] );
646 130410 : fd_bn254_fp2_add( &t[0], &t[0], &t[1] );
647 130410 : fd_bn254_fp2_mul_by_xi( &t[2], &t[2] );
648 130410 : fd_bn254_fp2_add( &t[2], &t[2], &t[3] );
649 130410 : fd_bn254_fp2_mul_by_xi( &t[4], &t[4] );
650 130410 : fd_bn254_fp2_add( &t[4], &t[4], &t[5] );
651 :
652 130410 : fd_bn254_fp2_sub( &r->el[0].el[0], &t[0], &a->el[0].el[0] );
653 130410 : fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &r->el[0].el[0] );
654 130410 : fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &t[0] );
655 130410 : fd_bn254_fp2_sub( &r->el[0].el[1], &t[2], &a->el[0].el[1] );
656 130410 : fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &r->el[0].el[1] );
657 130410 : fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &t[2] );
658 130410 : fd_bn254_fp2_sub( &r->el[0].el[2], &t[4], &a->el[0].el[2] );
659 130410 : fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &r->el[0].el[2] );
660 130410 : fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &t[4] );
661 :
662 130410 : fd_bn254_fp2_add( &r->el[1].el[0], &t[8], &a->el[1].el[0] );
663 130410 : fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &r->el[1].el[0] );
664 130410 : fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &t[8] );
665 130410 : fd_bn254_fp2_add( &r->el[1].el[1], &t[6], &a->el[1].el[1] );
666 130410 : fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &r->el[1].el[1] );
667 130410 : fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &t[6] );
668 130410 : fd_bn254_fp2_add( &r->el[1].el[2], &t[7], &a->el[1].el[2] );
669 130410 : fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &r->el[1].el[2] );
670 130410 : fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &t[7] );
671 130410 : return r;
672 130410 : }
673 :
674 : fd_bn254_fp12_t *
675 : fd_bn254_fp12_inv( fd_bn254_fp12_t * r,
676 690 : fd_bn254_fp12_t const * a ) {
677 : /* https://eprint.iacr.org/2010/354, Alg. 23 */
678 690 : fd_bn254_fp6_t t0[1], t1[1];
679 690 : fd_bn254_fp6_sqr( t0, &a->el[0] );
680 690 : fd_bn254_fp6_sqr( t1, &a->el[1] );
681 690 : fd_bn254_fp6_mul_by_gamma( t1, t1 );
682 690 : fd_bn254_fp6_sub( t0, t0, t1 );
683 690 : fd_bn254_fp6_inv( t1, t0 );
684 690 : fd_bn254_fp6_mul( &r->el[0], &a->el[0], t1 );
685 690 : fd_bn254_fp6_mul( &r->el[1], &a->el[1], t1 );
686 690 : fd_bn254_fp6_neg( &r->el[1], &r->el[1] );
687 690 : return r;
688 690 : }
689 :
690 : static inline fd_bn254_fp12_t *
691 : fd_bn254_fp12_frob( fd_bn254_fp12_t * r,
692 1380 : fd_bn254_fp12_t const * a ) {
693 : /* https://eprint.iacr.org/2010/354, Alg. 28 */
694 1380 : fd_bn254_fp2_t t[5];
695 :
696 : /* conj(g0) */
697 1380 : fd_bn254_fp2_conj( &r->el[0].el[0], &a->el[0].el[0] );
698 1380 : fd_bn254_fp2_conj( &t[0], &a->el[0].el[1] );
699 1380 : fd_bn254_fp2_conj( &t[1], &a->el[0].el[2] );
700 1380 : fd_bn254_fp2_conj( &t[2], &a->el[1].el[0] );
701 1380 : fd_bn254_fp2_conj( &t[3], &a->el[1].el[1] );
702 1380 : fd_bn254_fp2_conj( &t[4], &a->el[1].el[2] );
703 :
704 : /* conj(g1) * gamma_1,2 */
705 1380 : fd_bn254_fp2_mul( &r->el[0].el[1], &t[0], &fd_bn254_const_frob_gamma1_mont[1] );
706 :
707 : /* conj(g2) * gamma_1,4 */
708 1380 : fd_bn254_fp2_mul( &r->el[0].el[2], &t[1], &fd_bn254_const_frob_gamma1_mont[3] );
709 :
710 : /* conj(h0) * gamma_1,1 */
711 1380 : fd_bn254_fp2_mul( &r->el[1].el[0], &t[2], &fd_bn254_const_frob_gamma1_mont[0] );
712 :
713 : /* conj(h1) * gamma_1,3 */
714 1380 : fd_bn254_fp2_mul( &r->el[1].el[1], &t[3], &fd_bn254_const_frob_gamma1_mont[2] );
715 :
716 : /* conj(h2) * gamma_1,5 */
717 1380 : fd_bn254_fp2_mul( &r->el[1].el[2], &t[4], &fd_bn254_const_frob_gamma1_mont[4] );
718 1380 : return r;
719 1380 : }
720 :
721 : static inline fd_bn254_fp12_t *
722 : fd_bn254_fp12_frob2( fd_bn254_fp12_t * r,
723 2070 : fd_bn254_fp12_t const * a ) {
724 : /* https://eprint.iacr.org/2010/354, Alg. 29 */
725 :
726 : /* g0 */
727 2070 : fd_bn254_fp2_set( &r->el[0].el[0], &a->el[0].el[0] );
728 :
729 : /* g1 * gamma_2,2 */
730 2070 : 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] );
731 2070 : 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] );
732 :
733 : /* g2 * gamma_2,4 */
734 2070 : 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] );
735 2070 : 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] );
736 :
737 : /* h0 * gamma_2,1 */
738 2070 : 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] );
739 2070 : 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] );
740 :
741 : /* h1 * gamma_2,3 */
742 2070 : 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] );
743 2070 : 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] );
744 :
745 : /* h2 * gamma_2,5 */
746 2070 : 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] );
747 2070 : 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] );
748 2070 : return r;
749 2070 : }
|
