Mercurial > dropbear

comparison libtommath/bn_mp_prime_frobenius_underwood.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 f52919ffd3b1
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_FROBENIUS_UNDERWOOD_C 2 #ifdef BN_MP_PRIME_FROBENIUS_UNDERWOOD_C
3 3
4 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
5 * 5 /* SPDX-License-Identifier: Unlicense */
6 * LibTomMath is a library that provides multiple-precision
7 * integer arithmetic as well as number theoretic functionality.
8 *
9 * The library was designed directly after the MPI library by
10 * Michael Fromberger but has been written from scratch with
11 * additional optimizations in place.
12 *
13 * SPDX-License-Identifier: Unlicense
14 */
15 6
16 /* 7 /*
17 * See file bn_mp_prime_is_prime.c or the documentation in doc/bn.tex for the details 8 * See file bn_mp_prime_is_prime.c or the documentation in doc/bn.tex for the details
18 */ 9 */
19 #ifndef LTM_USE_FIPS_ONLY 10 #ifndef LTM_USE_ONLY_MR
20 11
21 #ifdef MP_8BIT 12 #ifdef MP_8BIT
22 /* 13 /*
23 * floor of positive solution of 14 * floor of positive solution of
24 * (2^16)-1 = (a+4)*(2*a+5) 15 * (2^16)-1 = (a+4)*(2*a+5)
30 */ 21 */
31 #define LTM_FROBENIUS_UNDERWOOD_A 177 22 #define LTM_FROBENIUS_UNDERWOOD_A 177
32 #else 23 #else
33 #define LTM_FROBENIUS_UNDERWOOD_A 32764 24 #define LTM_FROBENIUS_UNDERWOOD_A 32764
34 #endif 25 #endif
35 int mp_prime_frobenius_underwood(const mp_int *N, int *result) 26 mp_err mp_prime_frobenius_underwood(const mp_int *N, mp_bool *result)
36 { 27 {
37 mp_int T1z, T2z, Np1z, sz, tz; 28 mp_int T1z, T2z, Np1z, sz, tz;
38 29
39 int a, ap2, length, i, j, isset; 30 int a, ap2, length, i, j;
40 int e; 31 mp_err err;
41 32
42 *result = MP_NO; 33 *result = MP_NO;
43 34
44 if ((e = mp_init_multi(&T1z, &T2z, &Np1z, &sz, &tz, NULL)) != MP_OKAY) { 35 if ((err = mp_init_multi(&T1z, &T2z, &Np1z, &sz, &tz, NULL)) != MP_OKAY) {
45 return e; 36 return err;
46 } 37 }
47 38
48 for (a = 0; a < LTM_FROBENIUS_UNDERWOOD_A; a++) { 39 for (a = 0; a < LTM_FROBENIUS_UNDERWOOD_A; a++) {
49 /* TODO: That's ugly! No, really, it is! */ 40 /* TODO: That's ugly! No, really, it is! */
50 if ((a==2) || (a==4) || (a==7) || (a==8) || (a==10) || 41 if ((a==2) || (a==4) || (a==7) || (a==8) || (a==10) ||
51 (a==14) || (a==18) || (a==23) || (a==26) || (a==28)) { 42 (a==14) || (a==18) || (a==23) || (a==26) || (a==28)) {
52 continue; 43 continue;
53 } 44 }
54 /* (32764^2 - 4) < 2^31, no bigint for >MP_8BIT needed) */ 45 /* (32764^2 - 4) < 2^31, no bigint for >MP_8BIT needed) */
55 if ((e = mp_set_long(&T1z, (unsigned long)a)) != MP_OKAY) { 46 mp_set_u32(&T1z, (uint32_t)a);
56 goto LBL_FU_ERR;
57 }
58 47
59 if ((e = mp_sqr(&T1z, &T1z)) != MP_OKAY) { 48 if ((err = mp_sqr(&T1z, &T1z)) != MP_OKAY) goto LBL_FU_ERR;
60 goto LBL_FU_ERR;
61 }
62 49
63 if ((e = mp_sub_d(&T1z, 4uL, &T1z)) != MP_OKAY) { 50 if ((err = mp_sub_d(&T1z, 4uL, &T1z)) != MP_OKAY) goto LBL_FU_ERR;
64 goto LBL_FU_ERR;
65 }
66 51
67 if ((e = mp_kronecker(&T1z, N, &j)) != MP_OKAY) { 52 if ((err = mp_kronecker(&T1z, N, &j)) != MP_OKAY) goto LBL_FU_ERR;
68 goto LBL_FU_ERR;
69 }
70 53
71 if (j == -1) { 54 if (j == -1) {
72 break; 55 break;
73 } 56 }
74 57
77 goto LBL_FU_ERR; 60 goto LBL_FU_ERR;
78 } 61 }
79 } 62 }
80 /* Tell it a composite and set return value accordingly */ 63 /* Tell it a composite and set return value accordingly */
81 if (a >= LTM_FROBENIUS_UNDERWOOD_A) { 64 if (a >= LTM_FROBENIUS_UNDERWOOD_A) {
82 e = MP_ITER; 65 err = MP_ITER;
83 goto LBL_FU_ERR; 66 goto LBL_FU_ERR;
84 } 67 }
85 /* Composite if N and (a+4)*(2*a+5) are not coprime */ 68 /* Composite if N and (a+4)*(2*a+5) are not coprime */
86 if ((e = mp_set_long(&T1z, (unsigned long)((a+4)*((2*a)+5)))) != MP_OKAY) { 69 mp_set_u32(&T1z, (uint32_t)((a+4)*((2*a)+5)));
87 goto LBL_FU_ERR;
88 }
89 70
90 if ((e = mp_gcd(N, &T1z, &T1z)) != MP_OKAY) { 71 if ((err = mp_gcd(N, &T1z, &T1z)) != MP_OKAY) goto LBL_FU_ERR;
91 goto LBL_FU_ERR;
92 }
93 72
94 if (!((T1z.used == 1) && (T1z.dp[0] == 1u))) { 73 if (!((T1z.used == 1) && (T1z.dp[0] == 1u))) goto LBL_FU_ERR;
95 goto LBL_FU_ERR;
96 }
97 74
98 ap2 = a + 2; 75 ap2 = a + 2;
99 if ((e = mp_add_d(N, 1uL, &Np1z)) != MP_OKAY) { 76 if ((err = mp_add_d(N, 1uL, &Np1z)) != MP_OKAY) goto LBL_FU_ERR;
100 goto LBL_FU_ERR;
101 }
102 77
103 mp_set(&sz, 1uL); 78 mp_set(&sz, 1uL);
104 mp_set(&tz, 2uL); 79 mp_set(&tz, 2uL);
105 length = mp_count_bits(&Np1z); 80 length = mp_count_bits(&Np1z);
106 81
108 /* 83 /*
109 * temp = (sz*(a*sz+2*tz))%N; 84 * temp = (sz*(a*sz+2*tz))%N;
110 * tz = ((tz-sz)*(tz+sz))%N; 85 * tz = ((tz-sz)*(tz+sz))%N;
111 * sz = temp; 86 * sz = temp;
112 */ 87 */
113 if ((e = mp_mul_2(&tz, &T2z)) != MP_OKAY) { 88 if ((err = mp_mul_2(&tz, &T2z)) != MP_OKAY) goto LBL_FU_ERR;
114 goto LBL_FU_ERR;
115 }
116 89
117 /* a = 0 at about 50% of the cases (non-square and odd input) */ 90 /* a = 0 at about 50% of the cases (non-square and odd input) */
118 if (a != 0) { 91 if (a != 0) {
119 if ((e = mp_mul_d(&sz, (mp_digit)a, &T1z)) != MP_OKAY) { 92 if ((err = mp_mul_d(&sz, (mp_digit)a, &T1z)) != MP_OKAY) goto LBL_FU_ERR;
120 goto LBL_FU_ERR; 93 if ((err = mp_add(&T1z, &T2z, &T2z)) != MP_OKAY) goto LBL_FU_ERR;
121 }
122 if ((e = mp_add(&T1z, &T2z, &T2z)) != MP_OKAY) {
123 goto LBL_FU_ERR;
124 }
125 } 94 }
126 95
127 if ((e = mp_mul(&T2z, &sz, &T1z)) != MP_OKAY) { 96 if ((err = mp_mul(&T2z, &sz, &T1z)) != MP_OKAY) goto LBL_FU_ERR;
128 goto LBL_FU_ERR; 97 if ((err = mp_sub(&tz, &sz, &T2z)) != MP_OKAY) goto LBL_FU_ERR;
129 } 98 if ((err = mp_add(&sz, &tz, &sz)) != MP_OKAY) goto LBL_FU_ERR;
130 if ((e = mp_sub(&tz, &sz, &T2z)) != MP_OKAY) { 99 if ((err = mp_mul(&sz, &T2z, &tz)) != MP_OKAY) goto LBL_FU_ERR;
131 goto LBL_FU_ERR; 100 if ((err = mp_mod(&tz, N, &tz)) != MP_OKAY) goto LBL_FU_ERR;
132 } 101 if ((err = mp_mod(&T1z, N, &sz)) != MP_OKAY) goto LBL_FU_ERR;
133 if ((e = mp_add(&sz, &tz, &sz)) != MP_OKAY) { 102 if (s_mp_get_bit(&Np1z, (unsigned int)i) == MP_YES) {
134 goto LBL_FU_ERR;
135 }
136 if ((e = mp_mul(&sz, &T2z, &tz)) != MP_OKAY) {
137 goto LBL_FU_ERR;
138 }
139 if ((e = mp_mod(&tz, N, &tz)) != MP_OKAY) {
140 goto LBL_FU_ERR;
141 }
142 if ((e = mp_mod(&T1z, N, &sz)) != MP_OKAY) {
143 goto LBL_FU_ERR;
144 }
145 if ((isset = mp_get_bit(&Np1z, i)) == MP_VAL) {
146 e = isset;
147 goto LBL_FU_ERR;
148 }
149 if (isset == MP_YES) {
150 /* 103 /*
151 * temp = (a+2) * sz + tz 104 * temp = (a+2) * sz + tz
152 * tz = 2 * tz - sz 105 * tz = 2 * tz - sz
153 * sz = temp 106 * sz = temp
154 */ 107 */
155 if (a == 0) { 108 if (a == 0) {
156 if ((e = mp_mul_2(&sz, &T1z)) != MP_OKAY) { 109 if ((err = mp_mul_2(&sz, &T1z)) != MP_OKAY) goto LBL_FU_ERR;
157 goto LBL_FU_ERR;
158 }
159 } else { 110 } else {
160 if ((e = mp_mul_d(&sz, (mp_digit)ap2, &T1z)) != MP_OKAY) { 111 if ((err = mp_mul_d(&sz, (mp_digit)ap2, &T1z)) != MP_OKAY) goto LBL_FU_ERR;
161 goto LBL_FU_ERR;
162 }
163 } 112 }
164 if ((e = mp_add(&T1z, &tz, &T1z)) != MP_OKAY) { 113 if ((err = mp_add(&T1z, &tz, &T1z)) != MP_OKAY) goto LBL_FU_ERR;
165 goto LBL_FU_ERR; 114 if ((err = mp_mul_2(&tz, &T2z)) != MP_OKAY) goto LBL_FU_ERR;
166 } 115 if ((err = mp_sub(&T2z, &sz, &tz)) != MP_OKAY) goto LBL_FU_ERR;
167 if ((e = mp_mul_2(&tz, &T2z)) != MP_OKAY) {
168 goto LBL_FU_ERR;
169 }
170 if ((e = mp_sub(&T2z, &sz, &tz)) != MP_OKAY) {
171 goto LBL_FU_ERR;
172 }
173 mp_exch(&sz, &T1z); 116 mp_exch(&sz, &T1z);
174 } 117 }
175 } 118 }
176 119
177 if ((e = mp_set_long(&T1z, (unsigned long)((2 * a) + 5))) != MP_OKAY) { 120 mp_set_u32(&T1z, (uint32_t)((2 * a) + 5));
178 goto LBL_FU_ERR; 121 if ((err = mp_mod(&T1z, N, &T1z)) != MP_OKAY) goto LBL_FU_ERR;
179 } 122 if (MP_IS_ZERO(&sz) && (mp_cmp(&tz, &T1z) == MP_EQ)) {
180 if ((e = mp_mod(&T1z, N, &T1z)) != MP_OKAY) {
181 goto LBL_FU_ERR;
182 }
183 if ((mp_iszero(&sz) != MP_NO) && (mp_cmp(&tz, &T1z) == MP_EQ)) {
184 *result = MP_YES; 123 *result = MP_YES;
185 goto LBL_FU_ERR;
186 } 124 }
187 125
188 LBL_FU_ERR: 126 LBL_FU_ERR:
189 mp_clear_multi(&tz, &sz, &Np1z, &T2z, &T1z, NULL); 127 mp_clear_multi(&tz, &sz, &Np1z, &T2z, &T1z, NULL);
190 return e; 128 return err;
191 } 129 }
192 130
193 #endif 131 #endif
194 #endif 132 #endif
195
196 /* ref: HEAD -> master, tag: v1.1.0 */
197 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
198 /* commit time: 2019-01-28 20:32:32 +0100 */