Mercurial > dropbear
annotate bn_mp_prime_is_prime.c @ 201:c0bf626ee437 libtommath
Bringing back the original ltc 0.35 makefile
| author | Matt Johnston <matt@ucc.asn.au> |
|---|---|
| date | Wed, 11 May 2005 16:23:24 +0000 |
| parents | d8254fc979e9 |
| children |
| rev | line source |
|---|---|
| 142 | 1 #include <tommath.h> |
| 2 #ifdef BN_MP_PRIME_IS_PRIME_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 a variable number of rounds of Miller-Rabin | |
| 19 * | |
| 20 * Probability of error after t rounds is no more than | |
| 142 | 21 |
| 2 | 22 * |
| 23 * Sets result to 1 if probably prime, 0 otherwise | |
| 24 */ | |
| 25 int mp_prime_is_prime (mp_int * a, int t, int *result) | |
| 26 { | |
| 27 mp_int b; | |
| 28 int ix, err, res; | |
| 29 | |
| 30 /* default to no */ | |
| 31 *result = MP_NO; | |
| 32 | |
| 33 /* valid value of t? */ | |
| 34 if (t <= 0 || t > PRIME_SIZE) { | |
| 35 return MP_VAL; | |
| 36 } | |
| 37 | |
| 38 /* is the input equal to one of the primes in the table? */ | |
| 39 for (ix = 0; ix < PRIME_SIZE; ix++) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
40 if (mp_cmp_d(a, ltm_prime_tab[ix]) == MP_EQ) { |
| 2 | 41 *result = 1; |
| 42 return MP_OKAY; | |
| 43 } | |
| 44 } | |
| 45 | |
| 46 /* first perform trial division */ | |
| 47 if ((err = mp_prime_is_divisible (a, &res)) != MP_OKAY) { | |
| 48 return err; | |
| 49 } | |
| 50 | |
| 51 /* return if it was trivially divisible */ | |
| 52 if (res == MP_YES) { | |
| 53 return MP_OKAY; | |
| 54 } | |
| 55 | |
| 56 /* now perform the miller-rabin rounds */ | |
| 57 if ((err = mp_init (&b)) != MP_OKAY) { | |
| 58 return err; | |
| 59 } | |
| 60 | |
| 61 for (ix = 0; ix < t; ix++) { | |
| 62 /* set the prime */ | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
63 mp_set (&b, ltm_prime_tab[ix]); |
| 2 | 64 |
| 65 if ((err = mp_prime_miller_rabin (a, &b, &res)) != MP_OKAY) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
66 goto LBL_B; |
| 2 | 67 } |
| 68 | |
| 69 if (res == MP_NO) { | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
70 goto LBL_B; |
| 2 | 71 } |
| 72 } | |
| 73 | |
| 74 /* passed the test */ | |
| 75 *result = MP_YES; | |
|
190
d8254fc979e9
Initial import of libtommath 0.35
Matt Johnston <matt@ucc.asn.au>
parents:
142
diff
changeset
|
76 LBL_B:mp_clear (&b); |
| 2 | 77 return err; |
| 78 } | |
| 142 | 79 #endif |