Mercurial > dropbear

comparison libtommath/bn_mp_prime_is_prime.c @ 1692:1051e4eea25a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update LibTomMath to 1.2.0 (#84) * update C files * update other files * update headers * update makefiles * remove mp_set/get_double() * use ltm 1.2.0 API * update ltm_desc * use bundled tommath if system-tommath is too old * XMALLOC etc. were changed to MP_MALLOC etc.
author Steffen Jaeckel <s@jaeckel.eu>
date Tue, 26 May 2020 17:36:47 +0200
parents a36e545fb43d
children
comparison
equal deleted inserted replaced
1691:2d3745d58843 1692:1051e4eea25a
1 #include "tommath_private.h" 1 #include "tommath_private.h"
2 #ifdef BN_MP_PRIME_IS_PRIME_C 2 #ifdef BN_MP_PRIME_IS_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 * SPDX-License-Identifier: Unlicense
13 */
14 5
15 /* portable integer log of two with small footprint */ 6 /* portable integer log of two with small footprint */
16 static unsigned int s_floor_ilog2(int value) 7 static unsigned int s_floor_ilog2(int value)
17 { 8 {
18 unsigned int r = 0; 9 unsigned int r = 0;
21 } 12 }
22 return r; 13 return r;
23 } 14 }
24 15
25 16
26 int mp_prime_is_prime(const mp_int *a, int t, int *result) 17 mp_err mp_prime_is_prime(const mp_int *a, int t, mp_bool *result)
27 { 18 {
28 mp_int b; 19 mp_int b;
29 int ix, err, res, p_max = 0, size_a, len; 20 int ix, p_max = 0, size_a, len;
21 mp_bool res;
22 mp_err err;
30 unsigned int fips_rand, mask; 23 unsigned int fips_rand, mask;
31 24
32 /* default to no */ 25 /* default to no */
33 *result = MP_NO; 26 *result = MP_NO;
34
35 /* valid value of t? */
36 if (t > PRIME_SIZE) {
37 return MP_VAL;
38 }
39 27
40 /* Some shortcuts */ 28 /* Some shortcuts */
41 /* N > 3 */ 29 /* N > 3 */
42 if (a->used == 1) { 30 if (a->used == 1) {
43 if ((a->dp[0] == 0u) || (a->dp[0] == 1u)) { 31 if ((a->dp[0] == 0u) || (a->dp[0] == 1u)) {
44 *result = 0; 32 *result = MP_NO;
45 return MP_OKAY; 33 return MP_OKAY;
46 } 34 }
47 if (a->dp[0] == 2u) { 35 if (a->dp[0] == 2u) {
48 *result = 1; 36 *result = MP_YES;
49 return MP_OKAY; 37 return MP_OKAY;
50 } 38 }
51 } 39 }
52 40
53 /* N must be odd */ 41 /* N must be odd */
54 if (mp_iseven(a) == MP_YES) { 42 if (MP_IS_EVEN(a)) {
55 return MP_OKAY; 43 return MP_OKAY;
56 } 44 }
57 /* N is not a perfect square: floor(sqrt(N))^2 != N */ 45 /* N is not a perfect square: floor(sqrt(N))^2 != N */
58 if ((err = mp_is_square(a, &res)) != MP_OKAY) { 46 if ((err = mp_is_square(a, &res)) != MP_OKAY) {
59 return err; 47 return err;
60 } 48 }
61 if (res != 0) { 49 if (res != MP_NO) {
62 return MP_OKAY; 50 return MP_OKAY;
63 } 51 }
64 52
65 /* is the input equal to one of the primes in the table? */ 53 /* is the input equal to one of the primes in the table? */
66 for (ix = 0; ix < PRIME_SIZE; ix++) { 54 for (ix = 0; ix < PRIVATE_MP_PRIME_TAB_SIZE; ix++) {
67 if (mp_cmp_d(a, ltm_prime_tab[ix]) == MP_EQ) { 55 if (mp_cmp_d(a, s_mp_prime_tab[ix]) == MP_EQ) {
68 *result = MP_YES; 56 *result = MP_YES;
69 return MP_OKAY; 57 return MP_OKAY;
70 } 58 }
71 } 59 }
72 #ifdef MP_8BIT 60 #ifdef MP_8BIT
73 /* The search in the loop above was exhaustive in this case */ 61 /* The search in the loop above was exhaustive in this case */
74 if ((a->used == 1) && (PRIME_SIZE >= 31)) { 62 if ((a->used == 1) && (PRIVATE_MP_PRIME_TAB_SIZE >= 31)) {
75 return MP_OKAY; 63 return MP_OKAY;
76 } 64 }
77 #endif 65 #endif
78 66
79 /* first perform trial division */ 67 /* first perform trial division */
80 if ((err = mp_prime_is_divisible(a, &res)) != MP_OKAY) { 68 if ((err = s_mp_prime_is_divisible(a, &res)) != MP_OKAY) {
81 return err; 69 return err;
82 } 70 }
83 71
84 /* return if it was trivially divisible */ 72 /* return if it was trivially divisible */
85 if (res == MP_YES) { 73 if (res == MP_YES) {
112 goto LBL_B; 100 goto LBL_B;
113 } 101 }
114 102
115 /* 103 /*
116 * Both, the Frobenius-Underwood test and the the Lucas-Selfridge test are quite 104 * Both, the Frobenius-Underwood test and the the Lucas-Selfridge test are quite
117 * slow so if speed is an issue, define LTM_USE_FIPS_ONLY to use M-R tests with 105 * slow so if speed is an issue, define LTM_USE_ONLY_MR to use M-R tests with
118 * bases 2, 3 and t random bases. 106 * bases 2, 3 and t random bases.
119 */ 107 */
120 #ifndef LTM_USE_FIPS_ONLY 108 #ifndef LTM_USE_ONLY_MR
121 if (t >= 0) { 109 if (t >= 0) {
122 /* 110 /*
123 * Use a Frobenius-Underwood test instead of the Lucas-Selfridge test for 111 * Use a Frobenius-Underwood test instead of the Lucas-Selfridge test for
124 * MP_8BIT (It is unknown if the Lucas-Selfridge test works with 16-bit 112 * MP_8BIT (It is unknown if the Lucas-Selfridge test works with 16-bit
125 * integers but the necesssary analysis is on the todo-list). 113 * integers but the necesssary analysis is on the todo-list).
147 if (t == 0) { 135 if (t == 0) {
148 t = 1; 136 t = 1;
149 } 137 }
150 138
151 /* 139 /*
152 abs(t) extra rounds of M-R to extend the range of primes it can find if t < 0.
153 Only recommended if the input range is known to be < 3317044064679887385961981 140 Only recommended if the input range is known to be < 3317044064679887385961981
154 141
155 It uses the bases for a deterministic M-R test if input < 3317044064679887385961981 142 It uses the bases necessary for a deterministic M-R test if the input is
143 smaller than 3317044064679887385961981
156 The caller has to check the size. 144 The caller has to check the size.
157 145 TODO: can be made a bit finer grained but comparing is not free.
158 Not for cryptographic use because with known bases strong M-R pseudoprimes can
159 be constructed. Use at least one M-R test with a random base (t >= 1).
160
161 The 1119 bit large number
162
163 80383745745363949125707961434194210813883768828755814583748891752229742737653\
164 33652186502336163960045457915042023603208766569966760987284043965408232928738\
165 79185086916685732826776177102938969773947016708230428687109997439976544144845\
166 34115587245063340927902227529622941498423068816854043264575340183297861112989\
167 60644845216191652872597534901
168
169 has been constructed by F. Arnault (F. Arnault, "Rabin-Miller primality test:
170 composite numbers which pass it.", Mathematics of Computation, 1995, 64. Jg.,
171 Nr. 209, S. 355-361), is a semiprime with the two factors
172
173 40095821663949960541830645208454685300518816604113250877450620473800321707011\
174 96242716223191597219733582163165085358166969145233813917169287527980445796800\
175 452592031836601
176
177 20047910831974980270915322604227342650259408302056625438725310236900160853505\
178 98121358111595798609866791081582542679083484572616906958584643763990222898400\
179 226296015918301
180
181 and it is a strong pseudoprime to all forty-six prime M-R bases up to 200
182
183 It does not fail the strong Bailley-PSP test as implemented here, it is just
184 given as an example, if not the reason to use the BPSW-test instead of M-R-tests
185 with a sequence of primes 2...n.
186
187 */ 146 */
188 if (t < 0) { 147 if (t < 0) {
189 t = -t;
190 /* 148 /*
191 Sorenson, Jonathan; Webster, Jonathan (2015). 149 Sorenson, Jonathan; Webster, Jonathan (2015).
192 "Strong Pseudoprimes to Twelve Prime Bases". 150 "Strong Pseudoprimes to Twelve Prime Bases".
193 */ 151 */
194 /* 0x437ae92817f9fc85b7e5 = 318665857834031151167461 */ 152 /* 0x437ae92817f9fc85b7e5 = 318665857834031151167461 */
210 err = MP_VAL; 168 err = MP_VAL;
211 goto LBL_B; 169 goto LBL_B;
212 } 170 }
213 } 171 }
214 172
215 /* for compatibility with the current API (well, compatible within a sign's width) */
216 if (p_max < t) {
217 p_max = t;
218 }
219
220 if (p_max > PRIME_SIZE) {
221 err = MP_VAL;
222 goto LBL_B;
223 }
224 /* we did bases 2 and 3 already, skip them */ 173 /* we did bases 2 and 3 already, skip them */
225 for (ix = 2; ix < p_max; ix++) { 174 for (ix = 2; ix < p_max; ix++) {
226 mp_set(&b, ltm_prime_tab[ix]); 175 mp_set(&b, s_mp_prime_tab[ix]);
227 if ((err = mp_prime_miller_rabin(a, &b, &res)) != MP_OKAY) { 176 if ((err = mp_prime_miller_rabin(a, &b, &res)) != MP_OKAY) {
228 goto LBL_B; 177 goto LBL_B;
229 } 178 }
230 if (res == MP_NO) { 179 if (res == MP_NO) {
231 goto LBL_B; 180 goto LBL_B;
294 #ifdef MP_8BIT 243 #ifdef MP_8BIT
295 /* 244 /*
296 * One 8-bit digit is too small, so concatenate two if the size of 245 * One 8-bit digit is too small, so concatenate two if the size of
297 * unsigned int allows for it. 246 * unsigned int allows for it.
298 */ 247 */
299 if (((sizeof(unsigned int) * CHAR_BIT)/2) >= (sizeof(mp_digit) * CHAR_BIT)) { 248 if ((MP_SIZEOF_BITS(unsigned int)/2) >= MP_SIZEOF_BITS(mp_digit)) {
300 if ((err = mp_rand(&b, 1)) != MP_OKAY) { 249 if ((err = mp_rand(&b, 1)) != MP_OKAY) {
301 goto LBL_B; 250 goto LBL_B;
302 } 251 }
303 fips_rand <<= sizeof(mp_digit) * CHAR_BIT; 252 fips_rand <<= MP_SIZEOF_BITS(mp_digit);
304 fips_rand |= (unsigned int) b.dp[0]; 253 fips_rand |= (unsigned int) b.dp[0];
305 fips_rand &= mask; 254 fips_rand &= mask;
306 } 255 }
307 #endif 256 #endif
308 if (fips_rand > (unsigned int)(INT_MAX - DIGIT_BIT)) { 257 if (fips_rand > (unsigned int)(INT_MAX - MP_DIGIT_BIT)) {
309 len = INT_MAX / DIGIT_BIT; 258 len = INT_MAX / MP_DIGIT_BIT;
310 } else { 259 } else {
311 len = (((int)fips_rand + DIGIT_BIT) / DIGIT_BIT); 260 len = (((int)fips_rand + MP_DIGIT_BIT) / MP_DIGIT_BIT);
312 } 261 }
313 /* Unlikely. */ 262 /* Unlikely. */
314 if (len < 0) { 263 if (len < 0) {
315 ix--; 264 ix--;
316 continue; 265 continue;
361 mp_clear(&b); 310 mp_clear(&b);
362 return err; 311 return err;
363 } 312 }
364 313
365 #endif 314 #endif
366
367 /* ref: HEAD -> master, tag: v1.1.0 */
368 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
369 /* commit time: 2019-01-28 20:32:32 +0100 */