12 void ndraw(mp_int * a, char *name)
17 mp_toradix(a, buf, 10);
21 static void draw(mp_int * a)
27 unsigned long lfsr = 0xAAAAAAAAUL;
31 if (lfsr & 0x80000000UL) {
32 lfsr = ((lfsr << 1) ^ 0x8000001BUL) & 0xFFFFFFFFUL;
40 int myrng(unsigned char *dst, int len, void *dat)
44 for (x = 0; x < len; x++)
45 dst[x] = rand() & 0xFF;
51 char cmd[4096], buf[4096];
54 mp_int a, b, c, d, e, f;
55 unsigned long expt_n, add_n, sub_n, mul_n, div_n, sqr_n, mul2d_n, div2d_n,
56 gcd_n, lcm_n, inv_n, div2_n, mul2_n, add_d_n, sub_d_n, t;
58 int i, n, err, cnt, ix, old_kara_m, old_kara_s;
73 printf("Testing montgomery...\n");
74 for (i = 1; i < 10; i++) {
75 printf("Testing digit size: %d\n", i);
76 for (n = 0; n < 1000; n++) {
80 // let's see if R is right
81 mp_montgomery_calc_normalization(&b, &a);
82 mp_montgomery_setup(&a, &mp);
84 // now test a random reduction
85 for (ix = 0; ix < 100; ix++) {
86 mp_rand(&c, 1 + abs(rand()) % (2*i));
91 mp_montgomery_reduce(&c, &a, mp);
92 mp_mulmod(&c, &b, &a, &c);
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); }
107 printf("Testing: mp_get_int\n");
108 for (i = 0; i < 1000; ++i) {
109 t = ((unsigned long) rand() * rand() + 1) & 0xFFFFFFFF;
111 if (t != mp_get_int(&a)) {
112 printf("mp_get_int() bad result!\n");
117 if (mp_get_int(&a) != 0) {
118 printf("mp_get_int() bad result!\n");
121 mp_set_int(&a, 0xffffffff);
122 if (mp_get_int(&a) != 0xffffffff) {
123 printf("mp_get_int() bad result!\n");
127 printf("Testing: mp_sqrt\n");
128 for (i = 0; i < 1000; ++i) {
131 n = (rand() & 15) + 1;
133 if (mp_sqrt(&a, &b) != MP_OKAY) {
134 printf("mp_sqrt() error!\n");
137 mp_n_root(&a, 2, &a);
138 if (mp_cmp_mag(&b, &a) != MP_EQ) {
139 printf("mp_sqrt() bad result!\n");
144 printf("\nTesting: mp_is_square\n");
145 for (i = 0; i < 1000; ++i) {
149 /* test mp_is_square false negatives */
150 n = (rand() & 7) + 1;
153 if (mp_is_square(&a, &n) != MP_OKAY) {
154 printf("fn:mp_is_square() error!\n");
158 printf("fn:mp_is_square() bad result!\n");
162 /* test for false positives */
164 if (mp_is_square(&a, &n) != MP_OKAY) {
165 printf("fp:mp_is_square() error!\n");
169 printf("fp:mp_is_square() bad result!\n");
177 for (ix = 10; ix < 128; ix++) {
178 printf("Testing (not safe-prime): %9d bits \r", ix);
181 mp_prime_random_ex(&a, 8, ix,
182 (rand() & 1) ? LTM_PRIME_2MSB_OFF :
183 LTM_PRIME_2MSB_ON, myrng, NULL);
184 if (err != MP_OKAY) {
185 printf("failed with err code %d\n", err);
188 if (mp_count_bits(&a) != ix) {
189 printf("Prime is %d not %d bits!!!\n", mp_count_bits(&a), ix);
194 for (ix = 16; ix < 128; ix++) {
195 printf("Testing ( safe-prime): %9d bits \r", ix);
198 mp_prime_random_ex(&a, 8, ix,
199 ((rand() & 1) ? LTM_PRIME_2MSB_OFF :
200 LTM_PRIME_2MSB_ON) | LTM_PRIME_SAFE, myrng,
202 if (err != MP_OKAY) {
203 printf("failed with err code %d\n", err);
206 if (mp_count_bits(&a) != ix) {
207 printf("Prime is %d not %d bits!!!\n", mp_count_bits(&a), ix);
210 /* let's see if it's really a safe prime */
213 mp_prime_is_prime(&a, 8, &cnt);
215 printf("sub is not prime!\n");
222 mp_read_radix(&a, "123456", 10);
223 mp_toradix_n(&a, buf, 10, 3);
224 printf("a == %s\n", buf);
225 mp_toradix_n(&a, buf, 10, 4);
226 printf("a == %s\n", buf);
227 mp_toradix_n(&a, buf, 10, 30);
228 printf("a == %s\n", buf);
233 fgets(buf, sizeof(buf), stdin);
234 mp_read_radix(&a, buf, 10);
235 mp_prime_next_prime(&a, 5, 1);
236 mp_toradix(&a, buf, 10);
237 printf("%s, %lu\n", buf, a.dp[0] & 3);
241 /* test mp_cnt_lsb */
242 printf("testing mp_cnt_lsb...\n");
244 for (ix = 0; ix < 1024; ix++) {
245 if (mp_cnt_lsb(&a) != ix) {
246 printf("Failed at %d, %d\n", ix, mp_cnt_lsb(&a));
252 /* test mp_reduce_2k */
253 printf("Testing mp_reduce_2k...\n");
254 for (cnt = 3; cnt <= 128; ++cnt) {
258 mp_sub_d(&a, 2, &a); /* a = 2**cnt - 2 */
261 printf("\nTesting %4d bits", cnt);
262 printf("(%d)", mp_reduce_is_2k(&a));
263 mp_reduce_2k_setup(&a, &tmp);
265 for (ix = 0; ix < 1000; ix++) {
270 mp_rand(&b, (cnt / DIGIT_BIT + 1) * 2);
273 mp_reduce_2k(&b, &a, 2);
274 if (mp_cmp(&c, &b)) {
282 printf("Testing mp_div_3...\n");
284 for (cnt = 0; cnt < 10000;) {
288 printf("%9d\r", cnt);
289 mp_rand(&a, abs(rand()) % 128 + 1);
290 mp_div(&a, &d, &b, &e);
291 mp_div_3(&a, &c, &r2);
293 if (mp_cmp(&b, &c) || mp_cmp_d(&e, r2)) {
294 printf("\n\nmp_div_3 => Failure\n");
297 printf("\n\nPassed div_3 testing\n");
299 /* test the DR reduction */
300 printf("testing mp_dr_reduce...\n");
301 for (cnt = 2; cnt < 32; cnt++) {
302 printf("%d digit modulus\n", cnt);
305 for (ix = 1; ix < cnt; ix++) {
311 mp_rand(&b, cnt - 1);
317 printf("%9lu\r", rr);
325 mp_dr_reduce(&c, &a, (((mp_digit) 1) << DIGIT_BIT) - a.dp[0]);
327 if (mp_cmp(&b, &c) != MP_EQ) {
328 printf("Failed on trial %lu\n", rr);
332 } while (++rr < 500);
333 printf("Passed DR test for %d digits\n", cnt);
338 /* test the mp_reduce_2k_l code */
341 /* first load P with 2^1024 - 0x2A434 B9FDEC95 D8F9D550 FFFFFFFF FFFFFFFF */
343 mp_read_radix(&b, "2A434B9FDEC95D8F9D550FFFFFFFFFFFFFFFF", 16);
346 /* p = 2^2048 - 0x1 00000000 00000000 00000000 00000000 4945DDBF 8EA2A91D 5776399B B83E188F */
349 "1000000000000000000000000000000004945DDBF8EA2A91D5776399BB83E188F",
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");
361 mp_reduce_2k_setup_l(&a, &d);
362 /* now do a million square+1 to see if it varies */
366 printf("testing mp_reduce_2k_l...");
368 for (cnt = 0; cnt < (1UL << 20); cnt++) {
371 mp_reduce_2k_l(&b, &a, &d);
375 if (mp_cmp(&b, &c) != MP_EQ) {
376 printf("mp_reduce_2k_l() failed at step %lu\n", cnt);
378 printf("b == %s\n", buf);
380 printf("c == %s\n", buf);
384 printf("...Passed\n");
387 div2_n = mul2_n = inv_n = expt_n = lcm_n = gcd_n = add_n =
388 sub_n = mul_n = div_n = sqr_n = mul2d_n = div2d_n = cnt = add_d_n =
391 /* force KARA and TOOM to enable despite cutoffs */
392 KARATSUBA_SQR_CUTOFF = KARATSUBA_MUL_CUTOFF = 8;
393 TOOM_SQR_CUTOFF = TOOM_MUL_CUTOFF = 16;
396 /* randomly clear and re-init one variable, this has the affect of triming the alloc space */
397 switch (abs(rand()) % 7) {
423 break; /* don't clear any */
428 ("%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu ",
429 add_n, sub_n, mul_n, div_n, sqr_n, mul2d_n, div2d_n, gcd_n, lcm_n,
430 expt_n, inv_n, div2_n, mul2_n, add_d_n, sub_d_n);
431 fgets(cmd, 4095, stdin);
432 cmd[strlen(cmd) - 1] = 0;
433 printf("%s ]\r", cmd);
435 if (!strcmp(cmd, "mul2d")) {
437 fgets(buf, 4095, stdin);
438 mp_read_radix(&a, buf, 64);
439 fgets(buf, 4095, stdin);
440 sscanf(buf, "%d", &rr);
441 fgets(buf, 4095, stdin);
442 mp_read_radix(&b, buf, 64);
444 mp_mul_2d(&a, rr, &a);
446 if (mp_cmp(&a, &b) != MP_EQ) {
447 printf("mul2d failed, rr == %d\n", rr);
452 } else if (!strcmp(cmd, "div2d")) {
454 fgets(buf, 4095, stdin);
455 mp_read_radix(&a, buf, 64);
456 fgets(buf, 4095, stdin);
457 sscanf(buf, "%d", &rr);
458 fgets(buf, 4095, stdin);
459 mp_read_radix(&b, buf, 64);
461 mp_div_2d(&a, rr, &a, &e);
463 if (a.used == b.used && a.used == 0) {
464 a.sign = b.sign = MP_ZPOS;
466 if (mp_cmp(&a, &b) != MP_EQ) {
467 printf("div2d failed, rr == %d\n", rr);
472 } else if (!strcmp(cmd, "add")) {
474 fgets(buf, 4095, stdin);
475 mp_read_radix(&a, buf, 64);
476 fgets(buf, 4095, stdin);
477 mp_read_radix(&b, buf, 64);
478 fgets(buf, 4095, stdin);
479 mp_read_radix(&c, buf, 64);
482 if (mp_cmp(&c, &d) != MP_EQ) {
483 printf("add %lu failure!\n", add_n);
491 /* test the sign/unsigned storage functions */
493 rr = mp_signed_bin_size(&c);
494 mp_to_signed_bin(&c, (unsigned char *) cmd);
495 memset(cmd + rr, rand() & 255, sizeof(cmd) - rr);
496 mp_read_signed_bin(&d, (unsigned char *) cmd, rr);
497 if (mp_cmp(&c, &d) != MP_EQ) {
498 printf("mp_signed_bin failure!\n");
505 rr = mp_unsigned_bin_size(&c);
506 mp_to_unsigned_bin(&c, (unsigned char *) cmd);
507 memset(cmd + rr, rand() & 255, sizeof(cmd) - rr);
508 mp_read_unsigned_bin(&d, (unsigned char *) cmd, rr);
509 if (mp_cmp_mag(&c, &d) != MP_EQ) {
510 printf("mp_unsigned_bin failure!\n");
516 } else if (!strcmp(cmd, "sub")) {
518 fgets(buf, 4095, stdin);
519 mp_read_radix(&a, buf, 64);
520 fgets(buf, 4095, stdin);
521 mp_read_radix(&b, buf, 64);
522 fgets(buf, 4095, stdin);
523 mp_read_radix(&c, buf, 64);
526 if (mp_cmp(&c, &d) != MP_EQ) {
527 printf("sub %lu failure!\n", sub_n);
534 } else if (!strcmp(cmd, "mul")) {
536 fgets(buf, 4095, stdin);
537 mp_read_radix(&a, buf, 64);
538 fgets(buf, 4095, stdin);
539 mp_read_radix(&b, buf, 64);
540 fgets(buf, 4095, stdin);
541 mp_read_radix(&c, buf, 64);
544 if (mp_cmp(&c, &d) != MP_EQ) {
545 printf("mul %lu failure!\n", mul_n);
552 } else if (!strcmp(cmd, "div")) {
554 fgets(buf, 4095, stdin);
555 mp_read_radix(&a, buf, 64);
556 fgets(buf, 4095, stdin);
557 mp_read_radix(&b, buf, 64);
558 fgets(buf, 4095, stdin);
559 mp_read_radix(&c, buf, 64);
560 fgets(buf, 4095, stdin);
561 mp_read_radix(&d, buf, 64);
563 mp_div(&a, &b, &e, &f);
564 if (mp_cmp(&c, &e) != MP_EQ || mp_cmp(&d, &f) != MP_EQ) {
565 printf("div %lu %d, %d, failure!\n", div_n, mp_cmp(&c, &e),
576 } else if (!strcmp(cmd, "sqr")) {
578 fgets(buf, 4095, stdin);
579 mp_read_radix(&a, buf, 64);
580 fgets(buf, 4095, stdin);
581 mp_read_radix(&b, buf, 64);
584 if (mp_cmp(&b, &c) != MP_EQ) {
585 printf("sqr %lu failure!\n", sqr_n);
591 } else if (!strcmp(cmd, "gcd")) {
593 fgets(buf, 4095, stdin);
594 mp_read_radix(&a, buf, 64);
595 fgets(buf, 4095, stdin);
596 mp_read_radix(&b, buf, 64);
597 fgets(buf, 4095, stdin);
598 mp_read_radix(&c, buf, 64);
602 if (mp_cmp(&c, &d) != MP_EQ) {
603 printf("gcd %lu failure!\n", gcd_n);
610 } else if (!strcmp(cmd, "lcm")) {
612 fgets(buf, 4095, stdin);
613 mp_read_radix(&a, buf, 64);
614 fgets(buf, 4095, stdin);
615 mp_read_radix(&b, buf, 64);
616 fgets(buf, 4095, stdin);
617 mp_read_radix(&c, buf, 64);
621 if (mp_cmp(&c, &d) != MP_EQ) {
622 printf("lcm %lu failure!\n", lcm_n);
629 } else if (!strcmp(cmd, "expt")) {
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);
640 mp_exptmod(&e, &b, &c, &e);
641 if (mp_cmp(&d, &e) != MP_EQ) {
642 printf("expt %lu failure!\n", expt_n);
650 } else if (!strcmp(cmd, "invmod")) {
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");
671 } else if (!strcmp(cmd, "div2")) {
673 fgets(buf, 4095, stdin);
674 mp_read_radix(&a, buf, 64);
675 fgets(buf, 4095, stdin);
676 mp_read_radix(&b, buf, 64);
678 if (mp_cmp(&c, &b) != MP_EQ) {
679 printf("div_2 %lu failure\n", div2_n);
685 } else if (!strcmp(cmd, "mul2")) {
687 fgets(buf, 4095, stdin);
688 mp_read_radix(&a, buf, 64);
689 fgets(buf, 4095, stdin);
690 mp_read_radix(&b, buf, 64);
692 if (mp_cmp(&c, &b) != MP_EQ) {
693 printf("mul_2 %lu failure\n", mul2_n);
699 } else if (!strcmp(cmd, "add_d")) {
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);
713 printf("d == %d\n", ix);
716 } else if (!strcmp(cmd, "sub_d")) {
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);
730 printf("d == %d\n", ix);
738 /* $Source: /cvs/libtom/libtommath/demo/demo.c,v $ */
739 /* $Revision: 1.3 $ */
740 /* $Date: 2005/06/24 11:32:07 $ */