Mercurial > dropbear

comparison bn_mp_prime_is_prime.c @ 2:86e0b50a9b58 libtommath-orig ltm-0.30-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ltm 0.30 orig import
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:25:22 +0000
parents
children d29b64170cf0
comparison
equal deleted inserted replaced
-1:000000000000 2:86e0b50a9b58
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2 *
3 * LibTomMath is a library that provides multiple-precision
4 * integer arithmetic as well as number theoretic functionality.
5 *
6 * The library was designed directly after the MPI library by
7 * Michael Fromberger but has been written from scratch with
8 * additional optimizations in place.
9 *
10 * The library is free for all purposes without any express
11 * guarantee it works.
12 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org
14 */
15 #include <tommath.h>
16
17 /* performs a variable number of rounds of Miller-Rabin
18 *
19 * Probability of error after t rounds is no more than
20 * (1/4)^t when 1 <= t <= PRIME_SIZE
21 *
22 * Sets result to 1 if probably prime, 0 otherwise
23 */
24 int mp_prime_is_prime (mp_int * a, int t, int *result)
25 {
26 mp_int b;
27 int ix, err, res;
28
29 /* default to no */
30 *result = MP_NO;
31
32 /* valid value of t? */
33 if (t <= 0 || t > PRIME_SIZE) {
34 return MP_VAL;
35 }
36
37 /* is the input equal to one of the primes in the table? */
38 for (ix = 0; ix < PRIME_SIZE; ix++) {
39 if (mp_cmp_d(a, __prime_tab[ix]) == MP_EQ) {
40 *result = 1;
41 return MP_OKAY;
42 }
43 }
44
45 /* first perform trial division */
46 if ((err = mp_prime_is_divisible (a, &res)) != MP_OKAY) {
47 return err;
48 }
49
50 /* return if it was trivially divisible */
51 if (res == MP_YES) {
52 return MP_OKAY;
53 }
54
55 /* now perform the miller-rabin rounds */
56 if ((err = mp_init (&b)) != MP_OKAY) {
57 return err;
58 }
59
60 for (ix = 0; ix < t; ix++) {
61 /* set the prime */
62 mp_set (&b, __prime_tab[ix]);
63
64 if ((err = mp_prime_miller_rabin (a, &b, &res)) != MP_OKAY) {
65 goto __B;
66 }
67
68 if (res == MP_NO) {
69 goto __B;
70 }
71 }
72
73 /* passed the test */
74 *result = MP_YES;
75 __B:mp_clear (&b);
76 return err;
77 }