diff libtommath/bn_mp_prime_miller_rabin.c @ 1739:13d834efc376 fuzz

merge from main
author Matt Johnston <matt@ucc.asn.au>
date Thu, 15 Oct 2020 19:55:15 +0800
parents 1051e4eea25a
children
line wrap: on
line diff
--- a/libtommath/bn_mp_prime_miller_rabin.c	Wed Feb 28 22:11:39 2018 +0800
+++ b/libtommath/bn_mp_prime_miller_rabin.c	Thu Oct 15 19:55:15 2020 +0800
@@ -1,103 +1,91 @@
-#include <tommath_private.h>
+#include "tommath_private.h"
 #ifdef BN_MP_PRIME_MILLER_RABIN_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, [email protected], http://libtom.org
- */
+/* LibTomMath, multiple-precision integer library -- Tom St Denis */
+/* SPDX-License-Identifier: Unlicense */
 
-/* Miller-Rabin test of "a" to the base of "b" as described in 
+/* Miller-Rabin test of "a" to the base of "b" as described in
  * HAC pp. 139 Algorithm 4.24
  *
  * Sets result to 0 if definitely composite or 1 if probably prime.
- * Randomly the chance of error is no more than 1/4 and often 
+ * Randomly the chance of error is no more than 1/4 and often
  * very much lower.
  */
-int mp_prime_miller_rabin (mp_int * a, mp_int * b, int *result)
+mp_err mp_prime_miller_rabin(const mp_int *a, const mp_int *b, mp_bool *result)
 {
-  mp_int  n1, y, r;
-  int     s, j, err;
+   mp_int  n1, y, r;
+   mp_err  err;
+   int     s, j;
 
-  /* default */
-  *result = MP_NO;
+   /* default */
+   *result = MP_NO;
+
+   /* ensure b > 1 */
+   if (mp_cmp_d(b, 1uL) != MP_GT) {
+      return MP_VAL;
+   }
 
-  /* ensure b > 1 */
-  if (mp_cmp_d(b, 1) != MP_GT) {
-     return MP_VAL;
-  }     
+   /* get n1 = a - 1 */
+   if ((err = mp_init_copy(&n1, a)) != MP_OKAY) {
+      return err;
+   }
+   if ((err = mp_sub_d(&n1, 1uL, &n1)) != MP_OKAY) {
+      goto LBL_N1;
+   }
 
-  /* get n1 = a - 1 */
-  if ((err = mp_init_copy (&n1, a)) != MP_OKAY) {
-    return err;
-  }
-  if ((err = mp_sub_d (&n1, 1, &n1)) != MP_OKAY) {
-    goto LBL_N1;
-  }
+   /* set 2**s * r = n1 */
+   if ((err = mp_init_copy(&r, &n1)) != MP_OKAY) {
+      goto LBL_N1;
+   }
+
+   /* count the number of least significant bits
+    * which are zero
+    */
+   s = mp_cnt_lsb(&r);
 
-  /* set 2**s * r = n1 */
-  if ((err = mp_init_copy (&r, &n1)) != MP_OKAY) {
-    goto LBL_N1;
-  }
+   /* now divide n - 1 by 2**s */
+   if ((err = mp_div_2d(&r, s, &r, NULL)) != MP_OKAY) {
+      goto LBL_R;
+   }
 
-  /* count the number of least significant bits
-   * which are zero
-   */
-  s = mp_cnt_lsb(&r);
-
-  /* now divide n - 1 by 2**s */
-  if ((err = mp_div_2d (&r, s, &r, NULL)) != MP_OKAY) {
-    goto LBL_R;
-  }
+   /* compute y = b**r mod a */
+   if ((err = mp_init(&y)) != MP_OKAY) {
+      goto LBL_R;
+   }
+   if ((err = mp_exptmod(b, &r, a, &y)) != MP_OKAY) {
+      goto LBL_Y;
+   }
 
-  /* compute y = b**r mod a */
-  if ((err = mp_init (&y)) != MP_OKAY) {
-    goto LBL_R;
-  }
-  if ((err = mp_exptmod (b, &r, a, &y)) != MP_OKAY) {
-    goto LBL_Y;
-  }
+   /* if y != 1 and y != n1 do */
+   if ((mp_cmp_d(&y, 1uL) != MP_EQ) && (mp_cmp(&y, &n1) != MP_EQ)) {
+      j = 1;
+      /* while j <= s-1 and y != n1 */
+      while ((j <= (s - 1)) && (mp_cmp(&y, &n1) != MP_EQ)) {
+         if ((err = mp_sqrmod(&y, a, &y)) != MP_OKAY) {
+            goto LBL_Y;
+         }
 
-  /* if y != 1 and y != n1 do */
-  if ((mp_cmp_d (&y, 1) != MP_EQ) && (mp_cmp (&y, &n1) != MP_EQ)) {
-    j = 1;
-    /* while j <= s-1 and y != n1 */
-    while ((j <= (s - 1)) && (mp_cmp (&y, &n1) != MP_EQ)) {
-      if ((err = mp_sqrmod (&y, a, &y)) != MP_OKAY) {
+         /* if y == 1 then composite */
+         if (mp_cmp_d(&y, 1uL) == MP_EQ) {
+            goto LBL_Y;
+         }
+
+         ++j;
+      }
+
+      /* if y != n1 then composite */
+      if (mp_cmp(&y, &n1) != MP_EQ) {
          goto LBL_Y;
       }
-
-      /* if y == 1 then composite */
-      if (mp_cmp_d (&y, 1) == MP_EQ) {
-         goto LBL_Y;
-      }
-
-      ++j;
-    }
+   }
 
-    /* if y != n1 then composite */
-    if (mp_cmp (&y, &n1) != MP_EQ) {
-      goto LBL_Y;
-    }
-  }
-
-  /* probably prime now */
-  *result = MP_YES;
-LBL_Y:mp_clear (&y);
-LBL_R:mp_clear (&r);
-LBL_N1:mp_clear (&n1);
-  return err;
+   /* probably prime now */
+   *result = MP_YES;
+LBL_Y:
+   mp_clear(&y);
+LBL_R:
+   mp_clear(&r);
+LBL_N1:
+   mp_clear(&n1);
+   return err;
 }
 #endif
-
-/* ref:         $Format:%D$ */
-/* git commit:  $Format:%H$ */
-/* commit time: $Format:%ai$ */