fp_montgomery_calc_normalization.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 /* computes a = B**n mod b without division or multiplication useful for
00013  * normalizing numbers in a Montgomery system.
00014  */
00015 void fp_montgomery_calc_normalization(fp_int *a, fp_int *b)
00016 {
00017   int     x, bits;
00018 
00019   /* how many bits of last digit does b use */
00020   bits = fp_count_bits (b) % DIGIT_BIT;
00021   if (!bits) bits = DIGIT_BIT;
00022 
00023   /* compute A = B^(n-1) * 2^(bits-1) */
00024   if (b->used > 1) {
00025      fp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1);
00026   } else {
00027      fp_set(a, 1);
00028      bits = 1;
00029   }
00030 
00031   /* now compute C = A * B mod b */
00032   for (x = bits - 1; x < (int)DIGIT_BIT; x++) {
00033     fp_mul_2 (a, a);
00034     if (fp_cmp_mag (a, b) != FP_LT) {
00035       s_fp_sub (a, b, a);
00036     }
00037   }
00038 }
00039 
00040 
00041 /* $Source: /cvs/libtom/tomsfastmath/src/mont/fp_montgomery_calc_normalization.c,v $ */
00042 /* $Revision: 1.1 $ */
00043 /* $Date: 2006/12/31 21:25:53 $ */