1#include <tommath.h>
2#ifdef BN_MP_PRIME_IS_PRIME_C
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, tomstdenis@gmail.com, http://libtom.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
21
22 *
23 * Sets result to 1 if probably prime, 0 otherwise
24 */
25int 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++) {
40      if (mp_cmp_d(a, ltm_prime_tab[ix]) == MP_EQ) {
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 */
63    mp_set (&b, ltm_prime_tab[ix]);
64
65    if ((err = mp_prime_miller_rabin (a, &b, &res)) != MP_OKAY) {
66      goto LBL_B;
67    }
68
69    if (res == MP_NO) {
70      goto LBL_B;
71    }
72  }
73
74  /* passed the test */
75  *result = MP_YES;
76LBL_B:mp_clear (&b);
77  return err;
78}
79#endif
80
81/* $Source: /cvs/libtom/libtommath/bn_mp_prime_is_prime.c,v $ */
82/* $Revision: 1.4 $ */
83/* $Date: 2006/12/28 01:25:13 $ */
84