bn_mp_prime_next_prime.c [plain text]
#include <tommath.h>
#ifdef BN_MP_PRIME_NEXT_PRIME_C
int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
{
int err, res = MP_NO, x, y;
mp_digit res_tab[PRIME_SIZE], step, kstep;
mp_int b;
if (t <= 0 || t > PRIME_SIZE) {
return MP_VAL;
}
a->sign = MP_ZPOS;
if (mp_cmp_d(a, ltm_prime_tab[PRIME_SIZE-1]) == MP_LT) {
for (x = PRIME_SIZE - 2; x >= 0; x--) {
if (mp_cmp_d(a, ltm_prime_tab[x]) != MP_LT) {
if (bbs_style == 1) {
if ((ltm_prime_tab[x + 1] & 3) != 3) {
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, 1) == MP_EQ) {
mp_set(a, 2);
return MP_OKAY;
}
}
if (bbs_style == 1) {
kstep = 4;
} else {
kstep = 2;
}
if (bbs_style == 1) {
if ((a->dp[0] & 3) != 3) {
if ((err = mp_sub_d(a, (a->dp[0] & 3) + 1, a)) != MP_OKAY) { return err; };
}
} else {
if (mp_iseven(a) == 1) {
if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) {
return err;
}
}
}
for (x = 1; x < PRIME_SIZE; x++) {
if ((err = mp_mod_d(a, ltm_prime_tab[x], res_tab + x)) != MP_OKAY) {
return err;
}
}
if ((err = mp_init(&b)) != MP_OKAY) {
return err;
}
for (;;) {
step = 0;
do {
y = 0;
step += kstep;
for (x = 1; x < PRIME_SIZE; x++) {
res_tab[x] += kstep;
if (res_tab[x] >= ltm_prime_tab[x]) {
res_tab[x] -= ltm_prime_tab[x];
}
if (res_tab[x] == 0) {
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 (y == 1 && step >= ((((mp_digit)1)<<DIGIT_BIT) - kstep)) {
continue;
}
for (x = 0; x < t; x++) {
mp_set(&b, ltm_prime_tab[t]);
if ((err = mp_prime_miller_rabin(a, &b, &res)) != MP_OKAY) {
goto LBL_ERR;
}
if (res == MP_NO) {
break;
}
}
if (res == MP_YES) {
break;
}
}
err = MP_OKAY;
LBL_ERR:
mp_clear(&b);
return err;
}
#endif