merge from main

--HG--
branch : fuzz

1 files changed, 51 insertions, 89 deletions

diff --git a/libtommath/bn_mp_prime_next_prime.c b/libtommath/bn_mp_prime_next_prime.c
index 7a32d9b..d656565 100644
--- a/libtommath/bn_mp_prime_next_prime.c
+++ b/libtommath/bn_mp_prime_next_prime.c
@@ -1,70 +1,42 @@
-#include <tommath_private.h>
+#include "tommath_private.h"
 #ifdef BN_MP_PRIME_NEXT_PRIME_C
-/* LibTomMath, multiple-precision integer library -- Tom St Denis
- *
- * LibTomMath is a library that provides multiple-precision
- * integer arithmetic as well as number theoretic functionality.
- *
- * The library was designed directly after the MPI library by
- * Michael Fromberger but has been written from scratch with
- * additional optimizations in place.
- *
- * The library is free for all purposes without any express
- * guarantee it works.
- *
- * Tom St Denis, tstdenis82@gmail.com, http://libtom.org
- */
+/* LibTomMath, multiple-precision integer library -- Tom St Denis */
+/* SPDX-License-Identifier: Unlicense */
 
 /* finds the next prime after the number "a" using "t" trials
  * of Miller-Rabin.
  *
  * bbs_style = 1 means the prime must be congruent to 3 mod 4
  */
-int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
+mp_err mp_prime_next_prime(mp_int *a, int t, int bbs_style)
 {
-   int      err, res = MP_NO, x, y;
-   mp_digit res_tab[PRIME_SIZE], step, kstep;
+   int      x, y;
+   mp_ord   cmp;
+   mp_err   err;
+   mp_bool  res = MP_NO;
+   mp_digit res_tab[PRIVATE_MP_PRIME_TAB_SIZE], step, kstep;
    mp_int   b;
 
-   /* ensure t is valid */
-   if ((t <= 0) || (t > PRIME_SIZE)) {
-      return MP_VAL;
-   }
-
    /* force positive */
    a->sign = MP_ZPOS;
 
    /* simple algo if a is less than the largest prime in the table */
-   if (mp_cmp_d(a, ltm_prime_tab[PRIME_SIZE-1]) == MP_LT) {
-      /* find which prime it is bigger than */
-      for (x = PRIME_SIZE - 2; x >= 0; x--) {
-          if (mp_cmp_d(a, ltm_prime_tab[x]) != MP_LT) {
-             if (bbs_style == 1) {
-                /* ok we found a prime smaller or
-                 * equal [so the next is larger]
-                 *
-                 * however, the prime must be
-                 * congruent to 3 mod 4
-                 */
-                if ((ltm_prime_tab[x + 1] & 3) != 3) {
-                   /* scan upwards for a prime congruent to 3 mod 4 */
-                   for (y = x + 1; y < PRIME_SIZE; y++) {
-                       if ((ltm_prime_tab[y] & 3) == 3) {
-                          mp_set(a, ltm_prime_tab[y]);
-                          return MP_OKAY;
-                       }
-                   }
-                }
-             } else {
-                mp_set(a, ltm_prime_tab[x + 1]);
-                return MP_OKAY;
-             }
-          }
-      }
-      /* at this point a maybe 1 */
-      if (mp_cmp_d(a, 1) == MP_EQ) {
-         mp_set(a, 2);
-         return MP_OKAY;
+   if (mp_cmp_d(a, s_mp_prime_tab[PRIVATE_MP_PRIME_TAB_SIZE-1]) == MP_LT) {
+      /* find which prime it is bigger than "a" */
+      for (x = 0; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
+         cmp = mp_cmp_d(a, s_mp_prime_tab[x]);
+         if (cmp == MP_EQ) {
+            continue;
+         }
+         if (cmp != MP_GT) {
+            if ((bbs_style == 1) && ((s_mp_prime_tab[x] & 3u) != 3u)) {
+               /* try again until we get a prime congruent to 3 mod 4 */
+               continue;
+            } else {
+               mp_set(a, s_mp_prime_tab[x]);
+               return MP_OKAY;
+            }
+         }
       }
       /* fall through to the sieve */
    }
@@ -80,21 +52,23 @@ int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
 
    if (bbs_style == 1) {
       /* if a mod 4 != 3 subtract the correct value to make it so */
-      if ((a->dp[0] & 3) != 3) {
-         if ((err = mp_sub_d(a, (a->dp[0] & 3) + 1, a)) != MP_OKAY) { return err; };
+      if ((a->dp[0] & 3u) != 3u) {
+         if ((err = mp_sub_d(a, (a->dp[0] & 3u) + 1u, a)) != MP_OKAY) {
+            return err;
+         }
       }
    } else {
-      if (mp_iseven(a) == MP_YES) {
+      if (MP_IS_EVEN(a)) {
          /* force odd */
-         if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) {
+         if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) {
             return err;
          }
       }
    }
 
    /* generate the restable */
-   for (x = 1; x < PRIME_SIZE; x++) {
-      if ((err = mp_mod_d(a, ltm_prime_tab[x], res_tab + x)) != MP_OKAY) {
+   for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
+      if ((err = mp_mod_d(a, s_mp_prime_tab[x], res_tab + x)) != MP_OKAY) {
          return err;
       }
    }
@@ -115,43 +89,35 @@ int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
          step += kstep;
 
          /* compute the new residue without using division */
-         for (x = 1; x < PRIME_SIZE; x++) {
-             /* add the step to each residue */
-             res_tab[x] += kstep;
-
-             /* subtract the modulus [instead of using division] */
-             if (res_tab[x] >= ltm_prime_tab[x]) {
-                res_tab[x]  -= ltm_prime_tab[x];
-             }
-
-             /* set flag if zero */
-             if (res_tab[x] == 0) {
-                y = 1;
-             }
+         for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
+            /* add the step to each residue */
+            res_tab[x] += kstep;
+
+            /* subtract the modulus [instead of using division] */
+            if (res_tab[x] >= s_mp_prime_tab[x]) {
+               res_tab[x]  -= s_mp_prime_tab[x];
+            }
+
+            /* set flag if zero */
+            if (res_tab[x] == 0u) {
+               y = 1;
+            }
          }
-      } while ((y == 1) && (step < ((((mp_digit)1) << DIGIT_BIT) - kstep)));
+      } while ((y == 1) && (step < (((mp_digit)1 << MP_DIGIT_BIT) - kstep)));
 
       /* add the step */
       if ((err = mp_add_d(a, step, a)) != MP_OKAY) {
          goto LBL_ERR;
       }
 
-      /* if didn't pass sieve and step == MAX then skip test */
-      if ((y == 1) && (step >= ((((mp_digit)1) << DIGIT_BIT) - kstep))) {
+      /* if didn't pass sieve and step == MP_MAX then skip test */
+      if ((y == 1) && (step >= (((mp_digit)1 << MP_DIGIT_BIT) - kstep))) {
          continue;
       }
 
-      /* is this prime? */
-      for (x = 0; x < t; x++) {
-          mp_set(&b, ltm_prime_tab[x]);
-          if ((err = mp_prime_miller_rabin(a, &b, &res)) != MP_OKAY) {
-             goto LBL_ERR;
-          }
-          if (res == MP_NO) {
-             break;
-          }
+      if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
+         goto LBL_ERR;
       }
-
       if (res == MP_YES) {
          break;
       }
@@ -164,7 +130,3 @@ LBL_ERR:
 }
 
 #endif
-
-/* ref:         $Format:%D$ */
-/* git commit:  $Format:%H$ */
-/* commit time: $Format:%ai$ */