Mercurial > dropbear

comparison bn_mp_prime_next_prime.c @ 190:d8254fc979e9 libtommath-orig LTM_0.35

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import of libtommath 0.35
author Matt Johnston <matt@ucc.asn.au>
date Fri, 06 May 2005 08:59:30 +0000
parents d29b64170cf0
children
comparison
equal deleted inserted replaced
142:d29b64170cf0 190:d8254fc979e9
33 33
34 /* force positive */ 34 /* force positive */
35 a->sign = MP_ZPOS; 35 a->sign = MP_ZPOS;
36 36
37 /* simple algo if a is less than the largest prime in the table */ 37 /* simple algo if a is less than the largest prime in the table */
38 if (mp_cmp_d(a, __prime_tab[PRIME_SIZE-1]) == MP_LT) { 38 if (mp_cmp_d(a, ltm_prime_tab[PRIME_SIZE-1]) == MP_LT) {
39 /* find which prime it is bigger than */ 39 /* find which prime it is bigger than */
40 for (x = PRIME_SIZE - 2; x >= 0; x--) { 40 for (x = PRIME_SIZE - 2; x >= 0; x--) {
41 if (mp_cmp_d(a, __prime_tab[x]) != MP_LT) { 41 if (mp_cmp_d(a, ltm_prime_tab[x]) != MP_LT) {
42 if (bbs_style == 1) { 42 if (bbs_style == 1) {
43 /* ok we found a prime smaller or 43 /* ok we found a prime smaller or
44 * equal [so the next is larger] 44 * equal [so the next is larger]
45 * 45 *
46 * however, the prime must be 46 * however, the prime must be
47 * congruent to 3 mod 4 47 * congruent to 3 mod 4
48 */ 48 */
49 if ((__prime_tab[x + 1] & 3) != 3) { 49 if ((ltm_prime_tab[x + 1] & 3) != 3) {
50 /* scan upwards for a prime congruent to 3 mod 4 */ 50 /* scan upwards for a prime congruent to 3 mod 4 */
51 for (y = x + 1; y < PRIME_SIZE; y++) { 51 for (y = x + 1; y < PRIME_SIZE; y++) {
52 if ((__prime_tab[y] & 3) == 3) { 52 if ((ltm_prime_tab[y] & 3) == 3) {
53 mp_set(a, __prime_tab[y]); 53 mp_set(a, ltm_prime_tab[y]);
54 return MP_OKAY; 54 return MP_OKAY;
55 } 55 }
56 } 56 }
57 } 57 }
58 } else { 58 } else {
59 mp_set(a, __prime_tab[x + 1]); 59 mp_set(a, ltm_prime_tab[x + 1]);
60 return MP_OKAY; 60 return MP_OKAY;
61 } 61 }
62 } 62 }
63 } 63 }
64 /* at this point a maybe 1 */ 64 /* at this point a maybe 1 */
92 } 92 }
93 } 93 }
94 94
95 /* generate the restable */ 95 /* generate the restable */
96 for (x = 1; x < PRIME_SIZE; x++) { 96 for (x = 1; x < PRIME_SIZE; x++) {
97 if ((err = mp_mod_d(a, __prime_tab[x], res_tab + x)) != MP_OKAY) { 97 if ((err = mp_mod_d(a, ltm_prime_tab[x], res_tab + x)) != MP_OKAY) {
98 return err; 98 return err;
99 } 99 }
100 } 100 }
101 101
102 /* init temp used for Miller-Rabin Testing */ 102 /* init temp used for Miller-Rabin Testing */
118 for (x = 1; x < PRIME_SIZE; x++) { 118 for (x = 1; x < PRIME_SIZE; x++) {
119 /* add the step to each residue */ 119 /* add the step to each residue */
120 res_tab[x] += kstep; 120 res_tab[x] += kstep;
121 121
122 /* subtract the modulus [instead of using division] */ 122 /* subtract the modulus [instead of using division] */
123 if (res_tab[x] >= __prime_tab[x]) { 123 if (res_tab[x] >= ltm_prime_tab[x]) {
124 res_tab[x] -= __prime_tab[x]; 124 res_tab[x] -= ltm_prime_tab[x];
125 } 125 }
126 126
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;
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 __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++) {
146 mp_set(&b, __prime_tab[t]); 146 mp_set(&b, ltm_prime_tab[t]);
147 if ((err = mp_prime_miller_rabin(a, &b, &res)) != MP_OKAY) { 147 if ((err = mp_prime_miller_rabin(a, &b, &res)) != MP_OKAY) {
148 goto __ERR; 148 goto LBL_ERR;
149 } 149 }
150 if (res == MP_NO) { 150 if (res == MP_NO) {
151 break; 151 break;
152 } 152 }
153 } 153 }
156 break; 156 break;
157 } 157 }
158 } 158 }
159 159
160 err = MP_OKAY; 160 err = MP_OKAY;
161 __ERR: 161 LBL_ERR:
162 mp_clear(&b); 162 mp_clear(&b);
163 return err; 163 return err;
164 } 164 }
165 165
166 #endif 166 #endif