Mercurial > dropbear
comparison tomsfastmath/src/mont/fp_montgomery_calc_normalization.c @ 643:a362b62d38b2 dropbear-tfm
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a
with Makefile.in renamed
| author | Matt Johnston <matt@ucc.asn.au> |
|---|---|
| date | Wed, 23 Nov 2011 18:10:20 +0700 |
| parents | |
| children |
comparison
equal
deleted
inserted
replaced
| 642:33fd2f3499d2 | 643:a362b62d38b2 |
|---|---|
| 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, [email protected] | |
| 9 */ | |
| 10 #include <tfm.h> | |
| 11 | |
| 12 /* computes a = B**n mod b without division or multiplication useful for | |
| 13 * normalizing numbers in a Montgomery system. | |
| 14 */ | |
| 15 void fp_montgomery_calc_normalization(fp_int *a, fp_int *b) | |
| 16 { | |
| 17 int x, bits; | |
| 18 | |
| 19 /* how many bits of last digit does b use */ | |
| 20 bits = fp_count_bits (b) % DIGIT_BIT; | |
| 21 if (!bits) bits = DIGIT_BIT; | |
| 22 | |
| 23 /* compute A = B^(n-1) * 2^(bits-1) */ | |
| 24 if (b->used > 1) { | |
| 25 fp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1); | |
| 26 } else { | |
| 27 fp_set(a, 1); | |
| 28 bits = 1; | |
| 29 } | |
| 30 | |
| 31 /* now compute C = A * B mod b */ | |
| 32 for (x = bits - 1; x < (int)DIGIT_BIT; x++) { | |
| 33 fp_mul_2 (a, a); | |
| 34 if (fp_cmp_mag (a, b) != FP_LT) { | |
| 35 s_fp_sub (a, b, a); | |
| 36 } | |
| 37 } | |
| 38 } | |
| 39 | |
| 40 | |
| 41 /* $Source$ */ | |
| 42 /* $Revision$ */ | |
| 43 /* $Date$ */ |