Line data Source code
1 : #include "./fd_bn254_field_inl.h"
2 :
3 : /* Pairing final exponentiation */
4 :
5 : static fd_bn254_fp12_t *
6 : fd_bn254_fp12_sqr_fast( fd_bn254_fp12_t * r,
7 130977 : fd_bn254_fp12_t const * a ) {
8 : /* Cyclotomic sqr, https://eprint.iacr.org/2009/565, Sec. 3.2.
9 : Variant of https://eprint.iacr.org/2010/354, Alg. 24.
10 : This works when a^(p^6+1)=1, e.g. during pairing final exp. */
11 130977 : fd_bn254_fp2_t t[9];
12 :
13 130977 : fd_bn254_fp2_sqr( &t[0], &a->el[1].el[1] );
14 130977 : fd_bn254_fp2_sqr( &t[1], &a->el[0].el[0] );
15 130977 : fd_bn254_fp2_add( &t[6], &a->el[1].el[1], &a->el[0].el[0] );
16 130977 : fd_bn254_fp2_sqr( &t[6], &t[6] );
17 130977 : fd_bn254_fp2_sub( &t[6], &t[6], &t[0] );
18 130977 : fd_bn254_fp2_sub( &t[6], &t[6], &t[1] );
19 :
20 130977 : fd_bn254_fp2_sqr( &t[2], &a->el[0].el[2] );
21 130977 : fd_bn254_fp2_sqr( &t[3], &a->el[1].el[0] );
22 130977 : fd_bn254_fp2_add( &t[7], &a->el[0].el[2], &a->el[1].el[0] );
23 130977 : fd_bn254_fp2_sqr( &t[7], &t[7] );
24 130977 : fd_bn254_fp2_sub( &t[7], &t[7], &t[2] );
25 130977 : fd_bn254_fp2_sub( &t[7], &t[7], &t[3] );
26 :
27 130977 : fd_bn254_fp2_sqr( &t[4], &a->el[1].el[2] );
28 130977 : fd_bn254_fp2_sqr( &t[5], &a->el[0].el[1] );
29 130977 : fd_bn254_fp2_add( &t[8], &a->el[1].el[2], &a->el[0].el[1] );
30 130977 : fd_bn254_fp2_sqr( &t[8], &t[8] );
31 130977 : fd_bn254_fp2_sub( &t[8], &t[8], &t[4] );
32 130977 : fd_bn254_fp2_sub( &t[8], &t[8], &t[5] );
33 130977 : fd_bn254_fp2_mul_by_xi( &t[8], &t[8] );
34 :
35 130977 : fd_bn254_fp2_mul_by_xi( &t[0], &t[0] );
36 130977 : fd_bn254_fp2_add( &t[0], &t[0], &t[1] );
37 130977 : fd_bn254_fp2_mul_by_xi( &t[2], &t[2] );
38 130977 : fd_bn254_fp2_add( &t[2], &t[2], &t[3] );
39 130977 : fd_bn254_fp2_mul_by_xi( &t[4], &t[4] );
40 130977 : fd_bn254_fp2_add( &t[4], &t[4], &t[5] );
41 :
42 130977 : fd_bn254_fp2_sub( &r->el[0].el[0], &t[0], &a->el[0].el[0] );
43 130977 : fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &r->el[0].el[0] );
44 130977 : fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &t[0] );
45 130977 : fd_bn254_fp2_sub( &r->el[0].el[1], &t[2], &a->el[0].el[1] );
46 130977 : fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &r->el[0].el[1] );
47 130977 : fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &t[2] );
48 130977 : fd_bn254_fp2_sub( &r->el[0].el[2], &t[4], &a->el[0].el[2] );
49 130977 : fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &r->el[0].el[2] );
50 130977 : fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &t[4] );
51 :
52 130977 : fd_bn254_fp2_add( &r->el[1].el[0], &t[8], &a->el[1].el[0] );
53 130977 : fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &r->el[1].el[0] );
54 130977 : fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &t[8] );
55 130977 : fd_bn254_fp2_add( &r->el[1].el[1], &t[6], &a->el[1].el[1] );
56 130977 : fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &r->el[1].el[1] );
57 130977 : fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &t[6] );
58 130977 : fd_bn254_fp2_add( &r->el[1].el[2], &t[7], &a->el[1].el[2] );
59 130977 : fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &r->el[1].el[2] );
60 130977 : fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &t[7] );
61 130977 : return r;
62 130977 : }
63 :
64 : fd_bn254_fp12_t *
65 : fd_bn254_fp12_pow_x( fd_bn254_fp12_t * restrict r,
66 2079 : fd_bn254_fp12_t const * a ) {
67 : /* https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/internal/fptower/e12_pairing.go#L16 */
68 2079 : fd_bn254_fp12_t t[7];
69 2079 : fd_bn254_fp12_sqr_fast( &t[3], a );
70 2079 : fd_bn254_fp12_sqr_fast( &t[5], &t[3] );
71 2079 : fd_bn254_fp12_sqr_fast( r, &t[5] );
72 2079 : fd_bn254_fp12_sqr_fast( &t[0], r );
73 2079 : fd_bn254_fp12_mul ( &t[2], &t[0], a );
74 2079 : fd_bn254_fp12_mul ( &t[0], &t[2], &t[3] );
75 2079 : fd_bn254_fp12_mul ( &t[1], &t[0], a );
76 2079 : fd_bn254_fp12_mul ( &t[4], &t[2], r );
77 2079 : fd_bn254_fp12_sqr_fast( &t[6], &t[2] );
78 2079 : fd_bn254_fp12_mul ( &t[1], &t[1], &t[0] );
79 2079 : fd_bn254_fp12_mul ( &t[0], &t[1], &t[3] );
80 14553 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[6], &t[6] );
81 2079 : fd_bn254_fp12_mul ( &t[5], &t[5], &t[6] );
82 2079 : fd_bn254_fp12_mul ( &t[5], &t[5], &t[4] );
83 16632 : for( int i=0; i<7; i++ ) fd_bn254_fp12_sqr_fast( &t[5], &t[5] );
84 2079 : fd_bn254_fp12_mul ( &t[4], &t[4], &t[5] );
85 18711 : for( int i=0; i<8; i++ ) fd_bn254_fp12_sqr_fast( &t[4], &t[4] );
86 2079 : fd_bn254_fp12_mul ( &t[4], &t[4], &t[0] );
87 2079 : fd_bn254_fp12_mul ( &t[3], &t[3], &t[4] );
88 14553 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[3], &t[3] );
89 2079 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[3] );
90 18711 : for( int i=0; i<8; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
91 2079 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[0] );
92 14553 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
93 2079 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[0] );
94 22869 : for( int i=0; i<10; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
95 2079 : fd_bn254_fp12_mul ( &t[1], &t[1], &t[2] );
96 14553 : for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[1], &t[1] );
97 2079 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[1] );
98 2079 : fd_bn254_fp12_mul ( r, r, &t[0] );
99 2079 : return r;
100 2079 : }
101 :
102 : fd_bn254_fp12_t *
103 : fd_bn254_final_exp( fd_bn254_fp12_t * r,
104 693 : fd_bn254_fp12_t * const x ) {
105 : /* https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/pairing.go#L62 */
106 693 : fd_bn254_fp12_t t[5], s[1];
107 693 : fd_bn254_fp12_conj ( &t[0], x ); /* x^(p^6) */
108 693 : fd_bn254_fp12_inv ( &t[1], x ); /* x^(-1) */
109 693 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[1] ); /* x^(p^6-1) */
110 693 : fd_bn254_fp12_frob2( &t[2], &t[0] ); /* x^(p^6-1)(p^2) */
111 693 : fd_bn254_fp12_mul ( s, &t[0], &t[2] ); /* x^(p^6-1)(p^2+1) */
112 : /* Fast chain, https://eprint.iacr.org/2015/192, Alg. 10.
113 : Variant of https://eprint.iacr.org/2010/354, Alg. 31. */
114 693 : fd_bn254_fp12_pow_x ( &t[0], s );
115 693 : fd_bn254_fp12_conj ( &t[0], &t[0] );
116 693 : fd_bn254_fp12_sqr_fast( &t[0], &t[0] );
117 693 : fd_bn254_fp12_sqr_fast( &t[1], &t[0] );
118 693 : fd_bn254_fp12_mul ( &t[1], &t[1], &t[0] );
119 :
120 693 : fd_bn254_fp12_pow_x ( &t[2], &t[1] );
121 693 : fd_bn254_fp12_conj ( &t[2], &t[2] );
122 693 : fd_bn254_fp12_conj ( &t[3], &t[1] );
123 693 : fd_bn254_fp12_mul ( &t[1], &t[2], &t[3] );
124 :
125 693 : fd_bn254_fp12_sqr_fast( &t[3], &t[2] );
126 693 : fd_bn254_fp12_pow_x ( &t[4], &t[3] );
127 693 : fd_bn254_fp12_mul ( &t[4], &t[1], &t[4] );
128 693 : fd_bn254_fp12_mul ( &t[3], &t[0], &t[4] );
129 693 : fd_bn254_fp12_mul ( &t[0], &t[2], &t[4] );
130 693 : fd_bn254_fp12_mul ( &t[0], &t[0], s );
131 :
132 693 : fd_bn254_fp12_frob ( &t[2], &t[3] );
133 693 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[2] );
134 693 : fd_bn254_fp12_frob2 ( &t[2], &t[4] );
135 693 : fd_bn254_fp12_mul ( &t[0], &t[0], &t[2] );
136 :
137 693 : fd_bn254_fp12_conj ( &t[2], s );
138 693 : fd_bn254_fp12_mul ( &t[2], &t[2], &t[3] );
139 : // fd_bn254_fp12_frob3 ( &t[2], &t[2] );
140 693 : fd_bn254_fp12_frob2 ( &t[2], &t[2] );
141 693 : fd_bn254_fp12_frob ( &t[2], &t[2] );
142 693 : fd_bn254_fp12_mul ( r, &t[0], &t[2] );
143 693 : return r;
144 693 : }
|
