Mercurial > dropbear

comparison demo/demo.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
7 #define SLEEP 7 #define SLEEP
8 #endif 8 #endif
9 9
10 #include "tommath.h" 10 #include "tommath.h"
11 11
12 void ndraw(mp_int *a, char *name) 12 void ndraw(mp_int * a, char *name)
13 { 13 {
14 char buf[4096]; 14 char buf[16000];
15
15 printf("%s: ", name); 16 printf("%s: ", name);
16 mp_toradix(a, buf, 64); 17 mp_toradix(a, buf, 10);
17 printf("%s\n", buf); 18 printf("%s\n", buf);
18 } 19 }
19 20
20 static void draw(mp_int *a) 21 static void draw(mp_int * a)
21 { 22 {
22 ndraw(a, ""); 23 ndraw(a, "");
23 } 24 }
24 25
25 26
37 } 38 }
38 39
39 int myrng(unsigned char *dst, int len, void *dat) 40 int myrng(unsigned char *dst, int len, void *dat)
40 { 41 {
41 int x; 42 int x;
42 for (x = 0; x < len; x++) dst[x] = rand() & 0xFF; 43
44 for (x = 0; x < len; x++)
45 dst[x] = rand() & 0xFF;
43 return len; 46 return len;
44 } 47 }
45 48
46 49
47 50
48 char cmd[4096], buf[4096]; 51 char cmd[4096], buf[4096];
49 int main(void) 52 int main(void)
50 { 53 {
51 mp_int a, b, c, d, e, f; 54 mp_int a, b, c, d, e, f;
52 unsigned long expt_n, add_n, sub_n, mul_n, div_n, sqr_n, mul2d_n, div2d_n, gcd_n, lcm_n, inv_n, 55 unsigned long expt_n, add_n, sub_n, mul_n, div_n, sqr_n, mul2d_n, div2d_n,
53 div2_n, mul2_n, add_d_n, sub_d_n, t; 56 gcd_n, lcm_n, inv_n, div2_n, mul2_n, add_d_n, sub_d_n, t;
54 unsigned rr; 57 unsigned rr;
55 int i, n, err, cnt, ix, old_kara_m, old_kara_s; 58 int i, n, err, cnt, ix, old_kara_m, old_kara_s;
59 mp_digit mp;
56 60
57 61
58 mp_init(&a); 62 mp_init(&a);
59 mp_init(&b); 63 mp_init(&b);
60 mp_init(&c); 64 mp_init(&c);
63 mp_init(&f); 67 mp_init(&f);
64 68
65 srand(time(NULL)); 69 srand(time(NULL));
66 70
67 #if 0 71 #if 0
68 // test mp_get_int 72 // test montgomery
69 printf("Testing: mp_get_int\n"); 73 printf("Testing montgomery...\n");
70 for(i=0;i<1000;++i) { 74 for (i = 1; i < 10; i++) {
71 t = ((unsigned long)rand()*rand()+1)&0xFFFFFFFF; 75 printf("Testing digit size: %d\n", i);
72 mp_set_int(&a,t); 76 for (n = 0; n < 1000; n++) {
73 if (t!=mp_get_int(&a)) { 77 mp_rand(&a, i);
78 a.dp[0] |= 1;
79
80 // let's see if R is right
81 mp_montgomery_calc_normalization(&b, &a);
82 mp_montgomery_setup(&a, &mp);
83
84 // now test a random reduction
85 for (ix = 0; ix < 100; ix++) {
86 mp_rand(&c, 1 + abs(rand()) % (2*i));
87 mp_copy(&c, &d);
88 mp_copy(&c, &e);
89
90 mp_mod(&d, &a, &d);
91 mp_montgomery_reduce(&c, &a, mp);
92 mp_mulmod(&c, &b, &a, &c);
93
94 if (mp_cmp(&c, &d) != MP_EQ) {
95 printf("d = e mod a, c = e MOD a\n");
96 mp_todecimal(&a, buf); printf("a = %s\n", buf);
97 mp_todecimal(&e, buf); printf("e = %s\n", buf);
98 mp_todecimal(&d, buf); printf("d = %s\n", buf);
99 mp_todecimal(&c, buf); printf("c = %s\n", buf);
100 printf("compare no compare!\n"); exit(EXIT_FAILURE); }
101 }
102 }
103 }
104 printf("done\n");
105
106 // test mp_get_int
107 printf("Testing: mp_get_int\n");
108 for (i = 0; i < 1000; ++i) {
109 t = ((unsigned long) rand() * rand() + 1) & 0xFFFFFFFF;
110 mp_set_int(&a, t);
111 if (t != mp_get_int(&a)) {
112 printf("mp_get_int() bad result!\n");
113 return 1;
114 }
115 }
116 mp_set_int(&a, 0);
117 if (mp_get_int(&a) != 0) {
74 printf("mp_get_int() bad result!\n"); 118 printf("mp_get_int() bad result!\n");
75 return 1; 119 return 1;
76 } 120 }
77 } 121 mp_set_int(&a, 0xffffffff);
78 mp_set_int(&a,0); 122 if (mp_get_int(&a) != 0xffffffff) {
79 if (mp_get_int(&a)!=0) 123 printf("mp_get_int() bad result!\n");
80 { printf("mp_get_int() bad result!\n");
81 return 1;
82 }
83 mp_set_int(&a,0xffffffff);
84 if (mp_get_int(&a)!=0xffffffff)
85 { printf("mp_get_int() bad result!\n");
86 return 1;
87 }
88
89 // test mp_sqrt
90 printf("Testing: mp_sqrt\n");
91 for (i=0;i<1000;++i) {
92 printf("%6d\r", i); fflush(stdout);
93 n = (rand()&15)+1;
94 mp_rand(&a,n);
95 if (mp_sqrt(&a,&b) != MP_OKAY)
96 { printf("mp_sqrt() error!\n");
97 return 1; 124 return 1;
98 } 125 }
99 mp_n_root(&a,2,&a); 126 // test mp_sqrt
100 if (mp_cmp_mag(&b,&a) != MP_EQ) 127 printf("Testing: mp_sqrt\n");
101 { printf("mp_sqrt() bad result!\n"); 128 for (i = 0; i < 1000; ++i) {
102 return 1; 129 printf("%6d\r", i);
103 } 130 fflush(stdout);
104 } 131 n = (rand() & 15) + 1;
105 132 mp_rand(&a, n);
106 printf("\nTesting: mp_is_square\n"); 133 if (mp_sqrt(&a, &b) != MP_OKAY) {
107 for (i=0;i<1000;++i) { 134 printf("mp_sqrt() error!\n");
108 printf("%6d\r", i); fflush(stdout); 135 return 1;
109 136 }
110 /* test mp_is_square false negatives */ 137 mp_n_root(&a, 2, &a);
111 n = (rand()&7)+1; 138 if (mp_cmp_mag(&b, &a) != MP_EQ) {
112 mp_rand(&a,n); 139 printf("mp_sqrt() bad result!\n");
113 mp_sqr(&a,&a); 140 return 1;
114 if (mp_is_square(&a,&n)!=MP_OKAY) { 141 }
115 printf("fn:mp_is_square() error!\n"); 142 }
116 return 1; 143
117 } 144 printf("\nTesting: mp_is_square\n");
118 if (n==0) { 145 for (i = 0; i < 1000; ++i) {
119 printf("fn:mp_is_square() bad result!\n"); 146 printf("%6d\r", i);
120 return 1; 147 fflush(stdout);
121 } 148
122 149 /* test mp_is_square false negatives */
123 /* test for false positives */ 150 n = (rand() & 7) + 1;
124 mp_add_d(&a, 1, &a); 151 mp_rand(&a, n);
125 if (mp_is_square(&a,&n)!=MP_OKAY) { 152 mp_sqr(&a, &a);
126 printf("fp:mp_is_square() error!\n"); 153 if (mp_is_square(&a, &n) != MP_OKAY) {
127 return 1; 154 printf("fn:mp_is_square() error!\n");
128 } 155 return 1;
129 if (n==1) { 156 }
130 printf("fp:mp_is_square() bad result!\n"); 157 if (n == 0) {
131 return 1; 158 printf("fn:mp_is_square() bad result!\n");
132 } 159 return 1;
133 160 }
134 } 161
135 printf("\n\n"); 162 /* test for false positives */
163 mp_add_d(&a, 1, &a);
164 if (mp_is_square(&a, &n) != MP_OKAY) {
165 printf("fp:mp_is_square() error!\n");
166 return 1;
167 }
168 if (n == 1) {
169 printf("fp:mp_is_square() bad result!\n");
170 return 1;
171 }
172
173 }
174 printf("\n\n");
136 175
137 /* test for size */ 176 /* test for size */
138 for (ix = 10; ix < 256; ix++) { 177 for (ix = 10; ix < 128; ix++) {
139 printf("Testing (not safe-prime): %9d bits \r", ix); fflush(stdout); 178 printf("Testing (not safe-prime): %9d bits \r", ix);
140 err = mp_prime_random_ex(&a, 8, ix, (rand()&1)?LTM_PRIME_2MSB_OFF:LTM_PRIME_2MSB_ON, myrng, NULL); 179 fflush(stdout);
141 if (err != MP_OKAY) { 180 err =
142 printf("failed with err code %d\n", err); 181 mp_prime_random_ex(&a, 8, ix,
143 return EXIT_FAILURE; 182 (rand() & 1) ? LTM_PRIME_2MSB_OFF :
144 } 183 LTM_PRIME_2MSB_ON, myrng, NULL);
145 if (mp_count_bits(&a) != ix) { 184 if (err != MP_OKAY) {
146 printf("Prime is %d not %d bits!!!\n", mp_count_bits(&a), ix); 185 printf("failed with err code %d\n", err);
147 return EXIT_FAILURE; 186 return EXIT_FAILURE;
148 } 187 }
149 } 188 if (mp_count_bits(&a) != ix) {
150 189 printf("Prime is %d not %d bits!!!\n", mp_count_bits(&a), ix);
151 for (ix = 16; ix < 256; ix++) { 190 return EXIT_FAILURE;
152 printf("Testing ( safe-prime): %9d bits \r", ix); fflush(stdout); 191 }
153 err = mp_prime_random_ex(&a, 8, ix, ((rand()&1)?LTM_PRIME_2MSB_OFF:LTM_PRIME_2MSB_ON)|LTM_PRIME_SAFE, myrng, NULL); 192 }
154 if (err != MP_OKAY) { 193
155 printf("failed with err code %d\n", err); 194 for (ix = 16; ix < 128; ix++) {
156 return EXIT_FAILURE; 195 printf("Testing ( safe-prime): %9d bits \r", ix);
157 } 196 fflush(stdout);
158 if (mp_count_bits(&a) != ix) { 197 err =
159 printf("Prime is %d not %d bits!!!\n", mp_count_bits(&a), ix); 198 mp_prime_random_ex(&a, 8, ix,
160 return EXIT_FAILURE; 199 ((rand() & 1) ? LTM_PRIME_2MSB_OFF :
161 } 200 LTM_PRIME_2MSB_ON) | LTM_PRIME_SAFE, myrng,
162 /* let's see if it's really a safe prime */ 201 NULL);
163 mp_sub_d(&a, 1, &a); 202 if (err != MP_OKAY) {
164 mp_div_2(&a, &a); 203 printf("failed with err code %d\n", err);
165 mp_prime_is_prime(&a, 8, &cnt); 204 return EXIT_FAILURE;
166 if (cnt != MP_YES) { 205 }
167 printf("sub is not prime!\n"); 206 if (mp_count_bits(&a) != ix) {
168 return EXIT_FAILURE; 207 printf("Prime is %d not %d bits!!!\n", mp_count_bits(&a), ix);
169 } 208 return EXIT_FAILURE;
209 }
210 /* let's see if it's really a safe prime */
211 mp_sub_d(&a, 1, &a);
212 mp_div_2(&a, &a);
213 mp_prime_is_prime(&a, 8, &cnt);
214 if (cnt != MP_YES) {
215 printf("sub is not prime!\n");
216 return EXIT_FAILURE;
217 }
170 } 218 }
171 219
172 printf("\n\n"); 220 printf("\n\n");
173 221
174 mp_read_radix(&a, "123456", 10); 222 mp_read_radix(&a, "123456", 10);
192 240
193 /* test mp_cnt_lsb */ 241 /* test mp_cnt_lsb */
194 printf("testing mp_cnt_lsb...\n"); 242 printf("testing mp_cnt_lsb...\n");
195 mp_set(&a, 1); 243 mp_set(&a, 1);
196 for (ix = 0; ix < 1024; ix++) { 244 for (ix = 0; ix < 1024; ix++) {
197 if (mp_cnt_lsb(&a) != ix) { 245 if (mp_cnt_lsb(&a) != ix) {
198 printf("Failed at %d, %d\n", ix, mp_cnt_lsb(&a)); 246 printf("Failed at %d, %d\n", ix, mp_cnt_lsb(&a));
199 return 0; 247 return 0;
200 } 248 }
201 mp_mul_2(&a, &a); 249 mp_mul_2(&a, &a);
202 } 250 }
203 251
204 /* test mp_reduce_2k */ 252 /* test mp_reduce_2k */
205 printf("Testing mp_reduce_2k...\n"); 253 printf("Testing mp_reduce_2k...\n");
206 for (cnt = 3; cnt <= 128; ++cnt) { 254 for (cnt = 3; cnt <= 128; ++cnt) {
207 mp_digit tmp; 255 mp_digit tmp;
208 mp_2expt(&a, cnt); 256
209 mp_sub_d(&a, 2, &a); /* a = 2**cnt - 2 */ 257 mp_2expt(&a, cnt);
210 258 mp_sub_d(&a, 2, &a); /* a = 2**cnt - 2 */
211 259
212 printf("\nTesting %4d bits", cnt); 260
213 printf("(%d)", mp_reduce_is_2k(&a)); 261 printf("\nTesting %4d bits", cnt);
214 mp_reduce_2k_setup(&a, &tmp); 262 printf("(%d)", mp_reduce_is_2k(&a));
215 printf("(%d)", tmp); 263 mp_reduce_2k_setup(&a, &tmp);
216 for (ix = 0; ix < 1000; ix++) { 264 printf("(%d)", tmp);
217 if (!(ix & 127)) {printf("."); fflush(stdout); } 265 for (ix = 0; ix < 1000; ix++) {
218 mp_rand(&b, (cnt/DIGIT_BIT + 1) * 2); 266 if (!(ix & 127)) {
219 mp_copy(&c, &b); 267 printf(".");
220 mp_mod(&c, &a, &c); 268 fflush(stdout);
221 mp_reduce_2k(&b, &a, 1); 269 }
222 if (mp_cmp(&c, &b)) { 270 mp_rand(&b, (cnt / DIGIT_BIT + 1) * 2);
223 printf("FAILED\n"); 271 mp_copy(&c, &b);
224 exit(0); 272 mp_mod(&c, &a, &c);
225 } 273 mp_reduce_2k(&b, &a, 2);
226 } 274 if (mp_cmp(&c, &b)) {
227 } 275 printf("FAILED\n");
276 exit(0);
277 }
278 }
279 }
228 280
229 /* test mp_div_3 */ 281 /* test mp_div_3 */
230 printf("Testing mp_div_3...\n"); 282 printf("Testing mp_div_3...\n");
231 mp_set(&d, 3); 283 mp_set(&d, 3);
232 for (cnt = 0; cnt < 10000; ) { 284 for (cnt = 0; cnt < 10000;) {
233 mp_digit r1, r2; 285 mp_digit r1, r2;
234 286
235 if (!(++cnt & 127)) printf("%9d\r", cnt); 287 if (!(++cnt & 127))
288 printf("%9d\r", cnt);
236 mp_rand(&a, abs(rand()) % 128 + 1); 289 mp_rand(&a, abs(rand()) % 128 + 1);
237 mp_div(&a, &d, &b, &e); 290 mp_div(&a, &d, &b, &e);
238 mp_div_3(&a, &c, &r2); 291 mp_div_3(&a, &c, &r2);
239 292
240 if (mp_cmp(&b, &c) || mp_cmp_d(&e, r2)) { 293 if (mp_cmp(&b, &c) || mp_cmp_d(&e, r2)) {
241 printf("\n\nmp_div_3 => Failure\n"); 294 printf("\n\nmp_div_3 => Failure\n");
242 } 295 }
243 } 296 }
244 printf("\n\nPassed div_3 testing\n"); 297 printf("\n\nPassed div_3 testing\n");
245 298
246 /* test the DR reduction */ 299 /* test the DR reduction */
247 printf("testing mp_dr_reduce...\n"); 300 printf("testing mp_dr_reduce...\n");
248 for (cnt = 2; cnt < 32; cnt++) { 301 for (cnt = 2; cnt < 32; cnt++) {
249 printf("%d digit modulus\n", cnt); 302 printf("%d digit modulus\n", cnt);
250 mp_grow(&a, cnt); 303 mp_grow(&a, cnt);
251 mp_zero(&a); 304 mp_zero(&a);
252 for (ix = 1; ix < cnt; ix++) { 305 for (ix = 1; ix < cnt; ix++) {
253 a.dp[ix] = MP_MASK; 306 a.dp[ix] = MP_MASK;
254 } 307 }
255 a.used = cnt; 308 a.used = cnt;
256 a.dp[0] = 3; 309 a.dp[0] = 3;
257 310
258 mp_rand(&b, cnt - 1); 311 mp_rand(&b, cnt - 1);
259 mp_copy(&b, &c); 312 mp_copy(&b, &c);
260 313
261 rr = 0; 314 rr = 0;
262 do { 315 do {
263 if (!(rr & 127)) { printf("%9lu\r", rr); fflush(stdout); } 316 if (!(rr & 127)) {
264 mp_sqr(&b, &b); mp_add_d(&b, 1, &b); 317 printf("%9lu\r", rr);
265 mp_copy(&b, &c); 318 fflush(stdout);
266 319 }
267 mp_mod(&b, &a, &b); 320 mp_sqr(&b, &b);
268 mp_dr_reduce(&c, &a, (((mp_digit)1)<<DIGIT_BIT)-a.dp[0]); 321 mp_add_d(&b, 1, &b);
269 322 mp_copy(&b, &c);
270 if (mp_cmp(&b, &c) != MP_EQ) { 323
271 printf("Failed on trial %lu\n", rr); exit(-1); 324 mp_mod(&b, &a, &b);
272 325 mp_dr_reduce(&c, &a, (((mp_digit) 1) << DIGIT_BIT) - a.dp[0]);
273 } 326
327 if (mp_cmp(&b, &c) != MP_EQ) {
328 printf("Failed on trial %lu\n", rr);
329 exit(-1);
330
331 }
274 } while (++rr < 500); 332 } while (++rr < 500);
275 printf("Passed DR test for %d digits\n", cnt); 333 printf("Passed DR test for %d digits\n", cnt);
276 } 334 }
277 335
278 #endif 336 #endif
279 337
338 /* test the mp_reduce_2k_l code */
339 #if 0
340 #if 0
341 /* first load P with 2^1024 - 0x2A434 B9FDEC95 D8F9D550 FFFFFFFF FFFFFFFF */
342 mp_2expt(&a, 1024);
343 mp_read_radix(&b, "2A434B9FDEC95D8F9D550FFFFFFFFFFFFFFFF", 16);
344 mp_sub(&a, &b, &a);
345 #elif 1
346 /* p = 2^2048 - 0x1 00000000 00000000 00000000 00000000 4945DDBF 8EA2A91D 5776399B B83E188F */
347 mp_2expt(&a, 2048);
348 mp_read_radix(&b,
349 "1000000000000000000000000000000004945DDBF8EA2A91D5776399BB83E188F",
350 16);
351 mp_sub(&a, &b, &a);
352 #endif
353
354 mp_todecimal(&a, buf);
355 printf("p==%s\n", buf);
356 /* now mp_reduce_is_2k_l() should return */
357 if (mp_reduce_is_2k_l(&a) != 1) {
358 printf("mp_reduce_is_2k_l() return 0, should be 1\n");
359 return EXIT_FAILURE;
360 }
361 mp_reduce_2k_setup_l(&a, &d);
362 /* now do a million square+1 to see if it varies */
363 mp_rand(&b, 64);
364 mp_mod(&b, &a, &b);
365 mp_copy(&b, &c);
366 printf("testing mp_reduce_2k_l...");
367 fflush(stdout);
368 for (cnt = 0; cnt < (1UL << 20); cnt++) {
369 mp_sqr(&b, &b);
370 mp_add_d(&b, 1, &b);
371 mp_reduce_2k_l(&b, &a, &d);
372 mp_sqr(&c, &c);
373 mp_add_d(&c, 1, &c);
374 mp_mod(&c, &a, &c);
375 if (mp_cmp(&b, &c) != MP_EQ) {
376 printf("mp_reduce_2k_l() failed at step %lu\n", cnt);
377 mp_tohex(&b, buf);
378 printf("b == %s\n", buf);
379 mp_tohex(&c, buf);
380 printf("c == %s\n", buf);
381 return EXIT_FAILURE;
382 }
383 }
384 printf("...Passed\n");
385 #endif
386
280 div2_n = mul2_n = inv_n = expt_n = lcm_n = gcd_n = add_n = 387 div2_n = mul2_n = inv_n = expt_n = lcm_n = gcd_n = add_n =
281 sub_n = mul_n = div_n = sqr_n = mul2d_n = div2d_n = cnt = add_d_n = sub_d_n= 0; 388 sub_n = mul_n = div_n = sqr_n = mul2d_n = div2d_n = cnt = add_d_n =
389 sub_d_n = 0;
282 390
283 /* force KARA and TOOM to enable despite cutoffs */ 391 /* force KARA and TOOM to enable despite cutoffs */
284 KARATSUBA_SQR_CUTOFF = KARATSUBA_MUL_CUTOFF = 110; 392 KARATSUBA_SQR_CUTOFF = KARATSUBA_MUL_CUTOFF = 110;
285 TOOM_SQR_CUTOFF = TOOM_MUL_CUTOFF = 150; 393 TOOM_SQR_CUTOFF = TOOM_MUL_CUTOFF = 150;
286 394
287 for (;;) { 395 for (;;) {
288 /* randomly clear and re-init one variable, this has the affect of triming the alloc space */ 396 /* randomly clear and re-init one variable, this has the affect of triming the alloc space */
289 switch (abs(rand()) % 7) { 397 switch (abs(rand()) % 7) {
290 case 0: mp_clear(&a); mp_init(&a); break; 398 case 0:
291 case 1: mp_clear(&b); mp_init(&b); break; 399 mp_clear(&a);
292 case 2: mp_clear(&c); mp_init(&c); break; 400 mp_init(&a);
293 case 3: mp_clear(&d); mp_init(&d); break; 401 break;
294 case 4: mp_clear(&e); mp_init(&e); break; 402 case 1:
295 case 5: mp_clear(&f); mp_init(&f); break; 403 mp_clear(&b);
296 case 6: break; /* don't clear any */ 404 mp_init(&b);
297 } 405 break;
298 406 case 2:
299 407 mp_clear(&c);
300 printf("%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu ", add_n, sub_n, mul_n, div_n, sqr_n, mul2d_n, div2d_n, gcd_n, lcm_n, expt_n, inv_n, div2_n, mul2_n, add_d_n, sub_d_n); 408 mp_init(&c);
301 fgets(cmd, 4095, stdin); 409 break;
302 cmd[strlen(cmd)-1] = 0; 410 case 3:
303 printf("%s ]\r",cmd); fflush(stdout); 411 mp_clear(&d);
304 if (!strcmp(cmd, "mul2d")) { ++mul2d_n; 412 mp_init(&d);
305 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 413 break;
306 fgets(buf, 4095, stdin); sscanf(buf, "%d", &rr); 414 case 4:
307 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 415 mp_clear(&e);
308 416 mp_init(&e);
309 mp_mul_2d(&a, rr, &a); 417 break;
310 a.sign = b.sign; 418 case 5:
311 if (mp_cmp(&a, &b) != MP_EQ) { 419 mp_clear(&f);
312 printf("mul2d failed, rr == %d\n",rr); 420 mp_init(&f);
313 draw(&a); 421 break;
314 draw(&b); 422 case 6:
315 return 0; 423 break; /* don't clear any */
316 } 424 }
317 } else if (!strcmp(cmd, "div2d")) { ++div2d_n; 425
318 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 426
319 fgets(buf, 4095, stdin); sscanf(buf, "%d", &rr); 427 printf
320 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 428 ("%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu ",
321 429 add_n, sub_n, mul_n, div_n, sqr_n, mul2d_n, div2d_n, gcd_n, lcm_n,
322 mp_div_2d(&a, rr, &a, &e); 430 expt_n, inv_n, div2_n, mul2_n, add_d_n, sub_d_n);
323 a.sign = b.sign; 431 fgets(cmd, 4095, stdin);
324 if (a.used == b.used && a.used == 0) { a.sign = b.sign = MP_ZPOS; } 432 cmd[strlen(cmd) - 1] = 0;
325 if (mp_cmp(&a, &b) != MP_EQ) { 433 printf("%s ]\r", cmd);
326 printf("div2d failed, rr == %d\n",rr); 434 fflush(stdout);
327 draw(&a); 435 if (!strcmp(cmd, "mul2d")) {
328 draw(&b); 436 ++mul2d_n;
329 return 0; 437 fgets(buf, 4095, stdin);
330 } 438 mp_read_radix(&a, buf, 64);
331 } else if (!strcmp(cmd, "add")) { ++add_n; 439 fgets(buf, 4095, stdin);
332 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 440 sscanf(buf, "%d", &rr);
333 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 441 fgets(buf, 4095, stdin);
334 fgets(buf, 4095, stdin); mp_read_radix(&c, buf, 64); 442 mp_read_radix(&b, buf, 64);
335 mp_copy(&a, &d); 443
336 mp_add(&d, &b, &d); 444 mp_mul_2d(&a, rr, &a);
337 if (mp_cmp(&c, &d) != MP_EQ) { 445 a.sign = b.sign;
338 printf("add %lu failure!\n", add_n); 446 if (mp_cmp(&a, &b) != MP_EQ) {
339 draw(&a);draw(&b);draw(&c);draw(&d); 447 printf("mul2d failed, rr == %d\n", rr);
340 return 0; 448 draw(&a);
341 } 449 draw(&b);
342 450 return 0;
343 /* test the sign/unsigned storage functions */ 451 }
344 452 } else if (!strcmp(cmd, "div2d")) {
345 rr = mp_signed_bin_size(&c); 453 ++div2d_n;
346 mp_to_signed_bin(&c, (unsigned char *)cmd); 454 fgets(buf, 4095, stdin);
347 memset(cmd+rr, rand()&255, sizeof(cmd)-rr); 455 mp_read_radix(&a, buf, 64);
348 mp_read_signed_bin(&d, (unsigned char *)cmd, rr); 456 fgets(buf, 4095, stdin);
349 if (mp_cmp(&c, &d) != MP_EQ) { 457 sscanf(buf, "%d", &rr);
350 printf("mp_signed_bin failure!\n"); 458 fgets(buf, 4095, stdin);
351 draw(&c); 459 mp_read_radix(&b, buf, 64);
352 draw(&d); 460
353 return 0; 461 mp_div_2d(&a, rr, &a, &e);
354 } 462 a.sign = b.sign;
355 463 if (a.used == b.used && a.used == 0) {
356 464 a.sign = b.sign = MP_ZPOS;
357 rr = mp_unsigned_bin_size(&c); 465 }
358 mp_to_unsigned_bin(&c, (unsigned char *)cmd); 466 if (mp_cmp(&a, &b) != MP_EQ) {
359 memset(cmd+rr, rand()&255, sizeof(cmd)-rr); 467 printf("div2d failed, rr == %d\n", rr);
360 mp_read_unsigned_bin(&d, (unsigned char *)cmd, rr); 468 draw(&a);
361 if (mp_cmp_mag(&c, &d) != MP_EQ) { 469 draw(&b);
362 printf("mp_unsigned_bin failure!\n"); 470 return 0;
363 draw(&c); 471 }
364 draw(&d); 472 } else if (!strcmp(cmd, "add")) {
365 return 0; 473 ++add_n;
366 } 474 fgets(buf, 4095, stdin);
367 475 mp_read_radix(&a, buf, 64);
368 } else if (!strcmp(cmd, "sub")) { ++sub_n; 476 fgets(buf, 4095, stdin);
369 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 477 mp_read_radix(&b, buf, 64);
370 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 478 fgets(buf, 4095, stdin);
371 fgets(buf, 4095, stdin); mp_read_radix(&c, buf, 64); 479 mp_read_radix(&c, buf, 64);
372 mp_copy(&a, &d); 480 mp_copy(&a, &d);
373 mp_sub(&d, &b, &d); 481 mp_add(&d, &b, &d);
374 if (mp_cmp(&c, &d) != MP_EQ) { 482 if (mp_cmp(&c, &d) != MP_EQ) {
375 printf("sub %lu failure!\n", sub_n); 483 printf("add %lu failure!\n", add_n);
376 draw(&a);draw(&b);draw(&c);draw(&d); 484 draw(&a);
377 return 0; 485 draw(&b);
378 } 486 draw(&c);
379 } else if (!strcmp(cmd, "mul")) { ++mul_n; 487 draw(&d);
380 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 488 return 0;
381 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 489 }
382 fgets(buf, 4095, stdin); mp_read_radix(&c, buf, 64); 490
383 mp_copy(&a, &d); 491 /* test the sign/unsigned storage functions */
384 mp_mul(&d, &b, &d); 492
385 if (mp_cmp(&c, &d) != MP_EQ) { 493 rr = mp_signed_bin_size(&c);
386 printf("mul %lu failure!\n", mul_n); 494 mp_to_signed_bin(&c, (unsigned char *) cmd);
387 draw(&a);draw(&b);draw(&c);draw(&d); 495 memset(cmd + rr, rand() & 255, sizeof(cmd) - rr);
388 return 0; 496 mp_read_signed_bin(&d, (unsigned char *) cmd, rr);
389 } 497 if (mp_cmp(&c, &d) != MP_EQ) {
390 } else if (!strcmp(cmd, "div")) { ++div_n; 498 printf("mp_signed_bin failure!\n");
391 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 499 draw(&c);
392 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 500 draw(&d);
393 fgets(buf, 4095, stdin); mp_read_radix(&c, buf, 64); 501 return 0;
394 fgets(buf, 4095, stdin); mp_read_radix(&d, buf, 64); 502 }
395 503
396 mp_div(&a, &b, &e, &f); 504
397 if (mp_cmp(&c, &e) != MP_EQ || mp_cmp(&d, &f) != MP_EQ) { 505 rr = mp_unsigned_bin_size(&c);
398 printf("div %lu failure!\n", div_n); 506 mp_to_unsigned_bin(&c, (unsigned char *) cmd);
399 draw(&a);draw(&b);draw(&c);draw(&d); draw(&e); draw(&f); 507 memset(cmd + rr, rand() & 255, sizeof(cmd) - rr);
400 return 0; 508 mp_read_unsigned_bin(&d, (unsigned char *) cmd, rr);
401 } 509 if (mp_cmp_mag(&c, &d) != MP_EQ) {
402 510 printf("mp_unsigned_bin failure!\n");
403 } else if (!strcmp(cmd, "sqr")) { ++sqr_n; 511 draw(&c);
404 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 512 draw(&d);
405 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 513 return 0;
406 mp_copy(&a, &c); 514 }
407 mp_sqr(&c, &c); 515
408 if (mp_cmp(&b, &c) != MP_EQ) { 516 } else if (!strcmp(cmd, "sub")) {
409 printf("sqr %lu failure!\n", sqr_n); 517 ++sub_n;
410 draw(&a);draw(&b);draw(&c); 518 fgets(buf, 4095, stdin);
411 return 0; 519 mp_read_radix(&a, buf, 64);
412 } 520 fgets(buf, 4095, stdin);
413 } else if (!strcmp(cmd, "gcd")) { ++gcd_n; 521 mp_read_radix(&b, buf, 64);
414 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 522 fgets(buf, 4095, stdin);
415 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 523 mp_read_radix(&c, buf, 64);
416 fgets(buf, 4095, stdin); mp_read_radix(&c, buf, 64); 524 mp_copy(&a, &d);
417 mp_copy(&a, &d); 525 mp_sub(&d, &b, &d);
418 mp_gcd(&d, &b, &d); 526 if (mp_cmp(&c, &d) != MP_EQ) {
419 d.sign = c.sign; 527 printf("sub %lu failure!\n", sub_n);
420 if (mp_cmp(&c, &d) != MP_EQ) { 528 draw(&a);
421 printf("gcd %lu failure!\n", gcd_n); 529 draw(&b);
422 draw(&a);draw(&b);draw(&c);draw(&d); 530 draw(&c);
423 return 0; 531 draw(&d);
424 } 532 return 0;
425 } else if (!strcmp(cmd, "lcm")) { ++lcm_n; 533 }
426 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 534 } else if (!strcmp(cmd, "mul")) {
427 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 535 ++mul_n;
428 fgets(buf, 4095, stdin); mp_read_radix(&c, buf, 64); 536 fgets(buf, 4095, stdin);
429 mp_copy(&a, &d); 537 mp_read_radix(&a, buf, 64);
430 mp_lcm(&d, &b, &d); 538 fgets(buf, 4095, stdin);
431 d.sign = c.sign; 539 mp_read_radix(&b, buf, 64);
432 if (mp_cmp(&c, &d) != MP_EQ) { 540 fgets(buf, 4095, stdin);
433 printf("lcm %lu failure!\n", lcm_n); 541 mp_read_radix(&c, buf, 64);
434 draw(&a);draw(&b);draw(&c);draw(&d); 542 mp_copy(&a, &d);
435 return 0; 543 mp_mul(&d, &b, &d);
436 } 544 if (mp_cmp(&c, &d) != MP_EQ) {
437 } else if (!strcmp(cmd, "expt")) { ++expt_n; 545 printf("mul %lu failure!\n", mul_n);
438 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 546 draw(&a);
439 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 547 draw(&b);
440 fgets(buf, 4095, stdin); mp_read_radix(&c, buf, 64); 548 draw(&c);
441 fgets(buf, 4095, stdin); mp_read_radix(&d, buf, 64); 549 draw(&d);
442 mp_copy(&a, &e); 550 return 0;
443 mp_exptmod(&e, &b, &c, &e); 551 }
444 if (mp_cmp(&d, &e) != MP_EQ) { 552 } else if (!strcmp(cmd, "div")) {
445 printf("expt %lu failure!\n", expt_n); 553 ++div_n;
446 draw(&a);draw(&b);draw(&c);draw(&d); draw(&e); 554 fgets(buf, 4095, stdin);
447 return 0; 555 mp_read_radix(&a, buf, 64);
448 } 556 fgets(buf, 4095, stdin);
449 } else if (!strcmp(cmd, "invmod")) { ++inv_n; 557 mp_read_radix(&b, buf, 64);
450 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 558 fgets(buf, 4095, stdin);
451 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 559 mp_read_radix(&c, buf, 64);
452 fgets(buf, 4095, stdin); mp_read_radix(&c, buf, 64); 560 fgets(buf, 4095, stdin);
453 mp_invmod(&a, &b, &d); 561 mp_read_radix(&d, buf, 64);
454 mp_mulmod(&d,&a,&b,&e); 562
455 if (mp_cmp_d(&e, 1) != MP_EQ) { 563 mp_div(&a, &b, &e, &f);
456 printf("inv [wrong value from MPI?!] failure\n"); 564 if (mp_cmp(&c, &e) != MP_EQ || mp_cmp(&d, &f) != MP_EQ) {
457 draw(&a);draw(&b);draw(&c);draw(&d); 565 printf("div %lu %d, %d, failure!\n", div_n, mp_cmp(&c, &e),
458 mp_gcd(&a, &b, &e); 566 mp_cmp(&d, &f));
459 draw(&e); 567 draw(&a);
460 return 0; 568 draw(&b);
461 } 569 draw(&c);
462 570 draw(&d);
463 } else if (!strcmp(cmd, "div2")) { ++div2_n; 571 draw(&e);
464 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 572 draw(&f);
465 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 573 return 0;
466 mp_div_2(&a, &c); 574 }
467 if (mp_cmp(&c, &b) != MP_EQ) { 575
468 printf("div_2 %lu failure\n", div2_n); 576 } else if (!strcmp(cmd, "sqr")) {
469 draw(&a); 577 ++sqr_n;
470 draw(&b); 578 fgets(buf, 4095, stdin);
471 draw(&c); 579 mp_read_radix(&a, buf, 64);
472 return 0; 580 fgets(buf, 4095, stdin);
473 } 581 mp_read_radix(&b, buf, 64);
474 } else if (!strcmp(cmd, "mul2")) { ++mul2_n; 582 mp_copy(&a, &c);
475 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 583 mp_sqr(&c, &c);
476 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 584 if (mp_cmp(&b, &c) != MP_EQ) {
477 mp_mul_2(&a, &c); 585 printf("sqr %lu failure!\n", sqr_n);
478 if (mp_cmp(&c, &b) != MP_EQ) { 586 draw(&a);
479 printf("mul_2 %lu failure\n", mul2_n); 587 draw(&b);
480 draw(&a); 588 draw(&c);
481 draw(&b); 589 return 0;
482 draw(&c); 590 }
483 return 0; 591 } else if (!strcmp(cmd, "gcd")) {
484 } 592 ++gcd_n;
485 } else if (!strcmp(cmd, "add_d")) { ++add_d_n; 593 fgets(buf, 4095, stdin);
486 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 594 mp_read_radix(&a, buf, 64);
487 fgets(buf, 4095, stdin); sscanf(buf, "%d", &ix); 595 fgets(buf, 4095, stdin);
488 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 596 mp_read_radix(&b, buf, 64);
489 mp_add_d(&a, ix, &c); 597 fgets(buf, 4095, stdin);
490 if (mp_cmp(&b, &c) != MP_EQ) { 598 mp_read_radix(&c, buf, 64);
491 printf("add_d %lu failure\n", add_d_n); 599 mp_copy(&a, &d);
492 draw(&a); 600 mp_gcd(&d, &b, &d);
493 draw(&b); 601 d.sign = c.sign;
494 draw(&c); 602 if (mp_cmp(&c, &d) != MP_EQ) {
495 printf("d == %d\n", ix); 603 printf("gcd %lu failure!\n", gcd_n);
496 return 0; 604 draw(&a);
497 } 605 draw(&b);
498 } else if (!strcmp(cmd, "sub_d")) { ++sub_d_n; 606 draw(&c);
499 fgets(buf, 4095, stdin); mp_read_radix(&a, buf, 64); 607 draw(&d);
500 fgets(buf, 4095, stdin); sscanf(buf, "%d", &ix); 608 return 0;
501 fgets(buf, 4095, stdin); mp_read_radix(&b, buf, 64); 609 }
502 mp_sub_d(&a, ix, &c); 610 } else if (!strcmp(cmd, "lcm")) {
503 if (mp_cmp(&b, &c) != MP_EQ) { 611 ++lcm_n;
504 printf("sub_d %lu failure\n", sub_d_n); 612 fgets(buf, 4095, stdin);
505 draw(&a); 613 mp_read_radix(&a, buf, 64);
506 draw(&b); 614 fgets(buf, 4095, stdin);
507 draw(&c); 615 mp_read_radix(&b, buf, 64);
508 printf("d == %d\n", ix); 616 fgets(buf, 4095, stdin);
509 return 0; 617 mp_read_radix(&c, buf, 64);
510 } 618 mp_copy(&a, &d);
511 } 619 mp_lcm(&d, &b, &d);
620 d.sign = c.sign;
621 if (mp_cmp(&c, &d) != MP_EQ) {
622 printf("lcm %lu failure!\n", lcm_n);
623 draw(&a);
624 draw(&b);
625 draw(&c);
626 draw(&d);
627 return 0;
628 }
629 } else if (!strcmp(cmd, "expt")) {
630 ++expt_n;
631 fgets(buf, 4095, stdin);
632 mp_read_radix(&a, buf, 64);
633 fgets(buf, 4095, stdin);
634 mp_read_radix(&b, buf, 64);
635 fgets(buf, 4095, stdin);
636 mp_read_radix(&c, buf, 64);
637 fgets(buf, 4095, stdin);
638 mp_read_radix(&d, buf, 64);
639 mp_copy(&a, &e);
640 mp_exptmod(&e, &b, &c, &e);
641 if (mp_cmp(&d, &e) != MP_EQ) {
642 printf("expt %lu failure!\n", expt_n);
643 draw(&a);
644 draw(&b);
645 draw(&c);
646 draw(&d);
647 draw(&e);
648 return 0;
649 }
650 } else if (!strcmp(cmd, "invmod")) {
651 ++inv_n;
652 fgets(buf, 4095, stdin);
653 mp_read_radix(&a, buf, 64);
654 fgets(buf, 4095, stdin);
655 mp_read_radix(&b, buf, 64);
656 fgets(buf, 4095, stdin);
657 mp_read_radix(&c, buf, 64);
658 mp_invmod(&a, &b, &d);
659 mp_mulmod(&d, &a, &b, &e);
660 if (mp_cmp_d(&e, 1) != MP_EQ) {
661 printf("inv [wrong value from MPI?!] failure\n");
662 draw(&a);
663 draw(&b);
664 draw(&c);
665 draw(&d);
666 mp_gcd(&a, &b, &e);
667 draw(&e);
668 return 0;
669 }
670
671 } else if (!strcmp(cmd, "div2")) {
672 ++div2_n;
673 fgets(buf, 4095, stdin);
674 mp_read_radix(&a, buf, 64);
675 fgets(buf, 4095, stdin);
676 mp_read_radix(&b, buf, 64);
677 mp_div_2(&a, &c);
678 if (mp_cmp(&c, &b) != MP_EQ) {
679 printf("div_2 %lu failure\n", div2_n);
680 draw(&a);
681 draw(&b);
682 draw(&c);
683 return 0;
684 }
685 } else if (!strcmp(cmd, "mul2")) {
686 ++mul2_n;
687 fgets(buf, 4095, stdin);
688 mp_read_radix(&a, buf, 64);
689 fgets(buf, 4095, stdin);
690 mp_read_radix(&b, buf, 64);
691 mp_mul_2(&a, &c);
692 if (mp_cmp(&c, &b) != MP_EQ) {
693 printf("mul_2 %lu failure\n", mul2_n);
694 draw(&a);
695 draw(&b);
696 draw(&c);
697 return 0;
698 }
699 } else if (!strcmp(cmd, "add_d")) {
700 ++add_d_n;
701 fgets(buf, 4095, stdin);
702 mp_read_radix(&a, buf, 64);
703 fgets(buf, 4095, stdin);
704 sscanf(buf, "%d", &ix);
705 fgets(buf, 4095, stdin);
706 mp_read_radix(&b, buf, 64);
707 mp_add_d(&a, ix, &c);
708 if (mp_cmp(&b, &c) != MP_EQ) {
709 printf("add_d %lu failure\n", add_d_n);
710 draw(&a);
711 draw(&b);
712 draw(&c);
713 printf("d == %d\n", ix);
714 return 0;
715 }
716 } else if (!strcmp(cmd, "sub_d")) {
717 ++sub_d_n;
718 fgets(buf, 4095, stdin);
719 mp_read_radix(&a, buf, 64);
720 fgets(buf, 4095, stdin);
721 sscanf(buf, "%d", &ix);
722 fgets(buf, 4095, stdin);
723 mp_read_radix(&b, buf, 64);
724 mp_sub_d(&a, ix, &c);
725 if (mp_cmp(&b, &c) != MP_EQ) {
726 printf("sub_d %lu failure\n", sub_d_n);
727 draw(&a);
728 draw(&b);
729 draw(&c);
730 printf("d == %d\n", ix);
731 return 0;
732 }
733 }
512 } 734 }
513 return 0; 735 return 0;
514 } 736 }
515