Mercurial > dropbear

comparison libtommath/bn_mp_prime_next_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_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 * SPDX-License-Identifier: Unlicense
13 */
14 5
15 /* finds the next prime after the number "a" using "t" trials 6 /* finds the next prime after the number "a" using "t" trials
16 * of Miller-Rabin. 7 * of Miller-Rabin.
17 * 8 *
18 * 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
19 */ 10 */
20 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)
21 { 12 {
22 int err, res = MP_NO, x, y, cmp; 13 int x, y;
23 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;
24 mp_int b; 18 mp_int b;
25 19
26 /* force positive */ 20 /* force positive */
27 a->sign = MP_ZPOS; 21 a->sign = MP_ZPOS;
28 22
29 /* 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 */
30 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) {
31 /* find which prime it is bigger than "a" */ 25 /* find which prime it is bigger than "a" */
32 for (x = 0; x < PRIME_SIZE; x++) { 26 for (x = 0; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
33 cmp = mp_cmp_d(a, ltm_prime_tab[x]); 27 cmp = mp_cmp_d(a, s_mp_prime_tab[x]);
34 if (cmp == MP_EQ) { 28 if (cmp == MP_EQ) {
35 continue; 29 continue;
36 } 30 }
37 if (cmp != MP_GT) { 31 if (cmp != MP_GT) {
38 if ((bbs_style == 1) && ((ltm_prime_tab[x] & 3u) != 3u)) { 32 if ((bbs_style == 1) && ((s_mp_prime_tab[x] & 3u) != 3u)) {
39 /* try again until we get a prime congruent to 3 mod 4 */ 33 /* try again until we get a prime congruent to 3 mod 4 */
40 continue; 34 continue;
41 } else { 35 } else {
42 mp_set(a, ltm_prime_tab[x]); 36 mp_set(a, s_mp_prime_tab[x]);
43 return MP_OKAY; 37 return MP_OKAY;
44 } 38 }
45 } 39 }
46 } 40 }
47 /* fall through to the sieve */ 41 /* fall through to the sieve */
62 if ((err = mp_sub_d(a, (a->dp[0] & 3u) + 1u, a)) != MP_OKAY) { 56 if ((err = mp_sub_d(a, (a->dp[0] & 3u) + 1u, a)) != MP_OKAY) {
63 return err; 57 return err;
64 } 58 }
65 } 59 }
66 } else { 60 } else {
67 if (mp_iseven(a) == MP_YES) { 61 if (MP_IS_EVEN(a)) {
68 /* force odd */ 62 /* force odd */
69 if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) { 63 if ((err = mp_sub_d(a, 1uL, a)) != MP_OKAY) {
70 return err; 64 return err;
71 } 65 }
72 } 66 }
73 } 67 }
74 68
75 /* generate the restable */ 69 /* generate the restable */
76 for (x = 1; x < PRIME_SIZE; x++) { 70 for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
77 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) {
78 return err; 72 return err;
79 } 73 }
80 } 74 }
81 75
82 /* init temp used for Miller-Rabin Testing */ 76 /* init temp used for Miller-Rabin Testing */
93 87
94 /* increase step to next candidate */ 88 /* increase step to next candidate */
95 step += kstep; 89 step += kstep;
96 90
97 /* compute the new residue without using division */ 91 /* compute the new residue without using division */
98 for (x = 1; x < PRIME_SIZE; x++) { 92 for (x = 1; x < PRIVATE_MP_PRIME_TAB_SIZE; x++) {
99 /* add the step to each residue */ 93 /* add the step to each residue */
100 res_tab[x] += kstep; 94 res_tab[x] += kstep;
101 95
102 /* subtract the modulus [instead of using division] */ 96 /* subtract the modulus [instead of using division] */
103 if (res_tab[x] >= ltm_prime_tab[x]) { 97 if (res_tab[x] >= s_mp_prime_tab[x]) {
104 res_tab[x] -= ltm_prime_tab[x]; 98 res_tab[x] -= s_mp_prime_tab[x];
105 } 99 }
106 100
107 /* set flag if zero */ 101 /* set flag if zero */
108 if (res_tab[x] == 0u) { 102 if (res_tab[x] == 0u) {
109 y = 1; 103 y = 1;
110 } 104 }
111 } 105 }
112 } while ((y == 1) && (step < (((mp_digit)1 << DIGIT_BIT) - kstep))); 106 } while ((y == 1) && (step < (((mp_digit)1 << MP_DIGIT_BIT) - kstep)));
113 107
114 /* add the step */ 108 /* add the step */
115 if ((err = mp_add_d(a, step, a)) != MP_OKAY) { 109 if ((err = mp_add_d(a, step, a)) != MP_OKAY) {
116 goto LBL_ERR; 110 goto LBL_ERR;
117 } 111 }
118 112
119 /* if didn't pass sieve and step == MAX then skip test */ 113 /* if didn't pass sieve and step == MP_MAX then skip test */
120 if ((y == 1) && (step >= (((mp_digit)1 << DIGIT_BIT) - kstep))) { 114 if ((y == 1) && (step >= (((mp_digit)1 << MP_DIGIT_BIT) - kstep))) {
121 continue; 115 continue;
122 } 116 }
123 117
124 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { 118 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) {
125 goto LBL_ERR; 119 goto LBL_ERR;
134 mp_clear(&b); 128 mp_clear(&b);
135 return err; 129 return err;
136 } 130 }
137 131
138 #endif 132 #endif
139
140 /* ref: HEAD -> master, tag: v1.1.0 */
141 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
142 /* commit time: 2019-01-28 20:32:32 +0100 */