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       24674 :                         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       24674 :   fd_bn254_fp2_t t[9];
      12             : 
      13       24674 :   fd_bn254_fp2_sqr( &t[0], &a->el[1].el[1] );
      14       24674 :   fd_bn254_fp2_sqr( &t[1], &a->el[0].el[0] );
      15       24674 :   fd_bn254_fp2_add( &t[6], &a->el[1].el[1], &a->el[0].el[0] );
      16       24674 :   fd_bn254_fp2_sqr( &t[6], &t[6] );
      17       24674 :   fd_bn254_fp2_sub( &t[6], &t[6], &t[0] );
      18       24674 :   fd_bn254_fp2_sub( &t[6], &t[6], &t[1] );
      19             : 
      20       24674 :   fd_bn254_fp2_sqr( &t[2], &a->el[0].el[2] );
      21       24674 :   fd_bn254_fp2_sqr( &t[3], &a->el[1].el[0] );
      22       24674 :   fd_bn254_fp2_add( &t[7], &a->el[0].el[2], &a->el[1].el[0] );
      23       24674 :   fd_bn254_fp2_sqr( &t[7], &t[7] );
      24       24674 :   fd_bn254_fp2_sub( &t[7], &t[7], &t[2] );
      25       24674 :   fd_bn254_fp2_sub( &t[7], &t[7], &t[3] );
      26             : 
      27       24674 :   fd_bn254_fp2_sqr( &t[4], &a->el[1].el[2] );
      28       24674 :   fd_bn254_fp2_sqr( &t[5], &a->el[0].el[1] );
      29       24674 :   fd_bn254_fp2_add( &t[8], &a->el[1].el[2], &a->el[0].el[1] );
      30       24674 :   fd_bn254_fp2_sqr( &t[8], &t[8] );
      31       24674 :   fd_bn254_fp2_sub( &t[8], &t[8], &t[4] );
      32       24674 :   fd_bn254_fp2_sub( &t[8], &t[8], &t[5] );
      33       24674 :   fd_bn254_fp2_mul_by_xi( &t[8], &t[8] );
      34             : 
      35       24674 :   fd_bn254_fp2_mul_by_xi( &t[0], &t[0] );
      36       24674 :   fd_bn254_fp2_add( &t[0], &t[0], &t[1] );
      37       24674 :   fd_bn254_fp2_mul_by_xi( &t[2], &t[2] );
      38       24674 :   fd_bn254_fp2_add( &t[2], &t[2], &t[3] );
      39       24674 :   fd_bn254_fp2_mul_by_xi( &t[4], &t[4] );
      40       24674 :   fd_bn254_fp2_add( &t[4], &t[4], &t[5] );
      41             : 
      42       24674 :   fd_bn254_fp2_sub( &r->el[0].el[0], &t[0], &a->el[0].el[0] );
      43       24674 :   fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &r->el[0].el[0] );
      44       24674 :   fd_bn254_fp2_add( &r->el[0].el[0], &r->el[0].el[0], &t[0] );
      45       24674 :   fd_bn254_fp2_sub( &r->el[0].el[1], &t[2], &a->el[0].el[1] );
      46       24674 :   fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &r->el[0].el[1] );
      47       24674 :   fd_bn254_fp2_add( &r->el[0].el[1], &r->el[0].el[1], &t[2] );
      48       24674 :   fd_bn254_fp2_sub( &r->el[0].el[2], &t[4], &a->el[0].el[2] );
      49       24674 :   fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &r->el[0].el[2] );
      50       24674 :   fd_bn254_fp2_add( &r->el[0].el[2], &r->el[0].el[2], &t[4] );
      51             : 
      52       24674 :   fd_bn254_fp2_add( &r->el[1].el[0], &t[8], &a->el[1].el[0] );
      53       24674 :   fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &r->el[1].el[0] );
      54       24674 :   fd_bn254_fp2_add( &r->el[1].el[0], &r->el[1].el[0], &t[8] );
      55       24674 :   fd_bn254_fp2_add( &r->el[1].el[1], &t[6], &a->el[1].el[1] );
      56       24674 :   fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &r->el[1].el[1] );
      57       24674 :   fd_bn254_fp2_add( &r->el[1].el[1], &r->el[1].el[1], &t[6] );
      58       24674 :   fd_bn254_fp2_add( &r->el[1].el[2], &t[7], &a->el[1].el[2] );
      59       24674 :   fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &r->el[1].el[2] );
      60       24674 :   fd_bn254_fp2_add( &r->el[1].el[2], &r->el[1].el[2], &t[7] );
      61       24674 :   return r;
      62       24674 : }
      63             : 
      64             : fd_bn254_fp12_t *
      65             : fd_bn254_fp12_pow_x( fd_bn254_fp12_t * restrict r,
      66         396 :                      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         396 :   fd_bn254_fp12_t t[7];
      69         396 :   fd_bn254_fp12_sqr_fast( &t[3], a );
      70         396 :   fd_bn254_fp12_sqr_fast( &t[5], &t[3] );
      71         396 :   fd_bn254_fp12_sqr_fast( r,     &t[5] );
      72         396 :   fd_bn254_fp12_sqr_fast( &t[0], r );
      73         396 :   fd_bn254_fp12_mul     ( &t[2], &t[0], a );
      74         396 :   fd_bn254_fp12_mul     ( &t[0], &t[2], &t[3] );
      75         396 :   fd_bn254_fp12_mul     ( &t[1], &t[0], a );
      76         396 :   fd_bn254_fp12_mul     ( &t[4], &t[2], r );
      77         396 :   fd_bn254_fp12_sqr_fast( &t[6], &t[2] );
      78         396 :   fd_bn254_fp12_mul     ( &t[1], &t[1], &t[0] );
      79         396 :   fd_bn254_fp12_mul     ( &t[0], &t[1], &t[3] );
      80        2763 :   for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[6], &t[6] );
      81         396 :   fd_bn254_fp12_mul     ( &t[5], &t[5], &t[6] );
      82         396 :   fd_bn254_fp12_mul     ( &t[5], &t[5], &t[4] );
      83        3161 :   for( int i=0; i<7; i++ ) fd_bn254_fp12_sqr_fast( &t[5], &t[5] );
      84         396 :   fd_bn254_fp12_mul     ( &t[4], &t[4], &t[5] );
      85        3559 :   for( int i=0; i<8; i++ ) fd_bn254_fp12_sqr_fast( &t[4], &t[4] );
      86         396 :   fd_bn254_fp12_mul     ( &t[4], &t[4], &t[0] );
      87         396 :   fd_bn254_fp12_mul     ( &t[3], &t[3], &t[4] );
      88        2763 :   for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[3], &t[3] );
      89         396 :   fd_bn254_fp12_mul     ( &t[2], &t[2], &t[3] );
      90        3555 :   for( int i=0; i<8; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
      91         396 :   fd_bn254_fp12_mul     ( &t[2], &t[2], &t[0] );
      92        2767 :   for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
      93         396 :   fd_bn254_fp12_mul     ( &t[2], &t[2], &t[0] );
      94        4350 :   for( int i=0; i<10; i++ ) fd_bn254_fp12_sqr_fast( &t[2], &t[2] );
      95         396 :   fd_bn254_fp12_mul     ( &t[1], &t[1], &t[2] );
      96        2769 :   for( int i=0; i<6; i++ ) fd_bn254_fp12_sqr_fast( &t[1], &t[1] );
      97         396 :   fd_bn254_fp12_mul     ( &t[0], &t[0], &t[1] );
      98         396 :   fd_bn254_fp12_mul     ( r, r, &t[0] );
      99         396 :   return r;
     100         396 : }
     101             : 
     102             : fd_bn254_fp12_t *
     103             : fd_bn254_final_exp( fd_bn254_fp12_t *       r,
     104         132 :                     fd_bn254_fp12_t * const x ) {
     105             :   /* https://github.com/Consensys/gnark-crypto/blob/v0.12.1/ecc/bn254/pairing.go#L62 */
     106         132 :   fd_bn254_fp12_t t[5], s[1];
     107         132 :   fd_bn254_fp12_conj ( &t[0], x );            /* x^(p^6) */
     108         132 :   fd_bn254_fp12_inv  ( &t[1], x );            /* x^(-1) */
     109         132 :   fd_bn254_fp12_mul  ( &t[0], &t[0], &t[1] ); /* x^(p^6-1) */
     110         132 :   fd_bn254_fp12_frob2( &t[2], &t[0] );        /* x^(p^6-1)(p^2) */
     111         132 :   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         132 :   fd_bn254_fp12_pow_x   ( &t[0], s );
     115         132 :   fd_bn254_fp12_conj    ( &t[0], &t[0] );
     116         132 :   fd_bn254_fp12_sqr_fast( &t[0], &t[0] );
     117         132 :   fd_bn254_fp12_sqr_fast( &t[1], &t[0] );
     118         132 :   fd_bn254_fp12_mul     ( &t[1], &t[1], &t[0] );
     119             : 
     120         132 :   fd_bn254_fp12_pow_x   ( &t[2], &t[1] );
     121         132 :   fd_bn254_fp12_conj    ( &t[2], &t[2] );
     122         132 :   fd_bn254_fp12_conj    ( &t[3], &t[1] );
     123         132 :   fd_bn254_fp12_mul     ( &t[1], &t[2], &t[3] );
     124             : 
     125         132 :   fd_bn254_fp12_sqr_fast( &t[3], &t[2] );
     126         132 :   fd_bn254_fp12_pow_x   ( &t[4], &t[3] );
     127         132 :   fd_bn254_fp12_mul     ( &t[4], &t[1], &t[4] );
     128         132 :   fd_bn254_fp12_mul     ( &t[3], &t[0], &t[4] );
     129         132 :   fd_bn254_fp12_mul     ( &t[0], &t[2], &t[4] );
     130         132 :   fd_bn254_fp12_mul     ( &t[0], &t[0], s );
     131             : 
     132         132 :   fd_bn254_fp12_frob    ( &t[2], &t[3] );
     133         132 :   fd_bn254_fp12_mul     ( &t[0], &t[0], &t[2] );
     134         132 :   fd_bn254_fp12_frob2   ( &t[2], &t[4] );
     135         132 :   fd_bn254_fp12_mul     ( &t[0], &t[0], &t[2] );
     136             : 
     137         132 :   fd_bn254_fp12_conj    ( &t[2], s );
     138         132 :   fd_bn254_fp12_mul     ( &t[2], &t[2], &t[3] );
     139             :   // fd_bn254_fp12_frob3   ( &t[2], &t[2] );
     140         132 :   fd_bn254_fp12_frob2   ( &t[2], &t[2] );
     141         132 :   fd_bn254_fp12_frob    ( &t[2], &t[2] );
     142         132 :   fd_bn254_fp12_mul     ( r, &t[0], &t[2] );
     143         132 :   return r;
     144         132 : }