## File: bn_mp_prime_miller_rabin.c

package info (click to toggle)
libtommath 1.1.0-3
 `123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103` ``````#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. * * SPDX-License-Identifier: Unlicense */ /* 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 * very much lower. */ int mp_prime_miller_rabin(const mp_int *a, const mp_int *b, int *result) { mp_int n1, y, r; int s, j, err; /* default */ *result = MP_NO; /* ensure b > 1 */ if (mp_cmp_d(b, 1uL) != 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; } /* 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); /* 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; } /* 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 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; } } /* 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: HEAD -> master, tag: v1.1.0 */ /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */ /* commit time: 2019-01-28 20:32:32 +0100 */ ``````