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       32058 :                          fd_bn254_fp2_t const *  b ) {
      12       32058 :   fd_bn254_fp2_mul( &r->el[0], &a->el[0], b );
      13       32058 :   fd_bn254_fp2_mul( &r->el[1], &a->el[1], b );
      14       32058 :   fd_bn254_fp2_mul( &r->el[2], &a->el[2], b );
      15       32058 :   return r;
      16       32058 : }
      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       63695 :                         fd_bn254_fp2_t const *  b1 ) {
      26       63695 :   fd_bn254_fp2_t const * a0 = &a->el[0];
      27       63695 :   fd_bn254_fp2_t const * a1 = &a->el[1];
      28       63695 :   fd_bn254_fp2_t const * a2 = &a->el[2];
      29       63695 :   fd_bn254_fp2_t a0b0[1], a1b1[1];
      30       63695 :   fd_bn254_fp2_t sa[1], sb[1];
      31       63695 :   fd_bn254_fp2_t r0[1], r1[1], r2[1];
      32             : 
      33       63695 :   fd_bn254_fp2_mul( a0b0, a0, b0 );
      34       63695 :   fd_bn254_fp2_mul( a1b1, a1, b1 );
      35             : 
      36             :   /* r0 = a0b0 + xi * a2*b1 */
      37       63695 :   fd_bn254_fp2_mul( r0, a2, b1 );
      38       63695 :   fd_bn254_fp2_mul_by_xi( r0, r0 );
      39       63695 :   fd_bn254_fp2_add( r0, r0, a0b0 );
      40             : 
      41             :   /* r1 = (a0+a1)*(b0+b1) - a0b0 - a1b1 */
      42       63695 :   fd_bn254_fp2_add( sa, a0, a1 );
      43       63695 :   fd_bn254_fp2_add( sb, b0, b1 );
      44       63695 :   fd_bn254_fp2_mul( r1, sa, sb );
      45       63695 :   fd_bn254_fp2_sub( r1, r1, a0b0 );
      46       63695 :   fd_bn254_fp2_sub( r1, r1, a1b1 );
      47             : 
      48             :   /* r2 = (a0+a2)*b0 - a0b0 + a1b1 */
      49       63695 :   fd_bn254_fp2_add( sa, a0, a2 );
      50       63695 :   fd_bn254_fp2_mul( r2, sa, b0 );
      51       63695 :   fd_bn254_fp2_sub( r2, r2, a0b0 );
      52       63695 :   fd_bn254_fp2_add( r2, r2, a1b1 );
      53             : 
      54       63695 :   fd_bn254_fp2_set( &r->el[0], r0 );
      55       63695 :   fd_bn254_fp2_set( &r->el[1], r1 );
      56       63695 :   fd_bn254_fp2_set( &r->el[2], r2 );
      57       63695 :   return r;
      58       63695 : }
      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       32058 :                           fd_bn254_fp12_t const * b ) {
      70       32058 :   fd_bn254_fp2_t const * c0 = &b->el[0].el[0];
      71       32058 :   fd_bn254_fp2_t const * c3 = &b->el[1].el[0];
      72       32058 :   fd_bn254_fp2_t const * c4 = &b->el[1].el[1];
      73       32058 :   fd_bn254_fp6_t a0b0[1], a1b1[1], sa[1];
      74       32058 :   fd_bn254_fp2_t sc0[1];
      75             : 
      76             :   /* a0*b0 = a.el[0] * (c0, 0, 0) : 3 Fp2_mul */
      77       32058 :   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       32058 :   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       32058 :   fd_bn254_fp6_add( sa, &a->el[0], &a->el[1] );
      85       32058 :   fd_bn254_fp2_add( sc0, c0, c3 );
      86       32058 :   fd_bn254_fp6_mul_by_01( &r->el[1], sa, sc0, c4 );
      87       32058 :   fd_bn254_fp6_sub( &r->el[1], &r->el[1], a0b0 );
      88       32058 :   fd_bn254_fp6_sub( &r->el[1], &r->el[1], a1b1 );
      89             : 
      90             :   /* r0 = a0b0 + gamma * a1b1 */
      91       32058 :   fd_bn254_fp6_mul_by_gamma( a1b1, a1b1 );
      92       32058 :   fd_bn254_fp6_add( &r->el[0], a0b0, a1b1 );
      93       32058 :   return r;
      94       32058 : }
      95             : 
      96             : fd_bn254_fp12_t *
      97             : fd_bn254_fp12_sqr( fd_bn254_fp12_t * r,
      98        5990 :                         fd_bn254_fp12_t const * a ) {
      99             :   /* https://eprint.iacr.org/2010/354, Alg. 22. */
     100        5990 :   fd_bn254_fp6_t c0[1], c2[1], c3[1];
     101        5990 :   fd_bn254_fp6_sub( c0, &a->el[0], &a->el[1] );
     102        5990 :   fd_bn254_fp6_mul_by_gamma( c3, &a->el[1] );
     103        5990 :   fd_bn254_fp6_sub( c3, &a->el[0], c3 );
     104        5990 :   fd_bn254_fp6_mul( c2, &a->el[0], &a->el[1] );
     105        5990 :   fd_bn254_fp6_mul( c0, c0, c3 );
     106        5990 :   fd_bn254_fp6_add( c0, c0, c2 );
     107        5990 :   fd_bn254_fp6_add( &r->el[1], c2, c2 );
     108        5990 :   fd_bn254_fp6_mul_by_gamma( &r->el[0], c2 );
     109        5990 :   fd_bn254_fp6_add( &r->el[0], &r->el[0], c0 );
     110        5990 :   return r;
     111        5990 : }