Mercurial > dropbear

comparison libtommath/bn_mp_prime_next_prime.c @ 1656:a36e545fb43d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 <s@jaeckel.eu>
date Tue, 17 Sep 2019 16:11:09 +0200
parents f52919ffd3b1
children 1051e4eea25a
comparison
equal deleted inserted replaced
1655:f52919ffd3b1 1656:a36e545fb43d
17 * 17 *
18 * bbs_style = 1 means the prime must be congruent to 3 mod 4 18 * bbs_style = 1 means the prime must be congruent to 3 mod 4
19 */ 19 */
20 int mp_prime_next_prime(mp_int *a, int t, int bbs_style) 20 int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
21 { 21 {
22 int err, res = MP_NO, x, y; 22 int err, res = MP_NO, x, y, cmp;
23 mp_digit res_tab[PRIME_SIZE], step, kstep; 23 mp_digit res_tab[PRIME_SIZE], step, kstep;
24 mp_int b; 24 mp_int b;
25 25
26 /* force positive */ 26 /* force positive */
27 a->sign = MP_ZPOS; 27 a->sign = MP_ZPOS;
28 28
29 /* simple algo if a is less than the largest prime in the table */ 29 /* simple algo if a is less than the largest prime in the table */
30 if (mp_cmp_d(a, ltm_prime_tab[PRIME_SIZE-1]) == MP_LT) { 30 if (mp_cmp_d(a, ltm_prime_tab[PRIME_SIZE-1]) == MP_LT) {
31 /* find which prime it is bigger than */ 31 /* find which prime it is bigger than "a" */
32 for (x = PRIME_SIZE - 2; x >= 0; x--) { 32 for (x = 0; x < PRIME_SIZE; x++) {
33 if (mp_cmp_d(a, ltm_prime_tab[x]) != MP_LT) { 33 cmp = mp_cmp_d(a, ltm_prime_tab[x]);
34 if (bbs_style == 1) { 34 if (cmp == MP_EQ) {
35 /* ok we found a prime smaller or 35 continue;
36 * equal [so the next is larger] 36 }
37 * 37 if (cmp != MP_GT) {
38 * however, the prime must be 38 if ((bbs_style == 1) && ((ltm_prime_tab[x] & 3u) != 3u)) {
39 * congruent to 3 mod 4 39 /* try again until we get a prime congruent to 3 mod 4 */
40 */ 40 continue;
41 if ((ltm_prime_tab[x + 1] & 3u) != 3u) {
42 /* scan upwards for a prime congruent to 3 mod 4 */
43 for (y = x + 1; y < PRIME_SIZE; y++) {
44 if ((ltm_prime_tab[y] & 3u) == 3u) {
45 mp_set(a, ltm_prime_tab[y]);
46 return MP_OKAY;
47 }
48 }
49 }
50 } else { 41 } else {
51 mp_set(a, ltm_prime_tab[x + 1]); 42 mp_set(a, ltm_prime_tab[x]);
52 return MP_OKAY; 43 return MP_OKAY;
53 } 44 }
54 } 45 }
55 }
56 /* at this point a maybe 1 */
57 if (mp_cmp_d(a, 1uL) == MP_EQ) {
58 mp_set(a, 2uL);
59 return MP_OKAY;
60 } 46 }
61 /* fall through to the sieve */ 47 /* fall through to the sieve */
62 } 48 }
63 49
64 /* generate a prime congruent to 3 mod 4 or 1/3 mod 4? */ 50 /* generate a prime congruent to 3 mod 4 or 1/3 mod 4? */
73 if (bbs_style == 1) { 59 if (bbs_style == 1) {
74 /* if a mod 4 != 3 subtract the correct value to make it so */ 60 /* if a mod 4 != 3 subtract the correct value to make it so */
75 if ((a->dp[0] & 3u) != 3u) { 61 if ((a->dp[0] & 3u) != 3u) {
76 if ((err = mp_sub_d(a, (a->dp[0] & 3u) + 1u, a)) != MP_OKAY) { 62 if ((err = mp_sub_d(a, (a->dp[0] & 3u) + 1u, a)) != MP_OKAY) {
77 return err; 63 return err;
78 }; 64 }
79 } 65 }
80 } else { 66 } else {
81 if (mp_iseven(a) == MP_YES) { 67 if (mp_iseven(a) == MP_YES) {
82 /* force odd */ 68 /* force odd */
83 if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) { 69 if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) {