Mercurial > dropbear

comparison libtommath/bn_mp_prime_next_prime.c @ 1436:60fc6476e044

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update to libtommath v1.0
author Matt Johnston <matt@ucc.asn.au>
date Sat, 24 Jun 2017 22:37:14 +0800
parents a55b97f5a485
children 8bba51a55704
comparison
equal deleted inserted replaced
1435:f849a5ca2efc 1436:60fc6476e044
1 #include <tommath.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 *
5 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * The library is free for all purposes without any express
13 * guarantee it works. 13 * guarantee it works.
14 * 14 *
15 * Tom St Denis, [email protected], http://math.libtomcrypt.com 15 * Tom St Denis, [email protected], http://libtom.org
16 */ 16 */
17 17
18 /* finds the next prime after the number "a" using "t" trials 18 /* finds the next prime after the number "a" using "t" trials
19 * of Miller-Rabin. 19 * of Miller-Rabin.
20 * 20 *
21 * bbs_style = 1 means the prime must be congruent to 3 mod 4 21 * bbs_style = 1 means the prime must be congruent to 3 mod 4
22 */ 22 */
23 int mp_prime_next_prime(mp_int *a, int t, int bbs_style) 23 int mp_prime_next_prime(mp_int *a, int t, int bbs_style)
24 { 24 {
25 int err, res, x, y; 25 int err, res = MP_NO, x, y;
26 mp_digit res_tab[PRIME_SIZE], step, kstep; 26 mp_digit res_tab[PRIME_SIZE], step, kstep;
27 mp_int b; 27 mp_int b;
28 28
29 /* ensure t is valid */ 29 /* ensure t is valid */
30 if (t <= 0 || t > PRIME_SIZE) { 30 if ((t <= 0) || (t > PRIME_SIZE)) {
31 return MP_VAL; 31 return MP_VAL;
32 } 32 }
33 33
34 /* force positive */ 34 /* force positive */
35 a->sign = MP_ZPOS; 35 a->sign = MP_ZPOS;
82 /* if a mod 4 != 3 subtract the correct value to make it so */ 82 /* if a mod 4 != 3 subtract the correct value to make it so */
83 if ((a->dp[0] & 3) != 3) { 83 if ((a->dp[0] & 3) != 3) {
84 if ((err = mp_sub_d(a, (a->dp[0] & 3) + 1, a)) != MP_OKAY) { return err; }; 84 if ((err = mp_sub_d(a, (a->dp[0] & 3) + 1, a)) != MP_OKAY) { return err; };
85 } 85 }
86 } else { 86 } else {
87 if (mp_iseven(a) == 1) { 87 if (mp_iseven(a) == MP_YES) {
88 /* force odd */ 88 /* force odd */
89 if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) { 89 if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) {
90 return err; 90 return err;
91 } 91 }
92 } 92 }
127 /* set flag if zero */ 127 /* set flag if zero */
128 if (res_tab[x] == 0) { 128 if (res_tab[x] == 0) {
129 y = 1; 129 y = 1;
130 } 130 }
131 } 131 }
132 } while (y == 1 && step < ((((mp_digit)1)<<DIGIT_BIT) - kstep)); 132 } while ((y == 1) && (step < ((((mp_digit)1) << DIGIT_BIT) - kstep)));
133 133
134 /* add the step */ 134 /* add the step */
135 if ((err = mp_add_d(a, step, a)) != MP_OKAY) { 135 if ((err = mp_add_d(a, step, a)) != MP_OKAY) {
136 goto LBL_ERR; 136 goto LBL_ERR;
137 } 137 }
138 138
139 /* if didn't pass sieve and step == MAX then skip test */ 139 /* if didn't pass sieve and step == MAX then skip test */
140 if (y == 1 && step >= ((((mp_digit)1)<<DIGIT_BIT) - kstep)) { 140 if ((y == 1) && (step >= ((((mp_digit)1) << DIGIT_BIT) - kstep))) {
141 continue; 141 continue;
142 } 142 }
143 143
144 /* is this prime? */ 144 /* is this prime? */
145 for (x = 0; x < t; x++) { 145 for (x = 0; x < t; x++) {
163 return err; 163 return err;
164 } 164 }
165 165
166 #endif 166 #endif
167 167
168 /* $Source: /cvs/libtom/libtommath/bn_mp_prime_next_prime.c,v $ */ 168 /* $Source$ */
169 /* $Revision: 1.3 $ */ 169 /* $Revision$ */
170 /* $Date: 2006/03/31 14:18:44 $ */ 170 /* $Date$ */