fp_montgomery_setup.c

00001 /* TomsFastMath, a fast ISO C bignum library.
00002  * 
00003  * This project is meant to fill in where LibTomMath
00004  * falls short.  That is speed ;-)
00005  *
00006  * This project is public domain and free for all purposes.
00007  * 
00008  * Tom St Denis, tomstdenis@gmail.com
00009  */
00010 #include <tfm.h>
00011 
00012 /* setups the montgomery reduction */
00013 int fp_montgomery_setup(fp_int *a, fp_digit *rho)
00014 {
00015   fp_digit x, b;
00016 
00017 /* fast inversion mod 2**k
00018  *
00019  * Based on the fact that
00020  *
00021  * XA = 1 (mod 2**n)  =>  (X(2-XA)) A = 1 (mod 2**2n)
00022  *                    =>  2*X*A - X*X*A*A = 1
00023  *                    =>  2*(1) - (1)     = 1
00024  */
00025   b = a->dp[0];
00026 
00027   if ((b & 1) == 0) {
00028     return FP_VAL;
00029   }
00030 
00031   x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
00032   x *= 2 - b * x;               /* here x*a==1 mod 2**8 */
00033   x *= 2 - b * x;               /* here x*a==1 mod 2**16 */
00034   x *= 2 - b * x;               /* here x*a==1 mod 2**32 */
00035 #ifdef FP_64BIT
00036   x *= 2 - b * x;               /* here x*a==1 mod 2**64 */
00037 #endif
00038 
00039   /* rho = -1/m mod b */
00040   *rho = (((fp_word) 1 << ((fp_word) DIGIT_BIT)) - ((fp_word)x));
00041 
00042   return FP_OKAY;
00043 }
00044 
00045 
00046 /* $Source: /cvs/libtom/tomsfastmath/src/mont/fp_montgomery_setup.c,v $ */
00047 /* $Revision: 1.1 $ */
00048 /* $Date: 2006/12/31 21:25:53 $ */