Line data    Source code

       1             : #include "./fd_bn254_field_inl.h"
       2             : 
       3             : /* Fp12 ops used by the pairing (Miller loop and final exp). */
       4             : 
       5             : /* fd_bn254_fp6_mul_by_fp2 computes r = a * (b, 0, 0) in Fp6.
       6             :    Simply (a0*b, a1*b, a2*b).
       7             :    Cost: 3 Fp2_mul (vs 6 for full Fp6_mul). */
       8             : static inline fd_bn254_fp6_t *
       9             : fd_bn254_fp6_mul_by_fp2( fd_bn254_fp6_t *       r,
      10             :                          fd_bn254_fp6_t const *  a,
      11       77088 :                          fd_bn254_fp2_t const *  b ) {
      12       77088 :   fd_bn254_fp2_mul( &r->el[0], &a->el[0], b );
      13       77088 :   fd_bn254_fp2_mul( &r->el[1], &a->el[1], b );
      14       77088 :   fd_bn254_fp2_mul( &r->el[2], &a->el[2], b );
      15       77088 :   return r;
      16       77088 : }
      17             : 
      18             : /* fd_bn254_fp6_mul_by_01 computes r = a * (b0, b1, 0) in Fp6.
      19             :    Karatsuba with b2=0.
      20             :    Cost: 5 Fp2_mul (vs 6 for full Fp6_mul). */
      21             : static inline fd_bn254_fp6_t *
      22             : fd_bn254_fp6_mul_by_01( fd_bn254_fp6_t *       r,
      23             :                         fd_bn254_fp6_t const *  a,
      24             :                         fd_bn254_fp2_t const *  b0,
      25      154176 :                         fd_bn254_fp2_t const *  b1 ) {
      26      154176 :   fd_bn254_fp2_t const * a0 = &a->el[0];
      27      154176 :   fd_bn254_fp2_t const * a1 = &a->el[1];
      28      154176 :   fd_bn254_fp2_t const * a2 = &a->el[2];
      29      154176 :   fd_bn254_fp2_t a0b0[1], a1b1[1];
      30      154176 :   fd_bn254_fp2_t sa[1], sb[1];
      31      154176 :   fd_bn254_fp2_t r0[1], r1[1], r2[1];
      32             : 
      33      154176 :   fd_bn254_fp2_mul( a0b0, a0, b0 );
      34      154176 :   fd_bn254_fp2_mul( a1b1, a1, b1 );
      35             : 
      36             :   /* r0 = a0b0 + xi * a2*b1 */
      37      154176 :   fd_bn254_fp2_mul( r0, a2, b1 );
      38      154176 :   fd_bn254_fp2_mul_by_xi( r0, r0 );
      39      154176 :   fd_bn254_fp2_add( r0, r0, a0b0 );
      40             : 
      41             :   /* r1 = (a0+a1)*(b0+b1) - a0b0 - a1b1 */
      42      154176 :   fd_bn254_fp2_add( sa, a0, a1 );
      43      154176 :   fd_bn254_fp2_add( sb, b0, b1 );
      44      154176 :   fd_bn254_fp2_mul( r1, sa, sb );
      45      154176 :   fd_bn254_fp2_sub( r1, r1, a0b0 );
      46      154176 :   fd_bn254_fp2_sub( r1, r1, a1b1 );
      47             : 
      48             :   /* r2 = (a0+a2)*b0 - a0b0 + a1b1 */
      49      154176 :   fd_bn254_fp2_add( sa, a0, a2 );
      50      154176 :   fd_bn254_fp2_mul( r2, sa, b0 );
      51      154176 :   fd_bn254_fp2_sub( r2, r2, a0b0 );
      52      154176 :   fd_bn254_fp2_add( r2, r2, a1b1 );
      53             : 
      54      154176 :   fd_bn254_fp2_set( &r->el[0], r0 );
      55      154176 :   fd_bn254_fp2_set( &r->el[1], r1 );
      56      154176 :   fd_bn254_fp2_set( &r->el[2], r2 );
      57      154176 :   return r;
      58      154176 : }
      59             : 
      60             : /* fd_bn254_fp12_mul_sparse computes r = a * b in Fp12,
      61             :    where b has the "034" sparse pattern:
      62             :      b.el[0] = (c0, 0, 0)
      63             :      b.el[1] = (c3, c4, 0)
      64             :    This is the pattern produced by line evaluation functions.
      65             :    Cost: 13 Fp2_mul (vs 18 for full Fp12_mul). */
      66             : fd_bn254_fp12_t *
      67             : fd_bn254_fp12_mul_sparse( fd_bn254_fp12_t *       r,
      68             :                           fd_bn254_fp12_t const * a,
      69       77088 :                           fd_bn254_fp12_t const * b ) {
      70       77088 :   fd_bn254_fp2_t const * c0 = &b->el[0].el[0];
      71       77088 :   fd_bn254_fp2_t const * c3 = &b->el[1].el[0];
      72       77088 :   fd_bn254_fp2_t const * c4 = &b->el[1].el[1];
      73       77088 :   fd_bn254_fp6_t a0b0[1], a1b1[1], sa[1];
      74       77088 :   fd_bn254_fp2_t sc0[1];
      75             : 
      76             :   /* a0*b0 = a.el[0] * (c0, 0, 0) : 3 Fp2_mul */
      77       77088 :   fd_bn254_fp6_mul_by_fp2( a0b0, &a->el[0], c0 );
      78             : 
      79             :   /* a1*b1 = a.el[1] * (c3, c4, 0) : 5 Fp2_mul */
      80       77088 :   fd_bn254_fp6_mul_by_01( a1b1, &a->el[1], c3, c4 );
      81             : 
      82             :   /* r1 = (a0+a1) * (c0+c3, c4, 0) - a0b0 - a1b1 : 5 Fp2_mul.
      83             :      not lazy for the same reasons as fd_bn254_fp6_mul */
      84       77088 :   fd_bn254_fp6_add( sa, &a->el[0], &a->el[1] );
      85       77088 :   fd_bn254_fp2_add( sc0, c0, c3 );
      86       77088 :   fd_bn254_fp6_mul_by_01( &r->el[1], sa, sc0, c4 );
      87       77088 :   fd_bn254_fp6_sub( &r->el[1], &r->el[1], a0b0 );
      88       77088 :   fd_bn254_fp6_sub( &r->el[1], &r->el[1], a1b1 );
      89             : 
      90             :   /* r0 = a0b0 + gamma * a1b1 */
      91       77088 :   fd_bn254_fp6_mul_by_gamma( a1b1, a1b1 );
      92       77088 :   fd_bn254_fp6_add( &r->el[0], a0b0, a1b1 );
      93       77088 :   return r;
      94       77088 : }
      95             : 
      96             : fd_bn254_fp12_t *
      97             : fd_bn254_fp12_sqr( fd_bn254_fp12_t * r,
      98       24768 :                         fd_bn254_fp12_t const * a ) {
      99             :   /* https://eprint.iacr.org/2010/354, Alg. 22. */
     100       24768 :   fd_bn254_fp6_t c0[1], c2[1], c3[1];
     101       24768 :   fd_bn254_fp6_sub( c0, &a->el[0], &a->el[1] );
     102       24768 :   fd_bn254_fp6_mul_by_gamma( c3, &a->el[1] );
     103       24768 :   fd_bn254_fp6_sub( c3, &a->el[0], c3 );
     104       24768 :   fd_bn254_fp6_mul( c2, &a->el[0], &a->el[1] );
     105       24768 :   fd_bn254_fp6_mul( c0, c0, c3 );
     106       24768 :   fd_bn254_fp6_add( c0, c0, c2 );
     107       24768 :   fd_bn254_fp6_add( &r->el[1], c2, c2 );
     108       24768 :   fd_bn254_fp6_mul_by_gamma( &r->el[0], c2 );
     109       24768 :   fd_bn254_fp6_add( &r->el[0], &r->el[0], c0 );
     110       24768 :   return r;
     111       24768 : }