pd.if.org Git - zpackage/blob - tomsfastmath/src/mont/fp_montgomery_setup.c

   1 /* TomsFastMath, a fast ISO C bignum library.
   2  *
   3  * This project is meant to fill in where LibTomMath
   4  * falls short.  That is speed ;-)
   5  *
   6  * This project is public domain and free for all purposes.
   7  *
   8  * Tom St Denis, tomstdenis@gmail.com
   9  */
  10 #include <tfm_private.h>
  11
  12 /* setups the montgomery reduction */
  13 int fp_montgomery_setup(fp_int *a, fp_digit *rho)
  14 {
  15   fp_digit x, b;
  16
  17 /* fast inversion mod 2**k
  18  *
  19  * Based on the fact that
  20  *
  21  * XA = 1 (mod 2**n)  =>  (X(2-XA)) A = 1 (mod 2**2n)
  22  *                    =>  2*X*A - X*X*A*A = 1
  23  *                    =>  2*(1) - (1)     = 1
  24  */
  25   b = a->dp[0];
  26
  27   if ((b & 1) == 0) {
  28     return FP_VAL;
  29   }
  30
  31   x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
  32   x *= 2 - b * x;               /* here x*a==1 mod 2**8 */
  33   x *= 2 - b * x;               /* here x*a==1 mod 2**16 */
  34   x *= 2 - b * x;               /* here x*a==1 mod 2**32 */
  35 #ifdef FP_64BIT
  36   x *= 2 - b * x;               /* here x*a==1 mod 2**64 */
  37 #endif
  38
  39   /* rho = -1/m mod b */
  40   *rho = (((fp_word) 1 << ((fp_word) DIGIT_BIT)) - ((fp_word)x));
  41
  42   return FP_OKAY;
  43 }
  44
  45
  46 /* $Source$ */
  47 /* $Revision$ */
  48 /* $Date$ */