Line data    Source code

       1             : #include "fd_f25519.h"
       2             : #include "../hex/fd_hex.h"
       3             : 
       4             : #if FD_HAS_AVX512
       5             : #include "avx512/fd_f25519.c"
       6             : #else
       7             : #include "ref/fd_f25519.c"
       8             : #endif
       9             : 
      10             : /* fd_f25519_pow22523 computes r = a^(2^252-3), and returns r. */
      11             : fd_f25519_t *
      12             : fd_f25519_pow22523( fd_f25519_t *       r,
      13     2136267 :                     fd_f25519_t const * a ) {
      14     2136267 :   fd_f25519_t t0[1];
      15     2136267 :   fd_f25519_t t1[1];
      16     2136267 :   fd_f25519_t t2[1];
      17             : 
      18     2136267 :   fd_f25519_sqr( t0, a      );
      19     2136267 :   fd_f25519_sqr( t1, t0     );
      20     4272534 :   for( int i=1; i<  2; i++ ) fd_f25519_sqr( t1, t1 );
      21             : 
      22     2136267 :   fd_f25519_mul( t1, a,  t1 );
      23     2136267 :   fd_f25519_mul( t0, t0, t1 );
      24     2136267 :   fd_f25519_sqr( t0, t0     );
      25     2136267 :   fd_f25519_mul( t0, t1, t0 );
      26     2136267 :   fd_f25519_sqr( t1, t0     );
      27    10681335 :   for( int i=1; i<  5; i++ ) fd_f25519_sqr( t1, t1 );
      28             : 
      29     2136267 :   fd_f25519_mul( t0, t1, t0 );
      30     2136267 :   fd_f25519_sqr( t1, t0     );
      31    21362670 :   for( int i=1; i< 10; i++ ) fd_f25519_sqr( t1, t1 );
      32             : 
      33     2136267 :   fd_f25519_mul( t1, t1, t0 );
      34     2136267 :   fd_f25519_sqr( t2, t1     );
      35    42725340 :   for( int i=1; i< 20; i++ ) fd_f25519_sqr( t2, t2 );
      36             : 
      37     2136267 :   fd_f25519_mul( t1, t2, t1 );
      38     2136267 :   fd_f25519_sqr( t1, t1     );
      39    21362670 :   for( int i=1; i< 10; i++ ) fd_f25519_sqr( t1, t1 );
      40             : 
      41     2136267 :   fd_f25519_mul( t0, t1, t0 );
      42     2136267 :   fd_f25519_sqr( t1, t0     );
      43   106813350 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t1, t1 );
      44             : 
      45     2136267 :   fd_f25519_mul( t1, t1, t0 );
      46     2136267 :   fd_f25519_sqr( t2, t1     );
      47   213626700 :   for( int i=1; i<100; i++ ) fd_f25519_sqr( t2, t2 );
      48             : 
      49     2136267 :   fd_f25519_mul( t1, t2, t1 );
      50     2136267 :   fd_f25519_sqr( t1, t1     );
      51   106813350 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t1, t1 );
      52             : 
      53     2136267 :   fd_f25519_mul( t0, t1, t0 );
      54     2136267 :   fd_f25519_sqr( t0, t0     );
      55     4272534 :   for( int i=1; i<  2; i++ ) fd_f25519_sqr( t0, t0 );
      56             : 
      57     2136267 :   fd_f25519_mul(r, t0, a  );
      58     2136267 :   return r;
      59     2136267 : }
      60             : 
      61             : /* fd_f25519_inv computes r = 1/a, and returns r. */
      62             : fd_f25519_t *
      63             : fd_f25519_inv( fd_f25519_t *       r,
      64     1986942 :                fd_f25519_t const * a ) {
      65     1986942 :   fd_f25519_t t0[1];
      66     1986942 :   fd_f25519_t t1[1];
      67     1986942 :   fd_f25519_t t2[1];
      68     1986942 :   fd_f25519_t t3[1];
      69             : 
      70             :   /* Compute z**-1 = z**(2**255 - 19 - 2) with the exponent as
      71             :      2**255 - 21 = (2**5) * (2**250 - 1) + 11. */
      72             : 
      73     1986942 :   fd_f25519_sqr( t0,  a     );                        /* t0 = z**2 */
      74     1986942 :   fd_f25519_sqr( t1, t0     );
      75     1986942 :   fd_f25519_sqr( t1, t1     );                        /* t1 = t0**(2**2) = z**8 */
      76     1986942 :   fd_f25519_mul( t1,  a, t1 );                        /* t1 = z * t1 = z**9 */
      77     1986942 :   fd_f25519_mul( t0, t0, t1 );                        /* t0 = t0 * t1 = z**11 -- stash t0 away for the end. */
      78     1986942 :   fd_f25519_sqr( t2, t0     );                        /* t2 = t0**2 = z**22 */
      79     1986942 :   fd_f25519_mul( t1, t1, t2 );                        /* t1 = t1 * t2 = z**(2**5 - 1) */
      80     1986942 :   fd_f25519_sqr( t2, t1     );
      81     9934710 :   for( int i=1; i<  5; i++ ) fd_f25519_sqr( t2, t2 ); /* t2 = t1**(2**5) = z**((2**5) * (2**5 - 1)) */
      82     1986942 :   fd_f25519_mul( t1, t2, t1 );                        /* t1 = t1 * t2 = z**((2**5 + 1) * (2**5 - 1)) = z**(2**10 - 1) */
      83     1986942 :   fd_f25519_sqr( t2, t1     );
      84    19869420 :   for( int i=1; i< 10; i++ ) fd_f25519_sqr( t2, t2 );
      85     1986942 :   fd_f25519_mul( t2, t2, t1 );                        /* t2 = z**(2**20 - 1) */
      86     1986942 :   fd_f25519_sqr( t3, t2     );
      87    39738840 :   for( int i=1; i< 20; i++ ) fd_f25519_sqr( t3, t3 );
      88     1986942 :   fd_f25519_mul( t2, t3, t2 );                        /* t2 = z**(2**40 - 1) */
      89    21856362 :   for( int i=0; i< 10; i++ ) fd_f25519_sqr( t2, t2 ); /* t2 = z**(2**10) * (2**40 - 1) */
      90     1986942 :   fd_f25519_mul( t1, t2, t1 );                        /* t1 = z**(2**50 - 1) */
      91     1986942 :   fd_f25519_sqr( t2, t1     );
      92    99347100 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t2, t2 );
      93     1986942 :   fd_f25519_mul( t2, t2, t1 );                        /* t2 = z**(2**100 - 1) */
      94     1986942 :   fd_f25519_sqr( t3, t2     );
      95   198694200 :   for( int i=1; i<100; i++ ) fd_f25519_sqr( t3, t3 );
      96     1986942 :   fd_f25519_mul( t2, t3, t2 );                        /* t2 = z**(2**200 - 1) */
      97     1986942 :   fd_f25519_sqr( t2, t2     );
      98    99347100 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t2, t2 ); /* t2 = z**((2**50) * (2**200 - 1) */
      99     1986942 :   fd_f25519_mul( t1, t2, t1 );                        /* t1 = z**(2**250 - 1) */
     100     1986942 :   fd_f25519_sqr( t1, t1     );
     101     9934710 :   for( int i=1; i<  5; i++ ) fd_f25519_sqr( t1, t1 ); /* t1 = z**((2**5) * (2**250 - 1)) */
     102     1986942 :   return fd_f25519_mul( r, t1, t0 );                  /* Recall t0 = z**11; out = z**(2**255 - 21) */
     103     1986942 : }
     104             : 
     105             : /* fd_f25519_sqrt_ratio computes r = (u * v^3) * (u * v^7)^((p-5)/8),
     106             :    returns 0 on success, 1 on failure. */
     107             : int
     108             : fd_f25519_sqrt_ratio( fd_f25519_t *       r,
     109             :                       fd_f25519_t const * u,
     110     1836267 :                       fd_f25519_t const * v ) {
     111             :   /* r = (u * v^3) * (u * v^7)^((p-5)/8) */
     112     1836267 :   fd_f25519_t  v2[1]; fd_f25519_sqr(  v2, v      );
     113     1836267 :   fd_f25519_t  v3[1]; fd_f25519_mul(  v3, v2, v  );
     114     1836267 :   fd_f25519_t uv3[1]; fd_f25519_mul( uv3, u,  v3 );
     115     1836267 :   fd_f25519_t  v6[1]; fd_f25519_sqr(  v6, v3     );
     116     1836267 :   fd_f25519_t  v7[1]; fd_f25519_mul(  v7, v6, v  );
     117     1836267 :   fd_f25519_t uv7[1]; fd_f25519_mul( uv7, u,  v7 );
     118     1836267 :   fd_f25519_pow22523( r, uv7    );
     119     1836267 :   fd_f25519_mul     ( r, r, uv3 );
     120             : 
     121             :   /* check = v * r^2 */
     122     1836267 :   fd_f25519_t check[1];
     123     1836267 :   fd_f25519_sqr( check, r        );
     124     1836267 :   fd_f25519_mul( check, check, v );
     125             : 
     126             :   /* (correct_sign_sqrt)    check == u
     127             :      (flipped_sign_sqrt)    check == !u
     128             :      (flipped_sign_sqrt_i)  check == (!u * SQRT_M1) */
     129     1836267 :   fd_f25519_t u_neg[1];        fd_f25519_neg( u_neg,        u );
     130     1836267 :   fd_f25519_t u_neg_sqrtm1[1]; fd_f25519_mul( u_neg_sqrtm1, u_neg, fd_f25519_sqrtm1 );
     131     1836267 :   int correct_sign_sqrt   = fd_f25519_eq( check, u );
     132     1836267 :   int flipped_sign_sqrt   = fd_f25519_eq( check, u_neg );
     133     1836267 :   int flipped_sign_sqrt_i = fd_f25519_eq( check, u_neg_sqrtm1 );
     134             : 
     135             :   /* r_prime = SQRT_M1 * r */
     136     1836267 :   fd_f25519_t r_prime[1];
     137     1836267 :   fd_f25519_mul( r_prime, r, fd_f25519_sqrtm1 );
     138             : 
     139             :   /* r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r) */
     140     1836267 :   fd_f25519_if( r, flipped_sign_sqrt|flipped_sign_sqrt_i, r_prime, r );
     141     1836267 :   fd_f25519_abs( r, r );
     142     1836267 :   return correct_sign_sqrt|flipped_sign_sqrt;
     143     1836267 : }