Mercurial > dropbear
annotate bn_mp_prime_fermat.c @ 203:e109027b9edf libtommath LTM_DB_0.46 LTM_DB_0.47
Don't remove ~ files on make clean (and find -type was wrong anyway)
| author | Matt Johnston <matt@ucc.asn.au> |
|---|---|
| date | Wed, 11 May 2005 16:27:28 +0000 |
| parents | d8254fc979e9 |
| children |
| rev | line source |
|---|---|
| 142 | 1 #include <tommath.h> |
| 2 #ifdef BN_MP_PRIME_FERMAT_C | |
| 2 | 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis |
| 4 * | |
| 5 * LibTomMath is a library that provides multiple-precision | |
| 6 * integer arithmetic as well as number theoretic functionality. | |
| 7 * | |
| 8 * The library was designed directly after the MPI library by | |
| 9 * Michael Fromberger but has been written from scratch with | |
| 10 * additional optimizations in place. | |
| 11 * | |
| 12 * The library is free for all purposes without any express | |
| 13 * guarantee it works. | |
| 14 * | |
| 15 * Tom St Denis, [email protected], http://math.libtomcrypt.org | |
| 16 */ | |
| 17 | |
| 18 /* performs one Fermat test. | |
| 19 * | |
| 20 * If "a" were prime then b**a == b (mod a) since the order of | |
| 21 * the multiplicative sub-group would be phi(a) = a-1. That means | |
| 22 * it would be the same as b**(a mod (a-1)) == b**1 == b (mod a). | |
| 23 * | |
| 24 * Sets result to 1 if the congruence holds, or zero otherwise. | |
| 25 */ | |
| 26 int mp_prime_fermat (mp_int * a, mp_int * b, int *result) | |
| 27 { | |
| 28 mp_int t; | |
| 29 int err; | |
| 30 | |
| 31 /* default to composite */ | |
| 32 *result = MP_NO; | |
| 33 | |
| 34 /* ensure b > 1 */ | |
| 35 if (mp_cmp_d(b, 1) != MP_GT) { | |
| 36 return MP_VAL; | |
| 37 } | |
| 38 | |
| 39 /* init t */ | |
| 40 if ((err = mp_init (&t)) != MP_OKAY) { | |
| 41 return err; | |
| 42 } | |
| 43 | |
| 44 /* compute t = b**a mod a */ | |
| 45 if ((err = mp_exptmod (b, a, a, &t)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
46 goto LBL_T; |
| 2 | 47 } |
| 48 | |
| 49 /* is it equal to b? */ | |
| 50 if (mp_cmp (&t, b) == MP_EQ) { | |
| 51 *result = MP_YES; | |
| 52 } | |
| 53 | |
| 54 err = MP_OKAY; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
55 LBL_T:mp_clear (&t); |
| 2 | 56 return err; |
| 57 } | |
| 142 | 58 #endif |