Mercurial > dropbear

comparison libtommath/bn_mp_prime_next_prime.c @ 1739:13d834efc376 fuzz

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge from main
author Matt Johnston <matt@ucc.asn.au>
date Thu, 15 Oct 2020 19:55:15 +0800
parents 1051e4eea25a
children
comparison
equal deleted inserted replaced
1562:768ebf737aa0 1739:13d834efc376
1 #include <tommath_private.h> 1 #include "tommath_private.h"
2 #ifdef BN_MP_PRIME_NEXT_PRIME_C 2 #ifdef BN_MP_PRIME_NEXT_PRIME_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 * 4 /* SPDX-License-Identifier: Unlicense */
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * The library is free for all purposes without any express
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */
17 5
18 /* finds the next prime after the number "a" using "t" trials 6 /* finds the next prime after the number "a" using "t" trials
19 * of Miller-Rabin. 7 * of Miller-Rabin.
20 * 8 *
21 * bbs_style = 1 means the prime must be congruent to 3 mod 4 9 * bbs_style = 1 means the prime must be congruent to 3 mod 4
22 */ 10 */
23 int mp_prime_next_prime(mp_int *a, int t, int bbs_style) 11 mp_err mp_prime_next_prime(mp_int *a, int t, int bbs_style)
24 { 12 {
25 int err, res = MP_NO, x, y; 13 int x, y;
26 mp_digit res_tab[PRIME_SIZE], step, kstep; 14 mp_ord cmp;
15 mp_err err;
16 mp_bool res = MP_NO;
17 mp_digit res_tab[PRIVATE_MP_PRIME_TAB_SIZE], step, kstep;
27 mp_int b; 18 mp_int b;
28
29 /* ensure t is valid */
30 if ((t <= 0) || (t > PRIME_SIZE)) {
31 return MP_VAL;
32 }
33 19
34 /* force positive */ 20 /* force positive */
35 a->sign = MP_ZPOS; 21 a->sign = MP_ZPOS;
36 22
37 /* simple algo if a is less than the largest prime in the table */ 23 /* simple algo if a is less than the largest prime in the table */
38 if (mp_cmp_d(a, ltm_prime_tab[PRIME_SIZE-1]) == MP_LT) { 24 if (mp_cmp_d(a, s_mp_prime_tab[PRIVATE_MP_PRIME_TAB_SIZE-1]) == MP_LT) {
39 /* find which prime it is bigger than */ 25 /* find which prime it is bigger than "a" */
40 for (x = PRIME_SIZE - 2; x >= 0; x--) { 26 for (x = 0; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
41 if (mp_cmp_d(a, ltm_prime_tab[x]) != MP_LT) { 27 cmp = mp_cmp_d(a, s_mp_prime_tab[x]);
42 if (bbs_style == 1) { 28 if (cmp == MP_EQ) {
43 /* ok we found a prime smaller or 29 continue;
44 * equal [so the next is larger] 30 }
45 * 31 if (cmp != MP_GT) {
46 * however, the prime must be 32 if ((bbs_style == 1) && ((s_mp_prime_tab[x] & 3u) != 3u)) {
47 * congruent to 3 mod 4 33 /* try again until we get a prime congruent to 3 mod 4 */
48 */ 34 continue;
49 if ((ltm_prime_tab[x + 1] & 3) != 3) { 35 } else {
50 /* scan upwards for a prime congruent to 3 mod 4 */ 36 mp_set(a, s_mp_prime_tab[x]);
51 for (y = x + 1; y < PRIME_SIZE; y++) { 37 return MP_OKAY;
52 if ((ltm_prime_tab[y] & 3) == 3) { 38 }
53 mp_set(a, ltm_prime_tab[y]); 39 }
54 return MP_OKAY;
55 }
56 }
57 }
58 } else {
59 mp_set(a, ltm_prime_tab[x + 1]);
60 return MP_OKAY;
61 }
62 }
63 }
64 /* at this point a maybe 1 */
65 if (mp_cmp_d(a, 1) == MP_EQ) {
66 mp_set(a, 2);
67 return MP_OKAY;
68 } 40 }
69 /* fall through to the sieve */ 41 /* fall through to the sieve */
70 } 42 }
71 43
72 /* generate a prime congruent to 3 mod 4 or 1/3 mod 4? */ 44 /* generate a prime congruent to 3 mod 4 or 1/3 mod 4? */
78 50
79 /* at this point we will use a combination of a sieve and Miller-Rabin */ 51 /* at this point we will use a combination of a sieve and Miller-Rabin */
80 52
81 if (bbs_style == 1) { 53 if (bbs_style == 1) {
82 /* if a mod 4 != 3 subtract the correct value to make it so */ 54 /* if a mod 4 != 3 subtract the correct value to make it so */
83 if ((a->dp[0] & 3) != 3) { 55 if ((a->dp[0] & 3u) != 3u) {
84 if ((err = mp_sub_d(a, (a->dp[0] & 3) + 1, a)) != MP_OKAY) { return err; }; 56 if ((err = mp_sub_d(a, (a->dp[0] & 3u) + 1u, a)) != MP_OKAY) {
57 return err;
58 }
85 } 59 }
86 } else { 60 } else {
87 if (mp_iseven(a) == MP_YES) { 61 if (MP_IS_EVEN(a)) {
88 /* force odd */ 62 /* force odd */
89 if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) { 63 if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) {
90 return err; 64 return err;
91 } 65 }
92 } 66 }
93 } 67 }
94 68
95 /* generate the restable */ 69 /* generate the restable */
96 for (x = 1; x < PRIME_SIZE; x++) { 70 for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
97 if ((err = mp_mod_d(a, ltm_prime_tab[x], res_tab + x)) != MP_OKAY) { 71 if ((err = mp_mod_d(a, s_mp_prime_tab[x], res_tab + x)) != MP_OKAY) {
98 return err; 72 return err;
99 } 73 }
100 } 74 }
101 75
102 /* init temp used for Miller-Rabin Testing */ 76 /* init temp used for Miller-Rabin Testing */
113 87
114 /* increase step to next candidate */ 88 /* increase step to next candidate */
115 step += kstep; 89 step += kstep;
116 90
117 /* compute the new residue without using division */ 91 /* compute the new residue without using division */
118 for (x = 1; x < PRIME_SIZE; x++) { 92 for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
119 /* add the step to each residue */ 93 /* add the step to each residue */
120 res_tab[x] += kstep; 94 res_tab[x] += kstep;
121 95
122 /* subtract the modulus [instead of using division] */ 96 /* subtract the modulus [instead of using division] */
123 if (res_tab[x] >= ltm_prime_tab[x]) { 97 if (res_tab[x] >= s_mp_prime_tab[x]) {
124 res_tab[x] -= ltm_prime_tab[x]; 98 res_tab[x] -= s_mp_prime_tab[x];
125 } 99 }
126 100
127 /* set flag if zero */ 101 /* set flag if zero */
128 if (res_tab[x] == 0) { 102 if (res_tab[x] == 0u) {
129 y = 1; 103 y = 1;
130 } 104 }
131 } 105 }
132 } while ((y == 1) && (step < ((((mp_digit)1) << DIGIT_BIT) - kstep))); 106 } while ((y == 1) && (step < (((mp_digit)1 << MP_DIGIT_BIT) - kstep)));
133 107
134 /* add the step */ 108 /* add the step */
135 if ((err = mp_add_d(a, step, a)) != MP_OKAY) { 109 if ((err = mp_add_d(a, step, a)) != MP_OKAY) {
136 goto LBL_ERR; 110 goto LBL_ERR;
137 } 111 }
138 112
139 /* if didn't pass sieve and step == MAX then skip test */ 113 /* if didn't pass sieve and step == MP_MAX then skip test */
140 if ((y == 1) && (step >= ((((mp_digit)1) << DIGIT_BIT) - kstep))) { 114 if ((y == 1) && (step >= (((mp_digit)1 << MP_DIGIT_BIT) - kstep))) {
141 continue; 115 continue;
142 } 116 }
143 117
144 /* is this prime? */ 118 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
145 for (x = 0; x < t; x++) { 119 goto LBL_ERR;
146 mp_set(&b, ltm_prime_tab[x]);
147 if ((err = mp_prime_miller_rabin(a, &b, &res)) != MP_OKAY) {
148 goto LBL_ERR;
149 }
150 if (res == MP_NO) {
151 break;
152 }
153 } 120 }
154
155 if (res == MP_YES) { 121 if (res == MP_YES) {
156 break; 122 break;
157 } 123 }
158 } 124 }
159 125
162 mp_clear(&b); 128 mp_clear(&b);
163 return err; 129 return err;
164 } 130 }
165 131
166 #endif 132 #endif
167
168 /* ref: $Format:%D$ */
169 /* git commit: $Format:%H$ */
170 /* commit time: $Format:%ai$ */