diff libtommath/bn_mp_prime_next_prime.c @ 1655:f52919ffd3b1

update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) * make key-generation compliant to FIPS 186.4 * fix includes in tommath_class.h * update fuzzcorpus instead of error-out * fixup fuzzing make-targets * update Makefile.in * apply necessary patches to ltm sources * clean-up not required ltm files * update to vanilla ltm 1.1.0 this already only contains the required files * remove set/get double
author Steffen Jaeckel <s_jaeckel@gmx.de>
date Mon, 16 Sep 2019 15:50:38 +0200
parents 8bba51a55704
children a36e545fb43d
line wrap: on
line diff
--- a/libtommath/bn_mp_prime_next_prime.c	Wed May 15 21:59:45 2019 +0800
+++ b/libtommath/bn_mp_prime_next_prime.c	Mon Sep 16 15:50:38 2019 +0200
@@ -1,4 +1,4 @@
-#include <tommath_private.h>
+#include "tommath_private.h"
 #ifdef BN_MP_PRIME_NEXT_PRIME_C
 /* LibTomMath, multiple-precision integer library -- Tom St Denis
  *
@@ -9,10 +9,7 @@
  * 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, [email protected], http://libtom.org
+ * SPDX-License-Identifier: Unlicense
  */
 
 /* finds the next prime after the number "a" using "t" trials
@@ -26,11 +23,6 @@
    mp_digit res_tab[PRIME_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;
 
@@ -38,32 +30,32 @@
    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;
-             }
-          }
+         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;
+                     }
+                  }
+               }
+            } 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);
+      if (mp_cmp_d(a, 1uL) == MP_EQ) {
+         mp_set(a, 2uL);
          return MP_OKAY;
       }
       /* fall through to the sieve */
@@ -80,13 +72,15 @@
 
    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) {
          /* force odd */
-         if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) {
+         if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) {
             return err;
          }
       }
@@ -116,20 +110,20 @@
 
          /* compute the new residue without using division */
          for (x = 1; x < PRIME_SIZE; x++) {
-             /* add the step to each residue */
-             res_tab[x] += kstep;
+            /* 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];
-             }
+            /* 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;
-             }
+            /* 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 << DIGIT_BIT) - kstep)));
 
       /* add the step */
       if ((err = mp_add_d(a, step, a)) != MP_OKAY) {
@@ -137,21 +131,13 @@
       }
 
       /* if didn't pass sieve and step == MAX then skip test */
-      if ((y == 1) && (step >= ((((mp_digit)1) << DIGIT_BIT) - kstep))) {
+      if ((y == 1) && (step >= (((mp_digit)1 << 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;
       }
@@ -165,6 +151,6 @@
 
 #endif
 
-/* ref:         $Format:%D$ */
-/* git commit:  $Format:%H$ */
-/* commit time: $Format:%ai$ */
+/* ref:         HEAD -> master, tag: v1.1.0 */
+/* git commit:  08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
+/* commit time: 2019-01-28 20:32:32 +0100 */