userapps/opensource/sshd/libtommath/bn_mp_prime_next_prime.c

   1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   2  *
   3  * LibTomMath is library that provides for multiple-precision
   4  * integer arithmetic as well as number theoretic functionality.
   5  *
   6  * The library is 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, tomstdenis@iahu.ca, http://math.libtomcrypt.org
  14  */
  15 #include <tommath.h>
  16
  17 /* finds the next prime after the number "a" using "t" trials
  18  * of Miller-Rabin.
  19  */
  20 int mp_prime_next_prime(mp_int *a, int t)
  21 {
  22    int err, res;
  23
  24    if (mp_iseven(a) == 1) {
  25       /* force odd */
  26       if ((err = mp_add_d(a, 1, a)) != MP_OKAY) {
  27          return err;
  28       }
  29    } else {
  30       /* force to next odd number */
  31       if ((err = mp_add_d(a, 2, a)) != MP_OKAY) {
  32          return err;
  33       }
  34    }
  35
  36    for (;;) {
  37       /* is this prime? */
  38       if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
  39          return err;
  40       }
  41
  42       if (res == 1) {
  43          break;
  44       }
  45
  46       /* add two, next candidate */
  47       if ((err = mp_add_d(a, 2, a)) != MP_OKAY) {
  48          return err;
  49       }
  50    }
  51
  52    return MP_OKAY;
  53 }
  54