1 /* TomsFastMath, a fast ISO C bignum library.
3 * This project is meant to fill in where LibTomMath
4 * falls short. That is speed ;-)
6 * This project is public domain and free for all purposes.
8 * Tom St Denis, tomstdenis@gmail.com
10 #include <tfm_private.h>
12 /* setups the montgomery reduction */
13 int fp_montgomery_setup(fp_int *a, fp_digit *rho)
17 /* fast inversion mod 2**k
19 * Based on the fact that
21 * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
22 * => 2*X*A - X*X*A*A = 1
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 */
36 x *= 2 - b * x; /* here x*a==1 mod 2**64 */
39 /* rho = -1/m mod b */
40 *rho = (((fp_word) 1 << ((fp_word) DIGIT_BIT)) - ((fp_word)x));