release/src/router/dropbear/libtommath/bn_mp_prime_is_prime.c

   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://math.libtomcrypt.com
  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  */
  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++) {
  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;
  76 LBL_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.3 $ */
  83 /* $Date: 2006/03/31 14:18:44 $ */