### diff libtommath/bn_mp_prime_next_prime.c @ 1656:a36e545fb43d

Prime-related bugfixes (#81) * Merge pull request #180 from czurnieden/isprimeerror Fixed bug in mp_prime_isprime (cherry picked from commit f3ff7064f3301a2fc11b84d389fd67769862d437) * do 2 MR rounds for numbers >=2048bits * back-port modified mp_prime_next_prime()
author Steffen Jaeckel Tue, 17 Sep 2019 16:11:09 +0200 f52919ffd3b1 1051e4eea25a
line wrap: on
line diff
```--- a/libtommath/bn_mp_prime_next_prime.c	Mon Sep 16 15:50:38 2019 +0200
+++ b/libtommath/bn_mp_prime_next_prime.c	Tue Sep 17 16:11:09 2019 +0200
@@ -19,7 +19,7 @@
*/
int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
{
-   int      err, res = MP_NO, x, y;
+   int      err, res = MP_NO, x, y, cmp;
mp_digit res_tab[PRIME_SIZE], step, kstep;
mp_int   b;

@@ -28,36 +28,22 @@

/* 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] & 3u) != 3u) {
-                  /* scan upwards for a prime congruent to 3 mod 4 */
-                  for (y = x + 1; y < PRIME_SIZE; y++) {
-                     if ((ltm_prime_tab[y] & 3u) == 3u) {
-                        mp_set(a, ltm_prime_tab[y]);
-                        return MP_OKAY;
-                     }
-                  }
-               }
+      /* find which prime it is bigger than "a" */
+      for (x = 0; x < PRIME_SIZE; x++) {
+         cmp = mp_cmp_d(a, ltm_prime_tab[x]);
+         if (cmp == MP_EQ) {
+            continue;
+         }
+         if (cmp != MP_GT) {
+            if ((bbs_style == 1) && ((ltm_prime_tab[x] & 3u) != 3u)) {
+               /* try again until we get a prime congruent to 3 mod 4 */
+               continue;
} else {
-               mp_set(a, ltm_prime_tab[x + 1]);
+               mp_set(a, ltm_prime_tab[x]);
return MP_OKAY;
}
}
}
-      /* at this point a maybe 1 */
-      if (mp_cmp_d(a, 1uL) == MP_EQ) {
-         mp_set(a, 2uL);
-         return MP_OKAY;
-      }
/* fall through to the sieve */
}

@@ -75,7 +61,7 @@
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) {```