### view 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 source
```#include "tommath_private.h"
#ifdef BN_MP_PRIME_NEXT_PRIME_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
*
*/

/* finds the next prime after the number "a" using "t" trials
* of Miller-Rabin.
*
* bbs_style = 1 means the prime must be congruent to 3 mod 4
*/
int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
{
int      err, res = MP_NO, x, y, cmp;
mp_digit res_tab[PRIME_SIZE], step, kstep;
mp_int   b;

/* force positive */
a->sign = MP_ZPOS;

/* 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 "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]);
return MP_OKAY;
}
}
}
/* fall through to the sieve */
}

/* generate a prime congruent to 3 mod 4 or 1/3 mod 4? */
if (bbs_style == 1) {
kstep   = 4;
} else {
kstep   = 2;
}

/* at this point we will use a combination of a sieve and Miller-Rabin */

if (bbs_style == 1) {
/* if a mod 4 != 3 subtract the correct value to make it so */
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, 1uL, a)) != MP_OKAY) {
return err;
}
}
}

/* generate the restable */
for (x = 1; x < PRIME_SIZE; x++) {
if ((err = mp_mod_d(a, ltm_prime_tab[x], res_tab + x)) != MP_OKAY) {
return err;
}
}

/* init temp used for Miller-Rabin Testing */
if ((err = mp_init(&b)) != MP_OKAY) {
return err;
}

for (;;) {
step = 0;
do {
/* y == 1 if any residue was zero [e.g. cannot be prime] */
y     =  0;

/* increase step to next candidate */
step += kstep;

/* compute the new residue without using division */
for (x = 1; x < PRIME_SIZE; x++) {
/* 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];
}

/* set flag if zero */
if (res_tab[x] == 0u) {
y = 1;
}
}
} while ((y == 1) && (step < (((mp_digit)1 << DIGIT_BIT) - kstep)));

if ((err = mp_add_d(a, step, a)) != MP_OKAY) {
goto LBL_ERR;
}

/* if didn't pass sieve and step == MAX then skip test */
if ((y == 1) && (step >= (((mp_digit)1 << DIGIT_BIT) - kstep))) {
continue;
}

if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
goto LBL_ERR;
}
if (res == MP_YES) {
break;
}
}

err = MP_OKAY;
LBL_ERR:
mp_clear(&b);
return err;
}

#endif

/* ref:         HEAD -> master, tag: v1.1.0 */