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()

1 files changed, 13 insertions, 27 deletions

diff --git a/libtommath/bn_mp_prime_next_prime.c b/libtommath/bn_mp_prime_next_prime.c
index ad4c2e3..3592c86 100644
--- a/libtommath/bn_mp_prime_next_prime.c
+++ b/libtommath/bn_mp_prime_next_prime.c
@@ -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 @@ int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
 
    /* 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 @@ int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
       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) {