1 #include <inttypes.h>
2 #include "shared.h"
3
rand_long(void)4 static long rand_long(void)
5 {
6 long x;
7 if (s_mp_rand_source(&x, sizeof(x)) != MP_OKAY) {
8 fprintf(stderr, "s_mp_rand_source failed\n");
9 exit(EXIT_FAILURE);
10 }
11 return x;
12 }
13
rand_int(void)14 static int rand_int(void)
15 {
16 int x;
17 if (s_mp_rand_source(&x, sizeof(x)) != MP_OKAY) {
18 fprintf(stderr, "s_mp_rand_source failed\n");
19 exit(EXIT_FAILURE);
20 }
21 return x;
22 }
23
rand_int32(void)24 static int32_t rand_int32(void)
25 {
26 int32_t x;
27 if (s_mp_rand_source(&x, sizeof(x)) != MP_OKAY) {
28 fprintf(stderr, "s_mp_rand_source failed\n");
29 exit(EXIT_FAILURE);
30 }
31 return x;
32 }
33
rand_int64(void)34 static int64_t rand_int64(void)
35 {
36 int64_t x;
37 if (s_mp_rand_source(&x, sizeof(x)) != MP_OKAY) {
38 fprintf(stderr, "s_mp_rand_source failed\n");
39 exit(EXIT_FAILURE);
40 }
41 return x;
42 }
43
uabs32(int32_t x)44 static uint32_t uabs32(int32_t x)
45 {
46 return x > 0 ? (uint32_t)x : -(uint32_t)x;
47 }
48
uabs64(int64_t x)49 static uint64_t uabs64(int64_t x)
50 {
51 return x > 0 ? (uint64_t)x : -(uint64_t)x;
52 }
53
54 /* This function prototype is needed
55 * to test dead code elimination
56 * which is used for feature detection.
57 *
58 * If the feature detection does not
59 * work as desired we will get a linker error.
60 */
61 void does_not_exist(void);
62
test_feature_detection(void)63 static int test_feature_detection(void)
64 {
65 #define BN_TEST_FEATURE1_C
66 if (!MP_HAS(TEST_FEATURE1)) {
67 does_not_exist();
68 return EXIT_FAILURE;
69 }
70
71 #define BN_TEST_FEATURE2_C 1
72 if (MP_HAS(TEST_FEATURE2)) {
73 does_not_exist();
74 return EXIT_FAILURE;
75 }
76
77 #define BN_TEST_FEATURE3_C 0
78 if (MP_HAS(TEST_FEATURE3)) {
79 does_not_exist();
80 return EXIT_FAILURE;
81 }
82
83 #define BN_TEST_FEATURE4_C something
84 if (MP_HAS(TEST_FEATURE4)) {
85 does_not_exist();
86 return EXIT_FAILURE;
87 }
88
89 if (MP_HAS(TEST_FEATURE5)) {
90 does_not_exist();
91 return EXIT_FAILURE;
92 }
93
94 return EXIT_SUCCESS;
95 }
96
test_trivial_stuff(void)97 static int test_trivial_stuff(void)
98 {
99 mp_int a, b, c, d;
100 mp_err e;
101 if ((e = mp_init_multi(&a, &b, &c, &d, NULL)) != MP_OKAY) {
102 return EXIT_FAILURE;
103 }
104 (void)mp_error_to_string(e);
105
106 /* a: 0->5 */
107 mp_set(&a, 5u);
108 /* a: 5-> b: -5 */
109 mp_neg(&a, &b);
110 if (mp_cmp(&a, &b) != MP_GT) {
111 goto LBL_ERR;
112 }
113 if (mp_cmp(&b, &a) != MP_LT) {
114 goto LBL_ERR;
115 }
116 /* a: 5-> a: -5 */
117 mp_neg(&a, &a);
118 if (mp_cmp(&b, &a) != MP_EQ) {
119 goto LBL_ERR;
120 }
121 /* a: -5-> b: 5 */
122 mp_abs(&a, &b);
123 if (mp_isneg(&b) != MP_NO) {
124 goto LBL_ERR;
125 }
126 /* a: -5-> b: -4 */
127 mp_add_d(&a, 1uL, &b);
128 if (mp_isneg(&b) != MP_YES) {
129 goto LBL_ERR;
130 }
131 if (mp_get_i32(&b) != -4) {
132 goto LBL_ERR;
133 }
134 if (mp_get_u32(&b) != (uint32_t)-4) {
135 goto LBL_ERR;
136 }
137 if (mp_get_mag_u32(&b) != 4) {
138 goto LBL_ERR;
139 }
140 /* a: -5-> b: 1 */
141 mp_add_d(&a, 6uL, &b);
142 if (mp_get_u32(&b) != 1) {
143 goto LBL_ERR;
144 }
145 /* a: -5-> a: 1 */
146 mp_add_d(&a, 6uL, &a);
147 if (mp_get_u32(&a) != 1) {
148 goto LBL_ERR;
149 }
150 mp_zero(&a);
151 /* a: 0-> a: 6 */
152 mp_add_d(&a, 6uL, &a);
153 if (mp_get_u32(&a) != 6) {
154 goto LBL_ERR;
155 }
156
157 mp_set(&a, 42u);
158 mp_set(&b, 1u);
159 mp_neg(&b, &b);
160 mp_set(&c, 1u);
161 mp_exptmod(&a, &b, &c, &d);
162
163 mp_set(&c, 7u);
164 mp_exptmod(&a, &b, &c, &d);
165
166 if (mp_iseven(&a) == mp_isodd(&a)) {
167 goto LBL_ERR;
168 }
169
170 mp_clear_multi(&a, &b, &c, &d, NULL);
171 return EXIT_SUCCESS;
172 LBL_ERR:
173 mp_clear_multi(&a, &b, &c, &d, NULL);
174 return EXIT_FAILURE;
175 }
176
check_get_set_i32(mp_int * a,int32_t b)177 static int check_get_set_i32(mp_int *a, int32_t b)
178 {
179 mp_clear(a);
180 if (mp_shrink(a) != MP_OKAY) return EXIT_FAILURE;
181
182 mp_set_i32(a, b);
183 if (mp_shrink(a) != MP_OKAY) return EXIT_FAILURE;
184 if (mp_get_i32(a) != b) return EXIT_FAILURE;
185 if (mp_get_u32(a) != (uint32_t)b) return EXIT_FAILURE;
186 if (mp_get_mag_u32(a) != uabs32(b)) return EXIT_FAILURE;
187
188 mp_set_u32(a, (uint32_t)b);
189 if (mp_get_u32(a) != (uint32_t)b) return EXIT_FAILURE;
190 if (mp_get_i32(a) != (int32_t)(uint32_t)b) return EXIT_FAILURE;
191
192 return EXIT_SUCCESS;
193 }
194
test_mp_get_set_i32(void)195 static int test_mp_get_set_i32(void)
196 {
197 int i;
198 mp_int a;
199
200 if (mp_init(&a) != MP_OKAY) {
201 return EXIT_FAILURE;
202 }
203
204 check_get_set_i32(&a, 0);
205 check_get_set_i32(&a, -1);
206 check_get_set_i32(&a, 1);
207 check_get_set_i32(&a, INT32_MIN);
208 check_get_set_i32(&a, INT32_MAX);
209
210 for (i = 0; i < 1000; ++i) {
211 int32_t b = rand_int32();
212 if (check_get_set_i32(&a, b) != EXIT_SUCCESS) {
213 goto LBL_ERR;
214 }
215 }
216
217 mp_clear(&a);
218 return EXIT_SUCCESS;
219 LBL_ERR:
220 mp_clear(&a);
221 return EXIT_FAILURE;
222 }
223
check_get_set_i64(mp_int * a,int64_t b)224 static int check_get_set_i64(mp_int *a, int64_t b)
225 {
226 mp_clear(a);
227 if (mp_shrink(a) != MP_OKAY) return EXIT_FAILURE;
228
229 mp_set_i64(a, b);
230 if (mp_shrink(a) != MP_OKAY) return EXIT_FAILURE;
231 if (mp_get_i64(a) != b) return EXIT_FAILURE;
232 if (mp_get_u64(a) != (uint64_t)b) return EXIT_FAILURE;
233 if (mp_get_mag_u64(a) != uabs64(b)) return EXIT_FAILURE;
234
235 mp_set_u64(a, (uint64_t)b);
236 if (mp_get_u64(a) != (uint64_t)b) return EXIT_FAILURE;
237 if (mp_get_i64(a) != (int64_t)(uint64_t)b) return EXIT_FAILURE;
238
239 return EXIT_SUCCESS;
240 }
241
test_mp_get_set_i64(void)242 static int test_mp_get_set_i64(void)
243 {
244 int i;
245 mp_int a;
246
247 if (mp_init(&a) != MP_OKAY) {
248 return EXIT_FAILURE;
249 }
250
251 check_get_set_i64(&a, 0);
252 check_get_set_i64(&a, -1);
253 check_get_set_i64(&a, 1);
254 check_get_set_i64(&a, INT64_MIN);
255 check_get_set_i64(&a, INT64_MAX);
256
257 for (i = 0; i < 1000; ++i) {
258 int64_t b = rand_int64();
259 if (check_get_set_i64(&a, b) != EXIT_SUCCESS) {
260 goto LBL_ERR;
261 }
262 }
263
264 mp_clear(&a);
265 return EXIT_SUCCESS;
266 LBL_ERR:
267 mp_clear(&a);
268 return EXIT_FAILURE;
269 }
270
test_mp_fread_fwrite(void)271 static int test_mp_fread_fwrite(void)
272 {
273 mp_int a, b;
274 mp_err e;
275 FILE *tmp = NULL;
276 if ((e = mp_init_multi(&a, &b, NULL)) != MP_OKAY) {
277 return EXIT_FAILURE;
278 }
279
280 mp_set_ul(&a, 123456uL);
281 tmp = tmpfile();
282 if ((e = mp_fwrite(&a, 64, tmp)) != MP_OKAY) {
283 goto LBL_ERR;
284 }
285 rewind(tmp);
286 if ((e = mp_fread(&b, 64, tmp)) != MP_OKAY) {
287 goto LBL_ERR;
288 }
289 if (mp_get_u32(&b) != 123456uL) {
290 goto LBL_ERR;
291 }
292 fclose(tmp);
293
294 mp_clear_multi(&a, &b, NULL);
295 return EXIT_SUCCESS;
296 LBL_ERR:
297 if (tmp != NULL) fclose(tmp);
298 mp_clear_multi(&a, &b, NULL);
299 return EXIT_FAILURE;
300 }
301
very_random_source(void * out,size_t size)302 static mp_err very_random_source(void *out, size_t size)
303 {
304 memset(out, 0xff, size);
305 return MP_OKAY;
306 }
307
test_mp_rand(void)308 static int test_mp_rand(void)
309 {
310 mp_int a, b;
311 int n;
312 mp_err err;
313 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
314 return EXIT_FAILURE;
315 }
316 mp_rand_source(very_random_source);
317 for (n = 1; n < 1024; ++n) {
318 if ((err = mp_rand(&a, n)) != MP_OKAY) {
319 printf("Failed mp_rand() %s.\n", mp_error_to_string(err));
320 break;
321 }
322 if ((err = mp_incr(&a)) != MP_OKAY) {
323 printf("Failed mp_incr() %s.\n", mp_error_to_string(err));
324 break;
325 }
326 if ((err = mp_div_2d(&a, n * MP_DIGIT_BIT, &b, NULL)) != MP_OKAY) {
327 printf("Failed mp_div_2d() %s.\n", mp_error_to_string(err));
328 break;
329 }
330 if (mp_cmp_d(&b, 1) != MP_EQ) {
331 ndraw(&a, "mp_rand() a");
332 ndraw(&b, "mp_rand() b");
333 err = MP_ERR;
334 break;
335 }
336 }
337 mp_rand_source(s_mp_rand_jenkins);
338 mp_clear_multi(&a, &b, NULL);
339 return err == MP_OKAY ? EXIT_SUCCESS : EXIT_FAILURE;
340 }
341
test_mp_kronecker(void)342 static int test_mp_kronecker(void)
343 {
344 struct mp_kronecker_st {
345 long n;
346 int c[21];
347 };
348 static struct mp_kronecker_st kronecker[] = {
349 /*-10, -9, -8, -7,-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10*/
350 { -10, { 0, -1, 0, -1, 0, 0, 0, 1, 0, -1, 0, 1, 0, -1, 0, 0, 0, 1, 0, 1, 0 } },
351 { -9, { -1, 0, -1, 1, 0, -1, -1, 0, -1, -1, 0, 1, 1, 0, 1, 1, 0, -1, 1, 0, 1 } },
352 { -8, { 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0 } },
353 { -7, { 1, -1, -1, 0, 1, 1, -1, 1, -1, -1, 0, 1, 1, -1, 1, -1, -1, 0, 1, 1, -1 } },
354 { -6, { 0, 0, 0, -1, 0, -1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0 } },
355 { -5, { 0, -1, 1, -1, 1, 0, -1, -1, 1, -1, 0, 1, -1, 1, 1, 0, -1, 1, -1, 1, 0 } },
356 { -4, { 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0 } },
357 { -3, { -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1 } },
358 { -2, { 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0 } },
359 { -1, { -1, -1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1 } },
360 { 0, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
361 { 1, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } },
362 { 2, { 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0 } },
363 { 3, { 1, 0, -1, -1, 0, -1, 1, 0, -1, 1, 0, 1, -1, 0, 1, -1, 0, -1, -1, 0, 1 } },
364 { 4, { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 } },
365 { 5, { 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0, 1, -1, -1, 1, 0 } },
366 { 6, { 0, 0, 0, -1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, -1, 0, 0, 0 } },
367 { 7, { -1, 1, 1, 0, 1, -1, 1, 1, 1, 1, 0, 1, 1, 1, 1, -1, 1, 0, 1, 1, -1 } },
368 { 8, { 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0 } },
369 { 9, { 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 } },
370 { 10, { 0, 1, 0, -1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, -1, 0, 1, 0 } }
371 };
372
373 long k, m;
374 int i, cnt;
375 mp_err err;
376 mp_int a, b;
377 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
378 return EXIT_FAILURE;
379 }
380
381 mp_set_ul(&a, 0uL);
382 mp_set_ul(&b, 1uL);
383 if ((err = mp_kronecker(&a, &b, &i)) != MP_OKAY) {
384 printf("Failed executing mp_kronecker(0 | 1) %s.\n", mp_error_to_string(err));
385 goto LBL_ERR;
386 }
387 if (i != 1) {
388 printf("Failed trivial mp_kronecker(0 | 1) %d != 1\n", i);
389 goto LBL_ERR;
390 }
391 for (cnt = 0; cnt < (int)(sizeof(kronecker)/sizeof(kronecker[0])); ++cnt) {
392 k = kronecker[cnt].n;
393 mp_set_l(&a, k);
394 /* only test positive values of a */
395 for (m = -10; m <= 10; m++) {
396 mp_set_l(&b, m);
397 if ((err = mp_kronecker(&a, &b, &i)) != MP_OKAY) {
398 printf("Failed executing mp_kronecker(%ld | %ld) %s.\n", kronecker[cnt].n, m, mp_error_to_string(err));
399 goto LBL_ERR;
400 }
401 if ((err == MP_OKAY) && (i != kronecker[cnt].c[m + 10])) {
402 printf("Failed trivial mp_kronecker(%ld | %ld) %d != %d\n", kronecker[cnt].n, m, i, kronecker[cnt].c[m + 10]);
403 goto LBL_ERR;
404 }
405 }
406 }
407
408 mp_clear_multi(&a, &b, NULL);
409 return EXIT_SUCCESS;
410 LBL_ERR:
411 mp_clear_multi(&a, &b, NULL);
412 return EXIT_FAILURE;
413 }
414
test_mp_complement(void)415 static int test_mp_complement(void)
416 {
417 int i;
418
419 mp_int a, b, c;
420 if (mp_init_multi(&a, &b, &c, NULL)!= MP_OKAY) {
421 return EXIT_FAILURE;
422 }
423
424 for (i = 0; i < 1000; ++i) {
425 long l = rand_long();
426 mp_set_l(&a, l);
427 mp_complement(&a, &b);
428
429 l = ~l;
430 mp_set_l(&c, l);
431
432 if (mp_cmp(&b, &c) != MP_EQ) {
433 printf("\nmp_complement() bad result!");
434 goto LBL_ERR;
435 }
436 }
437
438 mp_clear_multi(&a, &b, &c, NULL);
439 return EXIT_SUCCESS;
440 LBL_ERR:
441 mp_clear_multi(&a, &b, &c, NULL);
442 return EXIT_FAILURE;
443 }
444
test_mp_signed_rsh(void)445 static int test_mp_signed_rsh(void)
446 {
447 int i;
448
449 mp_int a, b, d;
450 if (mp_init_multi(&a, &b, &d, NULL)!= MP_OKAY) {
451 return EXIT_FAILURE;
452 }
453
454 for (i = 0; i < 1000; ++i) {
455 long l;
456 int em;
457
458 l = rand_long();
459 mp_set_l(&a, l);
460
461 em = abs(rand_int()) % 32;
462
463 mp_set_l(&d, l >> em);
464
465 mp_signed_rsh(&a, em, &b);
466 if (mp_cmp(&b, &d) != MP_EQ) {
467 printf("\nmp_signed_rsh() bad result!");
468 goto LBL_ERR;
469 }
470 }
471
472 mp_clear_multi(&a, &b, &d, NULL);
473 return EXIT_SUCCESS;
474 LBL_ERR:
475 mp_clear_multi(&a, &b, &d, NULL);
476 return EXIT_FAILURE;
477
478 }
479
test_mp_xor(void)480 static int test_mp_xor(void)
481 {
482 int i;
483
484 mp_int a, b, c, d;
485 if (mp_init_multi(&a, &b, &c, &d, NULL)!= MP_OKAY) {
486 return EXIT_FAILURE;
487 }
488
489 for (i = 0; i < 1000; ++i) {
490 long l, em;
491
492 l = rand_long();
493 mp_set_l(&a,l);
494
495 em = rand_long();
496 mp_set_l(&b, em);
497
498 mp_set_l(&d, l ^ em);
499
500 mp_xor(&a, &b, &c);
501 if (mp_cmp(&c, &d) != MP_EQ) {
502 printf("\nmp_xor() bad result!");
503 goto LBL_ERR;
504 }
505 }
506
507 mp_clear_multi(&a, &b, &c, &d, NULL);
508 return EXIT_SUCCESS;
509 LBL_ERR:
510 mp_clear_multi(&a, &b, &c, &d, NULL);
511 return EXIT_FAILURE;
512
513 }
514
test_mp_or(void)515 static int test_mp_or(void)
516 {
517 int i;
518
519 mp_int a, b, c, d;
520 if (mp_init_multi(&a, &b, &c, &d, NULL)!= MP_OKAY) {
521 return EXIT_FAILURE;
522 }
523
524 for (i = 0; i < 1000; ++i) {
525 long l, em;
526
527 l = rand_long();
528 mp_set_l(&a, l);
529
530 em = rand_long();
531 mp_set_l(&b, em);
532
533 mp_set_l(&d, l | em);
534
535 mp_or(&a, &b, &c);
536 if (mp_cmp(&c, &d) != MP_EQ) {
537 printf("\nmp_or() bad result!");
538 goto LBL_ERR;
539 }
540 }
541
542 mp_clear_multi(&a, &b, &c, &d, NULL);
543 return EXIT_SUCCESS;
544 LBL_ERR:
545 mp_clear_multi(&a, &b, &c, &d, NULL);
546 return EXIT_FAILURE;
547 }
548
test_mp_and(void)549 static int test_mp_and(void)
550 {
551 int i;
552
553 mp_int a, b, c, d;
554 if (mp_init_multi(&a, &b, &c, &d, NULL)!= MP_OKAY) {
555 return EXIT_FAILURE;
556 }
557
558 for (i = 0; i < 1000; ++i) {
559 long l, em;
560
561 l = rand_long();
562 mp_set_l(&a, l);
563
564 em = rand_long();
565 mp_set_l(&b, em);
566
567 mp_set_l(&d, l & em);
568
569 mp_and(&a, &b, &c);
570 if (mp_cmp(&c, &d) != MP_EQ) {
571 printf("\nmp_and() bad result!");
572 goto LBL_ERR;
573 }
574 }
575
576 mp_clear_multi(&a, &b, &c, &d, NULL);
577 return EXIT_SUCCESS;
578 LBL_ERR:
579 mp_clear_multi(&a, &b, &c, &d, NULL);
580 return EXIT_FAILURE;
581 }
582
test_mp_invmod(void)583 static int test_mp_invmod(void)
584 {
585 mp_int a, b, c, d;
586 if (mp_init_multi(&a, &b, &c, &d, NULL)!= MP_OKAY) {
587 return EXIT_FAILURE;
588 }
589
590 /* mp_invmod corner-case of https://github.com/libtom/libtommath/issues/118 */
591 {
592 const char *a_ = "47182BB8DF0FFE9F61B1F269BACC066B48BA145D35137D426328DC3F88A5EA44";
593 const char *b_ = "FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF";
594 const char *should_ = "0521A82E10376F8E4FDEF9A32A427AC2A0FFF686E00290D39E3E4B5522409596";
595
596 if (mp_read_radix(&a, a_, 16) != MP_OKAY) {
597 printf("\nmp_read_radix(a) failed!");
598 goto LBL_ERR;
599 }
600 if (mp_read_radix(&b, b_, 16) != MP_OKAY) {
601 printf("\nmp_read_radix(b) failed!");
602 goto LBL_ERR;
603 }
604 if (mp_read_radix(&c, should_, 16) != MP_OKAY) {
605 printf("\nmp_read_radix(should) failed!");
606 goto LBL_ERR;
607 }
608
609 if (mp_invmod(&a, &b, &d) != MP_OKAY) {
610 printf("\nmp_invmod() failed!");
611 goto LBL_ERR;
612 }
613
614 if (mp_cmp(&c, &d) != MP_EQ) {
615 printf("\nmp_invmod() bad result!");
616 goto LBL_ERR;
617 }
618 }
619
620 mp_clear_multi(&a, &b, &c, &d, NULL);
621 return EXIT_SUCCESS;
622 LBL_ERR:
623 mp_clear_multi(&a, &b, &c, &d, NULL);
624 return EXIT_FAILURE;
625
626 }
627
628 #if defined(MP_HAS_SET_DOUBLE)
test_mp_set_double(void)629 static int test_mp_set_double(void)
630 {
631 int i;
632
633 mp_int a, b;
634 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
635 return EXIT_FAILURE;
636 }
637
638 /* test mp_get_double/mp_set_double */
639 if (mp_set_double(&a, +1.0/0.0) != MP_VAL) {
640 printf("\nmp_set_double should return MP_VAL for +inf");
641 goto LBL_ERR;
642 }
643 if (mp_set_double(&a, -1.0/0.0) != MP_VAL) {
644 printf("\nmp_set_double should return MP_VAL for -inf");
645 goto LBL_ERR;
646 }
647 if (mp_set_double(&a, +0.0/0.0) != MP_VAL) {
648 printf("\nmp_set_double should return MP_VAL for NaN");
649 goto LBL_ERR;
650 }
651 if (mp_set_double(&a, -0.0/0.0) != MP_VAL) {
652 printf("\nmp_set_double should return MP_VAL for NaN");
653 goto LBL_ERR;
654 }
655
656 for (i = 0; i < 1000; ++i) {
657 int tmp = rand_int();
658 double dbl = (double)tmp * rand_int() + 1;
659 if (mp_set_double(&a, dbl) != MP_OKAY) {
660 printf("\nmp_set_double() failed");
661 goto LBL_ERR;
662 }
663 if (dbl != mp_get_double(&a)) {
664 printf("\nmp_get_double() bad result!");
665 goto LBL_ERR;
666 }
667 if (mp_set_double(&a, -dbl) != MP_OKAY) {
668 printf("\nmp_set_double() failed");
669 goto LBL_ERR;
670 }
671 if (-dbl != mp_get_double(&a)) {
672 printf("\nmp_get_double() bad result!");
673 goto LBL_ERR;
674 }
675 }
676
677 mp_clear_multi(&a, &b, NULL);
678 return EXIT_SUCCESS;
679 LBL_ERR:
680 mp_clear_multi(&a, &b, NULL);
681 return EXIT_FAILURE;
682
683 }
684 #endif
685
test_mp_get_u32(void)686 static int test_mp_get_u32(void)
687 {
688 unsigned long t;
689 int i;
690
691 mp_int a, b;
692 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
693 return EXIT_FAILURE;
694 }
695
696 for (i = 0; i < 1000; ++i) {
697 t = (unsigned long)rand_long() & 0xFFFFFFFFuL;
698 mp_set_ul(&a, t);
699 if (t != mp_get_u32(&a)) {
700 printf("\nmp_get_u32() bad result!");
701 goto LBL_ERR;
702 }
703 }
704 mp_set_ul(&a, 0uL);
705 if (mp_get_u32(&a) != 0) {
706 printf("\nmp_get_u32() bad result!");
707 goto LBL_ERR;
708 }
709 mp_set_ul(&a, 0xFFFFFFFFuL);
710 if (mp_get_u32(&a) != 0xFFFFFFFFuL) {
711 printf("\nmp_get_u32() bad result!");
712 goto LBL_ERR;
713 }
714
715 mp_clear_multi(&a, &b, NULL);
716 return EXIT_SUCCESS;
717 LBL_ERR:
718 mp_clear_multi(&a, &b, NULL);
719 return EXIT_FAILURE;
720 }
721
test_mp_get_ul(void)722 static int test_mp_get_ul(void)
723 {
724 unsigned long s, t;
725 int i;
726
727 mp_int a, b;
728 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
729 return EXIT_FAILURE;
730 }
731
732 for (i = 0; i < ((int)MP_SIZEOF_BITS(unsigned long) - 1); ++i) {
733 t = (1UL << (i+1)) - 1;
734 if (!t)
735 t = ~0UL;
736 printf(" t = 0x%lx i = %d\r", t, i);
737 do {
738 mp_set_ul(&a, t);
739 s = mp_get_ul(&a);
740 if (s != t) {
741 printf("\nmp_get_ul() bad result! 0x%lx != 0x%lx", s, t);
742 goto LBL_ERR;
743 }
744 t <<= 1;
745 } while (t != 0uL);
746 }
747
748 mp_clear_multi(&a, &b, NULL);
749 return EXIT_SUCCESS;
750 LBL_ERR:
751 mp_clear_multi(&a, &b, NULL);
752 return EXIT_FAILURE;
753 }
754
test_mp_get_u64(void)755 static int test_mp_get_u64(void)
756 {
757 unsigned long long q, r;
758 int i;
759
760 mp_int a, b;
761 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
762 return EXIT_FAILURE;
763 }
764
765 for (i = 0; i < (int)(MP_SIZEOF_BITS(unsigned long long) - 1); ++i) {
766 r = (1ULL << (i+1)) - 1;
767 if (!r)
768 r = ~0ULL;
769 printf(" r = 0x%llx i = %d\r", r, i);
770 do {
771 mp_set_u64(&a, r);
772 q = mp_get_u64(&a);
773 if (q != r) {
774 printf("\nmp_get_u64() bad result! 0x%llx != 0x%llx", q, r);
775 goto LBL_ERR;
776 }
777 r <<= 1;
778 } while (r != 0uLL);
779 }
780
781 mp_clear_multi(&a, &b, NULL);
782 return EXIT_SUCCESS;
783 LBL_ERR:
784 mp_clear_multi(&a, &b, NULL);
785 return EXIT_FAILURE;
786
787 }
788
test_mp_sqrt(void)789 static int test_mp_sqrt(void)
790 {
791 int i, n;
792
793 mp_int a, b, c;
794 if (mp_init_multi(&a, &b, &c, NULL)!= MP_OKAY) {
795 return EXIT_FAILURE;
796 }
797
798 for (i = 0; i < 1000; ++i) {
799 printf("%6d\r", i);
800 fflush(stdout);
801 n = (rand_int() & 15) + 1;
802 mp_rand(&a, n);
803 if (mp_sqrt(&a, &b) != MP_OKAY) {
804 printf("\nmp_sqrt() error!");
805 goto LBL_ERR;
806 }
807 mp_root_u32(&a, 2uL, &c);
808 if (mp_cmp_mag(&b, &c) != MP_EQ) {
809 printf("mp_sqrt() bad result!\n");
810 goto LBL_ERR;
811 }
812 }
813
814 mp_clear_multi(&a, &b, &c, NULL);
815 return EXIT_SUCCESS;
816 LBL_ERR:
817 mp_clear_multi(&a, &b, &c, NULL);
818 return EXIT_FAILURE;
819 }
820
test_mp_is_square(void)821 static int test_mp_is_square(void)
822 {
823 int i, n;
824
825 mp_int a, b;
826 mp_bool res;
827
828 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
829 return EXIT_FAILURE;
830 }
831
832 for (i = 0; i < 1000; ++i) {
833 printf("%6d\r", i);
834 fflush(stdout);
835
836 /* test mp_is_square false negatives */
837 n = (rand_int() & 7) + 1;
838 mp_rand(&a, n);
839 mp_sqr(&a, &a);
840 if (mp_is_square(&a, &res) != MP_OKAY) {
841 printf("\nfn:mp_is_square() error!");
842 goto LBL_ERR;
843 }
844 if (res == MP_NO) {
845 printf("\nfn:mp_is_square() bad result!");
846 goto LBL_ERR;
847 }
848
849 /* test for false positives */
850 mp_add_d(&a, 1uL, &a);
851 if (mp_is_square(&a, &res) != MP_OKAY) {
852 printf("\nfp:mp_is_square() error!");
853 goto LBL_ERR;
854 }
855 if (res == MP_YES) {
856 printf("\nfp:mp_is_square() bad result!");
857 goto LBL_ERR;
858 }
859
860 }
861 printf("\n\n");
862
863 mp_clear_multi(&a, &b, NULL);
864 return EXIT_SUCCESS;
865 LBL_ERR:
866 mp_clear_multi(&a, &b, NULL);
867 return EXIT_FAILURE;
868 }
869
test_mp_sqrtmod_prime(void)870 static int test_mp_sqrtmod_prime(void)
871 {
872 struct mp_sqrtmod_prime_st {
873 unsigned long p;
874 unsigned long n;
875 mp_digit r;
876 };
877
878 static struct mp_sqrtmod_prime_st sqrtmod_prime[] = {
879 { 5, 14, 3 },
880 { 7, 9, 4 },
881 { 113, 2, 62 }
882 };
883 int i;
884
885 mp_int a, b, c;
886 if (mp_init_multi(&a, &b, &c, NULL)!= MP_OKAY) {
887 return EXIT_FAILURE;
888 }
889
890 /* r^2 = n (mod p) */
891 for (i = 0; i < (int)(sizeof(sqrtmod_prime)/sizeof(sqrtmod_prime[0])); ++i) {
892 mp_set_ul(&a, sqrtmod_prime[i].p);
893 mp_set_ul(&b, sqrtmod_prime[i].n);
894 if (mp_sqrtmod_prime(&b, &a, &c) != MP_OKAY) {
895 printf("Failed executing %d. mp_sqrtmod_prime\n", (i+1));
896 goto LBL_ERR;
897 }
898 if (mp_cmp_d(&c, sqrtmod_prime[i].r) != MP_EQ) {
899 printf("Failed %d. trivial mp_sqrtmod_prime\n", (i+1));
900 ndraw(&c, "r");
901 goto LBL_ERR;
902 }
903 }
904
905 mp_clear_multi(&a, &b, &c, NULL);
906 return EXIT_SUCCESS;
907 LBL_ERR:
908 mp_clear_multi(&a, &b, &c, NULL);
909 return EXIT_FAILURE;
910 }
911
test_mp_prime_rand(void)912 static int test_mp_prime_rand(void)
913 {
914 int ix;
915 mp_err err;
916 mp_int a, b;
917 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
918 return EXIT_FAILURE;
919 }
920
921 /* test for size */
922 for (ix = 10; ix < 128; ix++) {
923 printf("Testing (not safe-prime): %9d bits \r", ix);
924 fflush(stdout);
925 err = mp_prime_rand(&a, 8, ix, (rand_int() & 1) ? 0 : MP_PRIME_2MSB_ON);
926 if (err != MP_OKAY) {
927 printf("\nfailed with error: %s\n", mp_error_to_string(err));
928 goto LBL_ERR;
929 }
930 if (mp_count_bits(&a) != ix) {
931 printf("Prime is %d not %d bits!!!\n", mp_count_bits(&a), ix);
932 goto LBL_ERR;
933 }
934 }
935 printf("\n");
936
937 mp_clear_multi(&a, &b, NULL);
938 return EXIT_SUCCESS;
939 LBL_ERR:
940 mp_clear_multi(&a, &b, NULL);
941 return EXIT_FAILURE;
942 }
943
test_mp_prime_is_prime(void)944 static int test_mp_prime_is_prime(void)
945 {
946 int ix;
947 mp_err err;
948 mp_bool cnt, fu;
949
950 mp_int a, b;
951 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
952 return EXIT_FAILURE;
953 }
954
955 /* strong Miller-Rabin pseudoprime to the first 200 primes (F. Arnault) */
956 puts("Testing mp_prime_is_prime() with Arnault's pseudoprime 803...901 \n");
957 mp_read_radix(&a,
958 "91xLNF3roobhzgTzoFIG6P13ZqhOVYSN60Fa7Cj2jVR1g0k89zdahO9/kAiRprpfO1VAp1aBHucLFV/qLKLFb+zonV7R2Vxp1K13ClwUXStpV0oxTNQVjwybmFb5NBEHImZ6V7P6+udRJuH8VbMEnS0H8/pSqQrg82OoQQ2fPpAk6G1hkjqoCv5s/Yr",
959 64);
960 mp_prime_is_prime(&a, mp_prime_rabin_miller_trials(mp_count_bits(&a)), &cnt);
961 if (cnt == MP_YES) {
962 printf("Arnault's pseudoprime is not prime but mp_prime_is_prime says it is.\n");
963 goto LBL_ERR;
964 }
965 /* About the same size as Arnault's pseudoprime */
966 puts("Testing mp_prime_is_prime() with certified prime 2^1119 + 53\n");
967 mp_set(&a, 1uL);
968 mp_mul_2d(&a,1119,&a);
969 mp_add_d(&a, 53uL, &a);
970 err = mp_prime_is_prime(&a, mp_prime_rabin_miller_trials(mp_count_bits(&a)), &cnt);
971 /* small problem */
972 if (err != MP_OKAY) {
973 printf("\nfailed with error: %s\n", mp_error_to_string(err));
974 }
975 /* large problem */
976 if (cnt == MP_NO) {
977 printf("A certified prime is a prime but mp_prime_is_prime says it is not.\n");
978 }
979 if ((err != MP_OKAY) || (cnt == MP_NO)) {
980 printf("prime tested was: 0x");
981 mp_fwrite(&a,16,stdout);
982 putchar('\n');
983 goto LBL_ERR;
984 }
985 for (ix = 16; ix < 128; ix++) {
986 printf("Testing ( safe-prime): %9d bits \r", ix);
987 fflush(stdout);
988 err = mp_prime_rand(&a, 8, ix, ((rand_int() & 1) ? 0 : MP_PRIME_2MSB_ON) | MP_PRIME_SAFE);
989 if (err != MP_OKAY) {
990 printf("\nfailed with error: %s\n", mp_error_to_string(err));
991 goto LBL_ERR;
992 }
993 if (mp_count_bits(&a) != ix) {
994 printf("Prime is %d not %d bits!!!\n", mp_count_bits(&a), ix);
995 goto LBL_ERR;
996 }
997 /* let's see if it's really a safe prime */
998 mp_sub_d(&a, 1uL, &b);
999 mp_div_2(&b, &b);
1000 err = mp_prime_is_prime(&b, mp_prime_rabin_miller_trials(mp_count_bits(&b)), &cnt);
1001 /* small problem */
1002 if (err != MP_OKAY) {
1003 printf("\nfailed with error: %s\n", mp_error_to_string(err));
1004 }
1005 /* large problem */
1006 if (cnt == MP_NO) {
1007 printf("\nsub is not prime!\n");
1008 }
1009 mp_prime_frobenius_underwood(&b, &fu);
1010 if (fu == MP_NO) {
1011 printf("\nfrobenius-underwood says sub is not prime!\n");
1012 }
1013 if ((err != MP_OKAY) || (cnt == MP_NO)) {
1014 printf("prime tested was: 0x");
1015 mp_fwrite(&a,16,stdout);
1016 putchar('\n');
1017 printf("sub tested was: 0x");
1018 mp_fwrite(&b,16,stdout);
1019 putchar('\n');
1020 goto LBL_ERR;
1021 }
1022
1023 }
1024 /* Check regarding problem #143 */
1025 #ifndef MP_8BIT
1026 mp_read_radix(&a,
1027 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF",
1028 16);
1029 err = mp_prime_strong_lucas_selfridge(&a, &cnt);
1030 /* small problem */
1031 if (err != MP_OKAY) {
1032 printf("\nmp_prime_strong_lucas_selfridge failed with error: %s\n", mp_error_to_string(err));
1033 }
1034 /* large problem */
1035 if (cnt == MP_NO) {
1036 printf("\n\nissue #143 - mp_prime_strong_lucas_selfridge FAILED!\n");
1037 }
1038 if ((err != MP_OKAY) || (cnt == MP_NO)) {
1039 printf("prime tested was: 0x");
1040 mp_fwrite(&a,16,stdout);
1041 putchar('\n');
1042 goto LBL_ERR;
1043 }
1044 #endif
1045
1046 printf("\n\n");
1047
1048 mp_clear_multi(&a, &b, NULL);
1049 return EXIT_SUCCESS;
1050 LBL_ERR:
1051 mp_clear_multi(&a, &b, NULL);
1052 return EXIT_FAILURE;
1053
1054 }
1055
1056
test_mp_prime_next_prime(void)1057 static int test_mp_prime_next_prime(void)
1058 {
1059 mp_err err;
1060 mp_int a, b, c;
1061
1062 mp_init_multi(&a, &b, &c, NULL);
1063
1064
1065 /* edge cases */
1066 mp_set(&a, 0u);
1067 if ((err = mp_prime_next_prime(&a, 5, 0)) != MP_OKAY) {
1068 goto LBL_ERR;
1069 }
1070 if (mp_cmp_d(&a, 2u) != MP_EQ) {
1071 printf("mp_prime_next_prime: output should have been 2 but was: ");
1072 mp_fwrite(&a,10,stdout);
1073 putchar('\n');
1074 goto LBL_ERR;
1075 }
1076
1077 mp_set(&a, 0u);
1078 if ((err = mp_prime_next_prime(&a, 5, 1)) != MP_OKAY) {
1079 goto LBL_ERR;
1080 }
1081 if (mp_cmp_d(&a, 3u) != MP_EQ) {
1082 printf("mp_prime_next_prime: output should have been 3 but was: ");
1083 mp_fwrite(&a,10,stdout);
1084 putchar('\n');
1085 goto LBL_ERR;
1086 }
1087
1088 mp_set(&a, 2u);
1089 if ((err = mp_prime_next_prime(&a, 5, 0)) != MP_OKAY) {
1090 goto LBL_ERR;
1091 }
1092 if (mp_cmp_d(&a, 3u) != MP_EQ) {
1093 printf("mp_prime_next_prime: output should have been 3 but was: ");
1094 mp_fwrite(&a,10,stdout);
1095 putchar('\n');
1096 goto LBL_ERR;
1097 }
1098
1099 mp_set(&a, 2u);
1100 if ((err = mp_prime_next_prime(&a, 5, 1)) != MP_OKAY) {
1101 goto LBL_ERR;
1102 }
1103 if (mp_cmp_d(&a, 3u) != MP_EQ) {
1104 printf("mp_prime_next_prime: output should have been 3 but was: ");
1105 mp_fwrite(&a,10,stdout);
1106 putchar('\n');
1107 goto LBL_ERR;
1108 }
1109 mp_set(&a, 8);
1110 if ((err = mp_prime_next_prime(&a, 5, 1)) != MP_OKAY) {
1111 goto LBL_ERR;
1112 }
1113 if (mp_cmp_d(&a, 11u) != MP_EQ) {
1114 printf("mp_prime_next_prime: output should have been 11 but was: ");
1115 mp_fwrite(&a,10,stdout);
1116 putchar('\n');
1117 goto LBL_ERR;
1118 }
1119 /* 2^300 + 157 is a 300 bit large prime to guarantee a multi-limb bigint */
1120 if ((err = mp_2expt(&a, 300)) != MP_OKAY) {
1121 goto LBL_ERR;
1122 }
1123 mp_set_u32(&b, 157);
1124 if ((err = mp_add(&a, &b, &a)) != MP_OKAY) {
1125 goto LBL_ERR;
1126 }
1127 if ((err = mp_copy(&a, &b)) != MP_OKAY) {
1128 goto LBL_ERR;
1129 }
1130
1131 /* 2^300 + 385 is the next prime */
1132 mp_set_u32(&c, 228);
1133 if ((err = mp_add(&b, &c, &b)) != MP_OKAY) {
1134 goto LBL_ERR;
1135 }
1136 if ((err = mp_prime_next_prime(&a, 5, 0)) != MP_OKAY) {
1137 goto LBL_ERR;
1138 }
1139 if (mp_cmp(&a, &b) != MP_EQ) {
1140 printf("mp_prime_next_prime: output should have been\n");
1141 mp_fwrite(&b,10,stdout);
1142 putchar('\n');
1143 printf("but was:\n");
1144 mp_fwrite(&a,10,stdout);
1145 putchar('\n');
1146 goto LBL_ERR;
1147 }
1148
1149 /* Use another temporary variable or recompute? Mmh... */
1150 if ((err = mp_2expt(&a, 300)) != MP_OKAY) {
1151 goto LBL_ERR;
1152 }
1153 mp_set_u32(&b, 157);
1154 if ((err = mp_add(&a, &b, &a)) != MP_OKAY) {
1155 goto LBL_ERR;
1156 }
1157 if ((err = mp_copy(&a, &b)) != MP_OKAY) {
1158 goto LBL_ERR;
1159 }
1160
1161 /* 2^300 + 631 is the next prime congruent to 3 mod 4*/
1162 mp_set_u32(&c, 474);
1163 if ((err = mp_add(&b, &c, &b)) != MP_OKAY) {
1164 goto LBL_ERR;
1165 }
1166 if ((err = mp_prime_next_prime(&a, 5, 1)) != MP_OKAY) {
1167 goto LBL_ERR;
1168 }
1169 if (mp_cmp(&a, &b) != MP_EQ) {
1170 printf("mp_prime_next_prime (bbs): output should have been\n");
1171 mp_fwrite(&b,10,stdout);
1172 putchar('\n');
1173 printf("but was:\n");
1174 mp_fwrite(&a,10,stdout);
1175 putchar('\n');
1176 goto LBL_ERR;
1177 }
1178
1179 mp_clear_multi(&a, &b, &c, NULL);
1180 return EXIT_SUCCESS;
1181 LBL_ERR:
1182 mp_clear_multi(&a, &b, &c, NULL);
1183 return EXIT_FAILURE;
1184 }
1185
test_mp_montgomery_reduce(void)1186 static int test_mp_montgomery_reduce(void)
1187 {
1188 mp_digit mp;
1189 int ix, i, n;
1190 char buf[4096];
1191
1192 /* size_t written; */
1193
1194 mp_int a, b, c, d, e;
1195 if (mp_init_multi(&a, &b, &c, &d, &e, NULL)!= MP_OKAY) {
1196 return EXIT_FAILURE;
1197 }
1198
1199 /* test montgomery */
1200 for (i = 1; i <= 10; i++) {
1201 if (i == 10)
1202 i = 1000;
1203 printf(" digit size: %2d\r", i);
1204 fflush(stdout);
1205 for (n = 0; n < 1000; n++) {
1206 mp_rand(&a, i);
1207 a.dp[0] |= 1;
1208
1209 /* let's see if R is right */
1210 mp_montgomery_calc_normalization(&b, &a);
1211 mp_montgomery_setup(&a, &mp);
1212
1213 /* now test a random reduction */
1214 for (ix = 0; ix < 100; ix++) {
1215 mp_rand(&c, 1 + abs(rand_int()) % (2*i));
1216 mp_copy(&c, &d);
1217 mp_copy(&c, &e);
1218
1219 mp_mod(&d, &a, &d);
1220 mp_montgomery_reduce(&c, &a, mp);
1221 mp_mulmod(&c, &b, &a, &c);
1222
1223 if (mp_cmp(&c, &d) != MP_EQ) {
1224 /* *INDENT-OFF* */
1225 printf("d = e mod a, c = e MOD a\n");
1226 mp_to_decimal(&a, buf, sizeof(buf)); printf("a = %s\n", buf);
1227 mp_to_decimal(&e, buf, sizeof(buf)); printf("e = %s\n", buf);
1228 mp_to_decimal(&d, buf, sizeof(buf)); printf("d = %s\n", buf);
1229 mp_to_decimal(&c, buf, sizeof(buf)); printf("c = %s\n", buf);
1230
1231 printf("compare no compare!\n"); goto LBL_ERR;
1232 /* *INDENT-ON* */
1233 }
1234 /* only one big montgomery reduction */
1235 if (i > 10) {
1236 n = 1000;
1237 ix = 100;
1238 }
1239 }
1240 }
1241 }
1242
1243 printf("\n\n");
1244
1245 mp_clear_multi(&a, &b, &c, &d, &e, NULL);
1246 return EXIT_SUCCESS;
1247 LBL_ERR:
1248 mp_clear_multi(&a, &b, &c, &d, &e, NULL);
1249 return EXIT_FAILURE;
1250
1251 }
1252
test_mp_read_radix(void)1253 static int test_mp_read_radix(void)
1254 {
1255 char buf[4096];
1256 size_t written;
1257 mp_err err;
1258
1259 mp_int a;
1260 if (mp_init_multi(&a, NULL)!= MP_OKAY) goto LTM_ERR;
1261
1262 if ((err = mp_read_radix(&a, "123456", 10)) != MP_OKAY) goto LTM_ERR;
1263
1264 if ((err = mp_to_radix(&a, buf, SIZE_MAX, &written, 10)) != MP_OKAY) goto LTM_ERR;
1265 printf(" '123456' a == %s, length = %zu\n", buf, written);
1266
1267 /* See comment in bn_mp_to_radix.c */
1268 /*
1269 if( (err = mp_to_radix(&a, buf, 3u, &written, 10) ) != MP_OKAY) goto LTM_ERR;
1270 printf(" '56' a == %s, length = %zu\n", buf, written);
1271
1272 if( (err = mp_to_radix(&a, buf, 4u, &written, 10) ) != MP_OKAY) goto LTM_ERR;
1273 printf(" '456' a == %s, length = %zu\n", buf, written);
1274 if( (err = mp_to_radix(&a, buf, 30u, &written, 10) ) != MP_OKAY) goto LTM_ERR;
1275 printf(" '123456' a == %s, length = %zu, error = %s\n",
1276 buf, written, mp_error_to_string(err));
1277 */
1278 if ((err = mp_read_radix(&a, "-123456", 10)) != MP_OKAY) goto LTM_ERR;
1279 if ((err = mp_to_radix(&a, buf, SIZE_MAX, &written, 10)) != MP_OKAY) goto LTM_ERR;
1280 printf(" '-123456' a == %s, length = %zu\n", buf, written);
1281
1282 if ((err = mp_read_radix(&a, "0", 10)) != MP_OKAY) goto LTM_ERR;
1283 if ((err = mp_to_radix(&a, buf, SIZE_MAX, &written, 10)) != MP_OKAY) goto LTM_ERR;
1284 printf(" '0' a == %s, length = %zu\n", buf, written);
1285
1286
1287
1288 /* Although deprecated it needs to function as long as it isn't dropped */
1289 /*
1290 printf("Testing deprecated mp_toradix_n\n");
1291 if( (err = mp_read_radix(&a, "-123456", 10) ) != MP_OKAY) goto LTM_ERR;
1292 if( (err = mp_toradix_n(&a, buf, 10, 3) ) != MP_OKAY) goto LTM_ERR;
1293 printf("a == %s\n", buf);
1294 if( (err = mp_toradix_n(&a, buf, 10, 4) ) != MP_OKAY) goto LTM_ERR;
1295 printf("a == %s\n", buf);
1296 if( (err = mp_toradix_n(&a, buf, 10, 30) ) != MP_OKAY) goto LTM_ERR;
1297 printf("a == %s\n", buf);
1298 */
1299
1300
1301 while (0) {
1302 char *s = fgets(buf, sizeof(buf), stdin);
1303 if (s != buf) break;
1304 mp_read_radix(&a, buf, 10);
1305 mp_prime_next_prime(&a, 5, 1);
1306 mp_to_radix(&a, buf, sizeof(buf), NULL, 10);
1307 printf("%s, %lu\n", buf, (unsigned long)a.dp[0] & 3uL);
1308 }
1309
1310 mp_clear(&a);
1311 return EXIT_SUCCESS;
1312 LTM_ERR:
1313 mp_clear(&a);
1314 return EXIT_FAILURE;
1315 }
1316
test_mp_cnt_lsb(void)1317 static int test_mp_cnt_lsb(void)
1318 {
1319 int ix;
1320
1321 mp_int a, b;
1322 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
1323 return EXIT_FAILURE;
1324 }
1325
1326 mp_set(&a, 1uL);
1327 for (ix = 0; ix < 1024; ix++) {
1328 if (mp_cnt_lsb(&a) != ix) {
1329 printf("Failed at %d, %d\n", ix, mp_cnt_lsb(&a));
1330 goto LBL_ERR;
1331 }
1332 mp_mul_2(&a, &a);
1333 }
1334
1335 mp_clear_multi(&a, &b, NULL);
1336 return EXIT_SUCCESS;
1337 LBL_ERR:
1338 mp_clear_multi(&a, &b, NULL);
1339 return EXIT_FAILURE;
1340
1341 }
1342
test_mp_reduce_2k(void)1343 static int test_mp_reduce_2k(void)
1344 {
1345 int ix, cnt;
1346
1347 mp_int a, b, c, d;
1348 if (mp_init_multi(&a, &b, &c, &d, NULL)!= MP_OKAY) {
1349 return EXIT_FAILURE;
1350 }
1351
1352 /* test mp_reduce_2k */
1353 for (cnt = 3; cnt <= 128; ++cnt) {
1354 mp_digit tmp;
1355
1356 mp_2expt(&a, cnt);
1357 mp_sub_d(&a, 2uL, &a); /* a = 2**cnt - 2 */
1358
1359 printf("\r %4d bits", cnt);
1360 printf("(%d)", mp_reduce_is_2k(&a));
1361 mp_reduce_2k_setup(&a, &tmp);
1362 printf("(%lu)", (unsigned long) tmp);
1363 for (ix = 0; ix < 1000; ix++) {
1364 if (!(ix & 127)) {
1365 printf(".");
1366 fflush(stdout);
1367 }
1368 mp_rand(&b, (cnt / MP_DIGIT_BIT + 1) * 2);
1369 mp_copy(&c, &b);
1370 mp_mod(&c, &a, &c);
1371 mp_reduce_2k(&b, &a, 2uL);
1372 if (mp_cmp(&c, &b) != MP_EQ) {
1373 printf("FAILED\n");
1374 goto LBL_ERR;
1375 }
1376 }
1377 }
1378
1379 mp_clear_multi(&a, &b, &c, &d, NULL);
1380 return EXIT_SUCCESS;
1381 LBL_ERR:
1382 mp_clear_multi(&a, &b, &c, &d, NULL);
1383 return EXIT_FAILURE;
1384 }
1385
test_mp_div_3(void)1386 static int test_mp_div_3(void)
1387 {
1388 int cnt;
1389
1390 mp_int a, b, c, d, e;
1391 if (mp_init_multi(&a, &b, &c, &d, &e, NULL)!= MP_OKAY) {
1392 return EXIT_FAILURE;
1393 }
1394
1395 /* test mp_div_3 */
1396 mp_set(&d, 3uL);
1397 for (cnt = 0; cnt < 10000;) {
1398 mp_digit r2;
1399
1400 if (!(++cnt & 127)) {
1401 printf("%9d\r", cnt);
1402 fflush(stdout);
1403 }
1404 mp_rand(&a, abs(rand_int()) % 128 + 1);
1405 mp_div(&a, &d, &b, &e);
1406 mp_div_3(&a, &c, &r2);
1407
1408 if (mp_cmp(&b, &c) || mp_cmp_d(&e, r2)) {
1409 printf("\nmp_div_3 => Failure\n");
1410 goto LBL_ERR;
1411 }
1412 }
1413 printf("\nPassed div_3 testing");
1414
1415 mp_clear_multi(&a, &b, &c, &d, &e, NULL);
1416 return EXIT_SUCCESS;
1417 LBL_ERR:
1418 mp_clear_multi(&a, &b, &c, &d, &e, NULL);
1419 return EXIT_FAILURE;
1420 }
1421
test_mp_dr_reduce(void)1422 static int test_mp_dr_reduce(void)
1423 {
1424 mp_digit mp;
1425 int cnt;
1426 unsigned rr;
1427 int ix;
1428
1429 mp_int a, b, c;
1430 if (mp_init_multi(&a, &b, &c, NULL)!= MP_OKAY) {
1431 return EXIT_FAILURE;
1432 }
1433
1434 /* test the DR reduction */
1435 for (cnt = 2; cnt < 32; cnt++) {
1436 printf("\r%d digit modulus", cnt);
1437 mp_grow(&a, cnt);
1438 mp_zero(&a);
1439 for (ix = 1; ix < cnt; ix++) {
1440 a.dp[ix] = MP_MASK;
1441 }
1442 a.used = cnt;
1443 a.dp[0] = 3;
1444
1445 mp_rand(&b, cnt - 1);
1446 mp_copy(&b, &c);
1447
1448 rr = 0;
1449 do {
1450 if (!(rr & 127)) {
1451 printf(".");
1452 fflush(stdout);
1453 }
1454 mp_sqr(&b, &b);
1455 mp_add_d(&b, 1uL, &b);
1456 mp_copy(&b, &c);
1457
1458 mp_mod(&b, &a, &b);
1459 mp_dr_setup(&a, &mp);
1460 mp_dr_reduce(&c, &a, mp);
1461
1462 if (mp_cmp(&b, &c) != MP_EQ) {
1463 printf("Failed on trial %u\n", rr);
1464 goto LBL_ERR;
1465 }
1466 } while (++rr < 500);
1467 printf(" passed");
1468 fflush(stdout);
1469 }
1470
1471 mp_clear_multi(&a, &b, &c, NULL);
1472 return EXIT_SUCCESS;
1473 LBL_ERR:
1474 mp_clear_multi(&a, &b, &c, NULL);
1475 return EXIT_FAILURE;
1476 }
1477
test_mp_reduce_2k_l(void)1478 static int test_mp_reduce_2k_l(void)
1479 {
1480 # if LTM_DEMO_TEST_REDUCE_2K_L
1481 mp_int a, b, c, d;
1482 int cnt;
1483 char buf[4096];
1484 size_t length[1];
1485 if (mp_init_multi(&a, &b, NULL)!= MP_OKAY) {
1486 return EXIT_FAILURE;
1487 }
1488 /* test the mp_reduce_2k_l code */
1489 # if LTM_DEMO_TEST_REDUCE_2K_L == 1
1490 /* first load P with 2^1024 - 0x2A434 B9FDEC95 D8F9D550 FFFFFFFF FFFFFFFF */
1491 mp_2expt(&a, 1024);
1492 mp_read_radix(&b, "2A434B9FDEC95D8F9D550FFFFFFFFFFFFFFFF", 16);
1493 mp_sub(&a, &b, &a);
1494 # elif LTM_DEMO_TEST_REDUCE_2K_L == 2
1495 /* p = 2^2048 - 0x1 00000000 00000000 00000000 00000000 4945DDBF 8EA2A91D 5776399B B83E188F */
1496 mp_2expt(&a, 2048);
1497 mp_read_radix(&b,
1498 "1000000000000000000000000000000004945DDBF8EA2A91D5776399BB83E188F",
1499 16);
1500 mp_sub(&a, &b, &a);
1501 # else
1502 # error oops
1503 # endif
1504 *length = sizeof(buf);
1505 mp_to_radix(&a, buf, length, 10);
1506 printf("\n\np==%s, length = %zu\n", buf, *length);
1507 /* now mp_reduce_is_2k_l() should return */
1508 if (mp_reduce_is_2k_l(&a) != 1) {
1509 printf("mp_reduce_is_2k_l() return 0, should be 1\n");
1510 goto LBL_ERR;
1511 }
1512 mp_reduce_2k_setup_l(&a, &d);
1513 /* now do a million square+1 to see if it varies */
1514 mp_rand(&b, 64);
1515 mp_mod(&b, &a, &b);
1516 mp_copy(&b, &c);
1517 printf("Testing: mp_reduce_2k_l...");
1518 fflush(stdout);
1519 for (cnt = 0; cnt < (int)(1uL << 20); cnt++) {
1520 mp_sqr(&b, &b);
1521 mp_add_d(&b, 1uL, &b);
1522 mp_reduce_2k_l(&b, &a, &d);
1523 mp_sqr(&c, &c);
1524 mp_add_d(&c, 1uL, &c);
1525 mp_mod(&c, &a, &c);
1526 if (mp_cmp(&b, &c) != MP_EQ) {
1527 printf("mp_reduce_2k_l() failed at step %d\n", cnt);
1528 mp_to_hex(&b, buf, sizeof(buf));
1529 printf("b == %s\n", buf);
1530 mp_to_hex(&c, buf, sizeof(buf));
1531 printf("c == %s\n", buf);
1532 goto LBL_ERR;
1533 }
1534 }
1535
1536 mp_clear_multi(&a, &b, NULL);
1537 return EXIT_SUCCESS;
1538 LBL_ERR:
1539 mp_clear_multi(&a, &b, NULL);
1540 return EXIT_FAILURE;
1541 #else
1542 return EXIT_SUCCESS;
1543 # endif /* LTM_DEMO_TEST_REDUCE_2K_L */
1544 }
1545 /* stripped down version of mp_radix_size. The faster version can be off by up t
1546 o +3 */
1547 /* TODO: This function should be removed, replaced by mp_radix_size, mp_radix_size_overestimate in 2.0 */
s_rs(const mp_int * a,int radix,uint32_t * size)1548 static mp_err s_rs(const mp_int *a, int radix, uint32_t *size)
1549 {
1550 mp_err res;
1551 uint32_t digs = 0u;
1552 mp_int t;
1553 mp_digit d;
1554 *size = 0u;
1555 if (mp_iszero(a) == MP_YES) {
1556 *size = 2u;
1557 return MP_OKAY;
1558 }
1559 if (radix == 2) {
1560 *size = (uint32_t)mp_count_bits(a) + 1u;
1561 return MP_OKAY;
1562 }
1563 if ((res = mp_init_copy(&t, a)) != MP_OKAY) {
1564 return res;
1565 }
1566 t.sign = MP_ZPOS;
1567 while (mp_iszero(&t) == MP_NO) {
1568 if ((res = mp_div_d(&t, (mp_digit)radix, &t, &d)) != MP_OKAY) {
1569 mp_clear(&t);
1570 return res;
1571 }
1572 ++digs;
1573 }
1574 mp_clear(&t);
1575 *size = digs + 1;
1576 return MP_OKAY;
1577 }
test_mp_log_u32(void)1578 static int test_mp_log_u32(void)
1579 {
1580 mp_int a;
1581 mp_digit d;
1582 uint32_t base, lb, size;
1583 const uint32_t max_base = MP_MIN(UINT32_MAX, MP_DIGIT_MAX);
1584
1585 if (mp_init(&a) != MP_OKAY) {
1586 goto LBL_ERR;
1587 }
1588
1589 /*
1590 base a result
1591 0 x MP_VAL
1592 1 x MP_VAL
1593 */
1594 mp_set(&a, 42uL);
1595 base = 0u;
1596 if (mp_log_u32(&a, base, &lb) != MP_VAL) {
1597 goto LBL_ERR;
1598 }
1599 base = 1u;
1600 if (mp_log_u32(&a, base, &lb) != MP_VAL) {
1601 goto LBL_ERR;
1602 }
1603 /*
1604 base a result
1605 2 0 MP_VAL
1606 2 1 0
1607 2 2 1
1608 2 3 1
1609 */
1610 base = 2u;
1611 mp_zero(&a);
1612 if (mp_log_u32(&a, base, &lb) != MP_VAL) {
1613 goto LBL_ERR;
1614 }
1615
1616 for (d = 1; d < 4; d++) {
1617 mp_set(&a, d);
1618 if (mp_log_u32(&a, base, &lb) != MP_OKAY) {
1619 goto LBL_ERR;
1620 }
1621 if (lb != ((d == 1)?0uL:1uL)) {
1622 goto LBL_ERR;
1623 }
1624 }
1625 /*
1626 base a result
1627 3 0 MP_VAL
1628 3 1 0
1629 3 2 0
1630 3 3 1
1631 */
1632 base = 3u;
1633 mp_zero(&a);
1634 if (mp_log_u32(&a, base, &lb) != MP_VAL) {
1635 goto LBL_ERR;
1636 }
1637 for (d = 1; d < 4; d++) {
1638 mp_set(&a, d);
1639 if (mp_log_u32(&a, base, &lb) != MP_OKAY) {
1640 goto LBL_ERR;
1641 }
1642 if (lb != ((d < base)?0uL:1uL)) {
1643 goto LBL_ERR;
1644 }
1645 }
1646
1647 /*
1648 bases 2..64 with "a" a random large constant.
1649 The range of bases tested allows to check with
1650 radix_size.
1651 */
1652 if (mp_rand(&a, 10) != MP_OKAY) {
1653 goto LBL_ERR;
1654 }
1655 for (base = 2u; base < 65u; base++) {
1656 if (mp_log_u32(&a, base, &lb) != MP_OKAY) {
1657 goto LBL_ERR;
1658 }
1659 if (s_rs(&a,(int)base, &size) != MP_OKAY) {
1660 goto LBL_ERR;
1661 }
1662 /* radix_size includes the memory needed for '\0', too*/
1663 size -= 2;
1664 if (lb != size) {
1665 goto LBL_ERR;
1666 }
1667 }
1668
1669 /*
1670 bases 2..64 with "a" a random small constant to
1671 test the part of mp_ilogb that uses native types.
1672 */
1673 if (mp_rand(&a, 1) != MP_OKAY) {
1674 goto LBL_ERR;
1675 }
1676 for (base = 2u; base < 65u; base++) {
1677 if (mp_log_u32(&a, base, &lb) != MP_OKAY) {
1678 goto LBL_ERR;
1679 }
1680 if (s_rs(&a,(int)base, &size) != MP_OKAY) {
1681 goto LBL_ERR;
1682 }
1683 size -= 2;
1684 if (lb != size) {
1685 goto LBL_ERR;
1686 }
1687 }
1688
1689 /*Test upper edgecase with base UINT32_MAX and number (UINT32_MAX/2)*UINT32_MAX^10 */
1690 mp_set(&a, max_base);
1691 if (mp_expt_u32(&a, 10uL, &a) != MP_OKAY) {
1692 goto LBL_ERR;
1693 }
1694 if (mp_add_d(&a, max_base / 2, &a) != MP_OKAY) {
1695 goto LBL_ERR;
1696 }
1697 if (mp_log_u32(&a, max_base, &lb) != MP_OKAY) {
1698 goto LBL_ERR;
1699 }
1700 if (lb != 10u) {
1701 goto LBL_ERR;
1702 }
1703
1704 mp_clear(&a);
1705 return EXIT_SUCCESS;
1706 LBL_ERR:
1707 mp_clear(&a);
1708 return EXIT_FAILURE;
1709 }
1710
test_mp_incr(void)1711 static int test_mp_incr(void)
1712 {
1713 mp_int a, b;
1714 mp_err e = MP_OKAY;
1715
1716 if ((e = mp_init_multi(&a, &b, NULL)) != MP_OKAY) {
1717 goto LTM_ERR;
1718 }
1719
1720 /* Does it increment inside the limits of a MP_xBIT limb? */
1721 mp_set(&a, MP_MASK/2);
1722 if ((e = mp_incr(&a)) != MP_OKAY) {
1723 goto LTM_ERR;
1724 }
1725 if (mp_cmp_d(&a, (MP_MASK/2uL) + 1uL) != MP_EQ) {
1726 goto LTM_ERR;
1727 }
1728
1729 /* Does it increment outside of the limits of a MP_xBIT limb? */
1730 mp_set(&a, MP_MASK);
1731 mp_set(&b, MP_MASK);
1732 if ((e = mp_incr(&a)) != MP_OKAY) {
1733 goto LTM_ERR;
1734 }
1735 if ((e = mp_add_d(&b, 1uL, &b)) != MP_OKAY) {
1736 goto LTM_ERR;
1737 }
1738 if (mp_cmp(&a, &b) != MP_EQ) {
1739 goto LTM_ERR;
1740 }
1741
1742 /* Does it increment from -1 to 0? */
1743 mp_set(&a, 1uL);
1744 a.sign = MP_NEG;
1745 if ((e = mp_incr(&a)) != MP_OKAY) {
1746 goto LTM_ERR;
1747 }
1748 if (mp_cmp_d(&a, 0uL) != MP_EQ) {
1749 goto LTM_ERR;
1750 }
1751
1752 /* Does it increment from -(MP_MASK + 1) to -MP_MASK? */
1753 mp_set(&a, MP_MASK);
1754 if ((e = mp_add_d(&a, 1uL, &a)) != MP_OKAY) {
1755 goto LTM_ERR;
1756 }
1757 a.sign = MP_NEG;
1758 if ((e = mp_incr(&a)) != MP_OKAY) {
1759 goto LTM_ERR;
1760 }
1761 if (a.sign != MP_NEG) {
1762 goto LTM_ERR;
1763 }
1764 a.sign = MP_ZPOS;
1765 if (mp_cmp_d(&a, MP_MASK) != MP_EQ) {
1766 goto LTM_ERR;
1767 }
1768
1769 mp_clear_multi(&a, &b, NULL);
1770 return EXIT_SUCCESS;
1771 LTM_ERR:
1772 mp_clear_multi(&a, &b, NULL);
1773 return EXIT_FAILURE;
1774 }
1775
test_mp_decr(void)1776 static int test_mp_decr(void)
1777 {
1778 mp_int a, b;
1779 mp_err e = MP_OKAY;
1780
1781 if ((e = mp_init_multi(&a, &b, NULL)) != MP_OKAY) {
1782 goto LTM_ERR;
1783 }
1784
1785 /* Does it decrement inside the limits of a MP_xBIT limb? */
1786 mp_set(&a, MP_MASK/2);
1787 if ((e = mp_decr(&a)) != MP_OKAY) {
1788 goto LTM_ERR;
1789 }
1790 if (mp_cmp_d(&a, (MP_MASK/2uL) - 1uL) != MP_EQ) {
1791 goto LTM_ERR;
1792 }
1793
1794 /* Does it decrement outside of the limits of a MP_xBIT limb? */
1795 mp_set(&a, MP_MASK);
1796 if ((e = mp_add_d(&a, 1uL, &a)) != MP_OKAY) {
1797 goto LTM_ERR;
1798 }
1799 if ((e = mp_decr(&a)) != MP_OKAY) {
1800 goto LTM_ERR;
1801 }
1802 if (mp_cmp_d(&a, MP_MASK) != MP_EQ) {
1803 goto LTM_ERR;
1804 }
1805
1806 /* Does it decrement from 0 to -1? */
1807 mp_zero(&a);
1808 if ((e = mp_decr(&a)) != MP_OKAY) {
1809 goto LTM_ERR;
1810 }
1811 if (a.sign == MP_NEG) {
1812 a.sign = MP_ZPOS;
1813 if (mp_cmp_d(&a, 1uL) != MP_EQ) {
1814 goto LTM_ERR;
1815 }
1816 } else {
1817 goto LTM_ERR;
1818 }
1819
1820
1821 /* Does it decrement from -MP_MASK to -(MP_MASK + 1)? */
1822 mp_set(&a, MP_MASK);
1823 a.sign = MP_NEG;
1824 mp_set(&b, MP_MASK);
1825 b.sign = MP_NEG;
1826 if ((e = mp_sub_d(&b, 1uL, &b)) != MP_OKAY) {
1827 goto LTM_ERR;
1828 }
1829 if ((e = mp_decr(&a)) != MP_OKAY) {
1830 goto LTM_ERR;
1831 }
1832 if (mp_cmp(&a, &b) != MP_EQ) {
1833 goto LTM_ERR;
1834 }
1835
1836 mp_clear_multi(&a, &b, NULL);
1837 return EXIT_SUCCESS;
1838 LTM_ERR:
1839 mp_clear_multi(&a, &b, NULL);
1840 return EXIT_FAILURE;
1841 }
1842
1843 /*
1844 Cannot test mp_exp(_d) without mp_root and vice versa.
1845 So one of the two has to be tested from scratch.
1846
1847 Numbers generated by
1848 for i in {1..10}
1849 do
1850 seed=$(head -c 10000 /dev/urandom | tr -dc '[:digit:]' | head -c 120);
1851 echo $seed;
1852 convertbase $seed 10 64;
1853 done
1854
1855 (The program "convertbase" uses libtommath's to/from_radix functions)
1856
1857 Roots were precalculated with Pari/GP
1858
1859 default(realprecision,1000);
1860 for(n=3,100,r = floor(a^(1/n));printf("\"" r "\", "))
1861
1862 All numbers as strings to simplifiy things, especially for the
1863 low-mp branch.
1864 */
1865
test_mp_root_u32(void)1866 static int test_mp_root_u32(void)
1867 {
1868 mp_int a, c, r;
1869 mp_err e;
1870 int i, j;
1871
1872 const char *input[] = {
1873 "4n9cbk886QtLQmofprid3l2Q0GD8Yv979Lh8BdZkFE8g2pDUUSMBET/+M/YFyVZ3mBp",
1874 "5NlgzHhmIX05O5YoW5yW5reAlVNtRAlIcN2dfoATnNdc1Cw5lHZUTwNthmK6/ZLKfY6",
1875 "3gweiHDX+ji5utraSe46IJX+uuh7iggs63xIpMP5MriU4Np+LpHI5are8RzS9pKh9xP",
1876 "5QOJUSKMrfe7LkeyJOlupS8h7bjT+TXmZkDzOjZtfj7mdA7cbg0lRX3CuafhjIrpK8S",
1877 "4HtYFldVkyVbrlg/s7kmaA7j45PvLQm+1bbn6ehgP8tVoBmGbv2yDQI1iQQze4AlHyN",
1878 "3bwCUx79NAR7c68OPSp5ZabhZ9aBEr7rWNTO2oMY7zhbbbw7p6shSMxqE9K9nrTNucf",
1879 "4j5RGb78TfuYSzrXn0z6tiAoWiRI81hGY3el9AEa9S+gN4x/AmzotHT2Hvj6lyBpE7q",
1880 "4lwg30SXqZhEHNsl5LIXdyu7UNt0VTWebP3m7+WUL+hsnFW9xJe7UnzYngZsvWh14IE",
1881 "1+tcqFeRuGqjRADRoRUJ8gL4UUSFQVrVVoV6JpwVcKsuBq5G0pABn0dLcQQQMViiVRj",
1882 "hXwxuFySNSFcmbrs/coz4FUAaUYaOEt+l4V5V8vY71KyBvQPxRq/6lsSrG2FHvWDax"
1883 };
1884 /* roots 3-100 of the above */
1885 const char *root[10][100] = {
1886 {
1887 "9163694094944489658600517465135586130944",
1888 "936597377180979771960755204040", "948947857956884030956907",
1889 "95727185767390496595", "133844854039712620", "967779611885360",
1890 "20926191452627", "974139547476", "79203891950", "9784027073",
1891 "1667309744", "365848129", "98268452", "31109156", "11275351",
1892 "4574515", "2040800", "986985", "511525", "281431", "163096",
1893 "98914", "62437", "40832", "27556", "19127", "13614", "9913",
1894 "7367", "5577", "4294", "3357", "2662", "2138", "1738", "1428",
1895 "1185", "993", "839", "715", "613", "530", "461", "403", "355",
1896 "314", "279", "249", "224", "202", "182", "166", "151", "138",
1897 "126", "116", "107", "99", "92", "85", "79", "74", "69", "65", "61",
1898 "57", "54", "51", "48", "46", "43", "41", "39", "37", "36", "34",
1899 "32", "31", "30", "28", "27", "26", "25", "24", "23", "23", "22",
1900 "21", "20", "20", "19", "18", "18", "17", "17", "16", "16", "15"
1901 }, {
1902 "9534798256755061606359588498764080011382",
1903 "964902943621813525741417593772", "971822399862464674540423",
1904 "97646291566833512831", "136141536090599560", "982294733581430",
1905 "21204945933335", "985810529393", "80066084985", "9881613813",
1906 "1682654547", "368973625", "99051783", "31341581", "11354620",
1907 "4604882", "2053633", "992879", "514434", "282959", "163942",
1908 "99406", "62736", "41020", "27678", "19208", "13670", "9952",
1909 "7395", "5598", "4310", "3369", "2671", "2145", "1744", "1433",
1910 "1189", "996", "842", "717", "615", "531", "462", "404", "356",
1911 "315", "280", "250", "224", "202", "183", "166", "151", "138",
1912 "127", "116", "107", "99", "92", "85", "80", "74", "70", "65", "61",
1913 "58", "54", "51", "48", "46", "43", "41", "39", "37", "36", "34",
1914 "32", "31", "30", "29", "27", "26", "25", "24", "23", "23", "22",
1915 "21", "20", "20", "19", "18", "18", "17", "17", "16", "16", "15"
1916 }, {
1917 "8398539113202579297642815367509019445624",
1918 "877309458945432597462853440936", "900579899458998599215071",
1919 "91643543761699761637", "128935656335800903", "936647990947203",
1920 "20326748623514", "948988882684", "77342677787", "9573063447",
1921 "1634096832", "359076114", "96569670", "30604705", "11103188",
1922 "4508519", "2012897", "974160", "505193", "278105", "161251",
1923 "97842", "61788", "40423", "27291", "18949", "13492", "9826",
1924 "7305", "5532", "4260", "3332", "2642", "2123", "1726", "1418",
1925 "1177", "986", "834", "710", "610", "527", "458", "401", "353",
1926 "312", "278", "248", "223", "201", "181", "165", "150", "137",
1927 "126", "116", "107", "99", "91", "85", "79", "74", "69", "65", "61",
1928 "57", "54", "51", "48", "46", "43", "41", "39", "37", "35", "34",
1929 "32", "31", "30", "28", "27", "26", "25", "24", "23", "22", "22",
1930 "21", "20", "20", "19", "18", "18", "17", "17", "16", "16", "15"
1931 }, {
1932 "9559098494021810340217797724866627755195",
1933 "966746709063325235560830083787", "973307706084821682248292",
1934 "97770642291138756434", "136290128605981259", "983232784778520",
1935 "21222944848922", "986563584410", "80121684894", "9887903837",
1936 "1683643206", "369174929", "99102220", "31356542", "11359721",
1937 "4606836", "2054458", "993259", "514621", "283057", "163997",
1938 "99437", "62755", "41032", "27686", "19213", "13674", "9955",
1939 "7397", "5599", "4311", "3370", "2672", "2146", "1744", "1433",
1940 "1189", "996", "842", "717", "615", "532", "462", "404", "356",
1941 "315", "280", "250", "224", "202", "183", "166", "151", "138",
1942 "127", "116", "107", "99", "92", "86", "80", "74", "70", "65", "61",
1943 "58", "54", "51", "48", "46", "43", "41", "39", "37", "36", "34",
1944 "32", "31", "30", "29", "27", "26", "25", "24", "23", "23", "22",
1945 "21", "20", "20", "19", "18", "18", "17", "17", "16", "16", "15"
1946 }, {
1947 "8839202025813295923132694443541993309220",
1948 "911611499784863252820288596270", "928640961450376817534853",
1949 "94017030509441723821", "131792686685970629", "954783483196511",
1950 "20676214073400", "963660189823", "78428929840", "9696237956",
1951 "1653495486", "363032624", "97562430", "30899570", "11203842",
1952 "4547110", "2029216", "981661", "508897", "280051", "162331",
1953 "98469", "62168", "40663", "27446", "19053", "13563", "9877",
1954 "7341", "5558", "4280", "3347", "2654", "2132", "1733", "1424",
1955 "1182", "990", "837", "713", "612", "529", "460", "402", "354",
1956 "313", "279", "249", "223", "201", "182", "165", "150", "138",
1957 "126", "116", "107", "99", "92", "85", "79", "74", "69", "65", "61",
1958 "57", "54", "51", "48", "46", "43", "41", "39", "37", "36", "34",
1959 "32", "31", "30", "28", "27", "26", "25", "24", "23", "23", "22",
1960 "21", "20", "20", "19", "18", "18", "17", "17", "16", "16", "15"
1961 }, {
1962 "8338442683973420410660145045849076963795",
1963 "872596990706967613912664152945", "896707843885562730147307",
1964 "91315073695274540969", "128539440806486007", "934129001105825",
1965 "20278149285734", "946946589774", "77191347471", "9555892093",
1966 "1631391010", "358523975", "96431070", "30563524", "11089126",
1967 "4503126", "2010616", "973111", "504675", "277833", "161100",
1968 "97754", "61734", "40390", "27269", "18934", "13482", "9819",
1969 "7300", "5528", "4257", "3330", "2641", "2122", "1725", "1417",
1970 "1177", "986", "833", "710", "609", "527", "458", "401", "353",
1971 "312", "278", "248", "222", "200", "181", "165", "150", "137",
1972 "126", "116", "107", "99", "91", "85", "79", "74", "69", "65", "61",
1973 "57", "54", "51", "48", "46", "43", "41", "39", "37", "35", "34",
1974 "32", "31", "30", "28", "27", "26", "25", "24", "23", "22", "22",
1975 "21", "20", "20", "19", "18", "18", "17", "17", "16", "16", "15"
1976 }, {
1977 "9122818552483814953977703257848970704164",
1978 "933462289569511464780529972314", "946405863353935713909178",
1979 "95513446972056321834", "133588658082928446",
1980 "966158521967027", "20895030642048", "972833934108",
1981 "79107381638", "9773098125", "1665590516", "365497822",
1982 "98180628", "31083090", "11266459", "4571108", "2039360",
1983 "986323", "511198", "281260", "163001", "98858",
1984 "62404", "40811", "27543", "19117", "13608", "9908",
1985 "7363", "5575", "4292", "3356", "2661", "2138",
1986 "1737", "1428", "1185", "993", "839", "714", "613",
1987 "530", "461", "403", "355", "314", "279", "249",
1988 "224", "202", "182", "165", "151", "138", "126",
1989 "116", "107", "99", "92", "85", "79", "74", "69",
1990 "65", "61", "57", "54", "51", "48", "46", "43",
1991 "41", "39", "37", "36", "34", "32", "31", "30",
1992 "28", "27", "26", "25", "24", "23", "23", "22",
1993 "21", "20", "20", "19", "18", "18", "17", "17",
1994 "16", "16", "15"
1995 }, {
1996 "9151329724083804100369546479681933027521",
1997 "935649419557299174433860420387", "948179413831316112751907",
1998 "95662582675170358900", "133767426788182384",
1999 "967289728859610", "20916775466497", "973745045600",
2000 "79174731802", "9780725058", "1666790321", "365742295",
2001 "98241919", "31101281", "11272665", "4573486", "2040365",
2002 "986785", "511426", "281380", "163067", "98897",
2003 "62427", "40826", "27552", "19124", "13612", "9911",
2004 "7366", "5576", "4294", "3357", "2662", "2138",
2005 "1738", "1428", "1185", "993", "839", "715", "613",
2006 "530", "461", "403", "355", "314", "279", "249",
2007 "224", "202", "182", "165", "151", "138", "126",
2008 "116", "107", "99", "92", "85", "79", "74", "69",
2009 "65", "61", "57", "54", "51", "48", "46", "43",
2010 "41", "39", "37", "36", "34", "32", "31", "30",
2011 "28", "27", "26", "25", "24", "23", "23", "22",
2012 "21", "20", "20", "19", "18", "18", "17", "17",
2013 "16", "16", "15"
2014 }, {
2015 "6839396355168045468586008471269923213531",
2016 "752078770083218822016981965090", "796178899357307807726034",
2017 "82700643015444840424", "118072966296549115",
2018 "867224751770392", "18981881485802", "892288574037",
2019 "73130030771", "9093989389", "1558462688", "343617470",
2020 "92683740", "29448679", "10708016", "4356820", "1948676",
2021 "944610", "490587", "270425", "156989", "95362",
2022 "60284", "39477", "26675", "18536", "13208", "9627",
2023 "7161", "5426", "4181", "3272", "2596", "2087",
2024 "1697", "1395", "1159", "971", "821", "700", "601",
2025 "520", "452", "396", "348", "308", "274", "245",
2026 "220", "198", "179", "163", "148", "136", "124",
2027 "114", "106", "98", "91", "84", "78", "73", "68",
2028 "64", "60", "57", "53", "50", "48", "45", "43",
2029 "41", "39", "37", "35", "34", "32", "31", "29",
2030 "28", "27", "26", "25", "24", "23", "22", "22",
2031 "21", "20", "19", "19", "18", "18", "17", "17",
2032 "16", "16", "15"
2033 }, {
2034 "4788090721380022347683138981782307670424",
2035 "575601315594614059890185238256", "642831903229558719812840",
2036 "69196031110028430211", "101340693763170691",
2037 "758683936560287", "16854690815260", "801767985909",
2038 "66353290503", "8318415180", "1435359033", "318340531",
2039 "86304307", "27544217", "10054988", "4105446", "1841996",
2040 "895414", "466223", "257591", "149855", "91205",
2041 "57758", "37886", "25639", "17842", "12730", "9290",
2042 "6918", "5248", "4048", "3170", "2518", "2026",
2043 "1649", "1357", "1128", "946", "800", "682", "586",
2044 "507", "441", "387", "341", "302", "268", "240",
2045 "215", "194", "176", "160", "146", "133", "122",
2046 "112", "104", "96", "89", "83", "77", "72", "67",
2047 "63", "59", "56", "53", "50", "47", "45", "42",
2048 "40", "38", "36", "35", "33", "32", "30", "29",
2049 "28", "27", "26", "25", "24", "23", "22", "21",
2050 "21", "20", "19", "19", "18", "17", "17", "16",
2051 "16", "15", "15"
2052 }
2053 };
2054
2055 if ((e = mp_init_multi(&a, &c, &r, NULL)) != MP_OKAY) {
2056 return EXIT_FAILURE;
2057 }
2058 #ifdef MP_8BIT
2059 for (i = 0; i < 1; i++) {
2060 #else
2061 for (i = 0; i < 10; i++) {
2062 #endif
2063 mp_read_radix(&a, input[i], 64);
2064 #ifdef MP_8BIT
2065 for (j = 3; j < 10; j++) {
2066 #else
2067 for (j = 3; j < 100; j++) {
2068 #endif
2069 mp_root_u32(&a, (uint32_t)j, &c);
2070 mp_read_radix(&r, root[i][j-3], 10);
2071 if (mp_cmp(&r, &c) != MP_EQ) {
2072 fprintf(stderr, "mp_root_u32 failed at input #%d, root #%d\n", i, j);
2073 goto LTM_ERR;
2074 }
2075 }
2076 }
2077 mp_clear_multi(&a, &c, &r, NULL);
2078 return EXIT_SUCCESS;
2079 LTM_ERR:
2080 mp_clear_multi(&a, &c, &r, NULL);
2081 return EXIT_FAILURE;
2082 }
2083
2084 static int test_s_mp_balance_mul(void)
2085 {
2086 mp_int a, b, c;
2087 mp_err e = MP_OKAY;
2088
2089 const char *na =
2090 "4b0I5uMTujCysw+1OOuOyH2FX2WymrHUqi8BBDb7XpkV/4i7vXTbEYUy/kdIfCKu5jT5JEqYkdmnn3jAYo8XShPzNLxZx9yoLjxYRyptSuOI2B1DspvbIVYXY12sxPZ4/HCJ4Usm2MU5lO/006KnDMxuxiv1rm6YZJZ0eZU";
2091 const char *nb = "3x9vs0yVi4hIq7poAeVcggC3WoRt0zRLKO";
2092 const char *nc =
2093 "HzrSq9WVt1jDTVlwUxSKqxctu2GVD+N8+SVGaPFRqdxyld6IxDBbj27BPJzYUdR96k3sWpkO8XnDBvupGPnehpQe4KlO/KmN1PjFov/UTZYM+LYzkFcBPyV6hkkL8ePC1rlFLAHzgJMBCXVp4mRqtkQrDsZXXlcqlbTFu69wF6zDEysiX2cAtn/kP9ldblJiwYPCD8hG";
2094
2095 if ((e = mp_init_multi(&a, &b, &c, NULL)) != MP_OKAY) {
2096 goto LTM_ERR;
2097 }
2098
2099 if ((e = mp_read_radix(&a, na, 64)) != MP_OKAY) {
2100 goto LTM_ERR;
2101 }
2102 if ((e = mp_read_radix(&b, nb, 64)) != MP_OKAY) {
2103 goto LTM_ERR;
2104 }
2105
2106 if ((e = s_mp_balance_mul(&a, &b, &c)) != MP_OKAY) {
2107 goto LTM_ERR;
2108 }
2109
2110 if ((e = mp_read_radix(&b, nc, 64)) != MP_OKAY) {
2111 goto LTM_ERR;
2112 }
2113
2114 if (mp_cmp(&b, &c) != MP_EQ) {
2115 goto LTM_ERR;
2116 }
2117
2118 mp_clear_multi(&a, &b, &c, NULL);
2119 return EXIT_SUCCESS;
2120 LTM_ERR:
2121 mp_clear_multi(&a, &b, &c, NULL);
2122 return EXIT_FAILURE;
2123 }
2124
2125 #define s_mp_mul(a, b, c) s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1)
2126 static int test_s_mp_karatsuba_mul(void)
2127 {
2128 mp_int a, b, c, d;
2129 int size, err;
2130
2131 if ((err = mp_init_multi(&a, &b, &c, &d, NULL)) != MP_OKAY) {
2132 goto LTM_ERR;
2133 }
2134 for (size = MP_KARATSUBA_MUL_CUTOFF; size < MP_KARATSUBA_MUL_CUTOFF + 20; size++) {
2135 if ((err = mp_rand(&a, size)) != MP_OKAY) {
2136 goto LTM_ERR;
2137 }
2138 if ((err = mp_rand(&b, size)) != MP_OKAY) {
2139 goto LTM_ERR;
2140 }
2141 if ((err = s_mp_karatsuba_mul(&a, &b, &c)) != MP_OKAY) {
2142 goto LTM_ERR;
2143 }
2144 if ((err = s_mp_mul(&a,&b,&d)) != MP_OKAY) {
2145 goto LTM_ERR;
2146 }
2147 if (mp_cmp(&c, &d) != MP_EQ) {
2148 fprintf(stderr, "Karatsuba multiplication failed at size %d\n", size);
2149 goto LTM_ERR;
2150 }
2151 }
2152
2153 mp_clear_multi(&a, &b, &c, &d, NULL);
2154 return EXIT_SUCCESS;
2155 LTM_ERR:
2156 mp_clear_multi(&a, &b, &c, &d, NULL);
2157 return EXIT_FAILURE;
2158 }
2159
2160 static int test_s_mp_karatsuba_sqr(void)
2161 {
2162 mp_int a, b, c;
2163 int size, err;
2164
2165 if ((err = mp_init_multi(&a, &b, &c, NULL)) != MP_OKAY) {
2166 goto LTM_ERR;
2167 }
2168 for (size = MP_KARATSUBA_SQR_CUTOFF; size < MP_KARATSUBA_SQR_CUTOFF + 20; size++) {
2169 if ((err = mp_rand(&a, size)) != MP_OKAY) {
2170 goto LTM_ERR;
2171 }
2172 if ((err = s_mp_karatsuba_sqr(&a, &b)) != MP_OKAY) {
2173 goto LTM_ERR;
2174 }
2175 if ((err = s_mp_sqr(&a, &c)) != MP_OKAY) {
2176 goto LTM_ERR;
2177 }
2178 if (mp_cmp(&b, &c) != MP_EQ) {
2179 fprintf(stderr, "Karatsuba squaring failed at size %d\n", size);
2180 goto LTM_ERR;
2181 }
2182 }
2183
2184 mp_clear_multi(&a, &b, &c, NULL);
2185 return EXIT_SUCCESS;
2186 LTM_ERR:
2187 mp_clear_multi(&a, &b, &c, NULL);
2188 return EXIT_FAILURE;
2189 }
2190
2191 static int test_s_mp_toom_mul(void)
2192 {
2193 mp_int a, b, c, d;
2194 int size, err;
2195
2196 #if (MP_DIGIT_BIT == 60)
2197 int tc_cutoff;
2198 #endif
2199
2200 if ((err = mp_init_multi(&a, &b, &c, &d, NULL)) != MP_OKAY) {
2201 goto LTM_ERR;
2202 }
2203 /* This number construction is limb-size specific */
2204 #if (MP_DIGIT_BIT == 60)
2205 if ((err = mp_rand(&a, 1196)) != MP_OKAY) {
2206 goto LTM_ERR;
2207 }
2208 if ((err = mp_mul_2d(&a,71787 - mp_count_bits(&a), &a)) != MP_OKAY) {
2209 goto LTM_ERR;
2210 }
2211
2212 if ((err = mp_rand(&b, 1338)) != MP_OKAY) {
2213 goto LTM_ERR;
2214 }
2215 if ((err = mp_mul_2d(&b, 80318 - mp_count_bits(&b), &b)) != MP_OKAY) {
2216 goto LTM_ERR;
2217 }
2218 if ((err = mp_mul_2d(&b, 6310, &b)) != MP_OKAY) {
2219 goto LTM_ERR;
2220 }
2221 if ((err = mp_2expt(&c, 99000 - 1000)) != MP_OKAY) {
2222 goto LTM_ERR;
2223 }
2224 if ((err = mp_add(&b, &c, &b)) != MP_OKAY) {
2225 goto LTM_ERR;
2226 }
2227
2228 tc_cutoff = TOOM_MUL_CUTOFF;
2229 TOOM_MUL_CUTOFF = INT_MAX;
2230 if ((err = mp_mul(&a, &b, &c)) != MP_OKAY) {
2231 goto LTM_ERR;
2232 }
2233 TOOM_MUL_CUTOFF = tc_cutoff;
2234 if ((err = mp_mul(&a, &b, &d)) != MP_OKAY) {
2235 goto LTM_ERR;
2236 }
2237 if (mp_cmp(&c, &d) != MP_EQ) {
2238 fprintf(stderr, "Toom-Cook 3-way multiplication failed for edgecase f1 * f2\n");
2239 goto LTM_ERR;
2240 }
2241 #endif
2242
2243 for (size = MP_TOOM_MUL_CUTOFF; size < MP_TOOM_MUL_CUTOFF + 20; size++) {
2244 if ((err = mp_rand(&a, size)) != MP_OKAY) {
2245 goto LTM_ERR;
2246 }
2247 if ((err = mp_rand(&b, size)) != MP_OKAY) {
2248 goto LTM_ERR;
2249 }
2250 if ((err = s_mp_toom_mul(&a, &b, &c)) != MP_OKAY) {
2251 goto LTM_ERR;
2252 }
2253 if ((err = s_mp_mul(&a,&b,&d)) != MP_OKAY) {
2254 goto LTM_ERR;
2255 }
2256 if (mp_cmp(&c, &d) != MP_EQ) {
2257 fprintf(stderr, "Toom-Cook 3-way multiplication failed at size %d\n", size);
2258 goto LTM_ERR;
2259 }
2260 }
2261
2262 mp_clear_multi(&a, &b, &c, &d, NULL);
2263 return EXIT_SUCCESS;
2264 LTM_ERR:
2265 mp_clear_multi(&a, &b, &c, &d, NULL);
2266 return EXIT_FAILURE;
2267 }
2268
2269 static int test_s_mp_toom_sqr(void)
2270 {
2271 mp_int a, b, c;
2272 int size, err;
2273
2274 if ((err = mp_init_multi(&a, &b, &c, NULL)) != MP_OKAY) {
2275 goto LTM_ERR;
2276 }
2277 for (size = MP_TOOM_SQR_CUTOFF; size < MP_TOOM_SQR_CUTOFF + 20; size++) {
2278 if ((err = mp_rand(&a, size)) != MP_OKAY) {
2279 goto LTM_ERR;
2280 }
2281 if ((err = s_mp_toom_sqr(&a, &b)) != MP_OKAY) {
2282 goto LTM_ERR;
2283 }
2284 if ((err = s_mp_sqr(&a, &c)) != MP_OKAY) {
2285 goto LTM_ERR;
2286 }
2287 if (mp_cmp(&b, &c) != MP_EQ) {
2288 fprintf(stderr, "Toom-Cook 3-way squaring failed at size %d\n", size);
2289 goto LTM_ERR;
2290 }
2291 }
2292
2293 mp_clear_multi(&a, &b, &c, NULL);
2294 return EXIT_SUCCESS;
2295 LTM_ERR:
2296 mp_clear_multi(&a, &b, &c, NULL);
2297 return EXIT_FAILURE;
2298 }
2299
2300 static int test_mp_read_write_ubin(void)
2301 {
2302 mp_int a, b, c;
2303 int err;
2304 size_t size, len;
2305 unsigned char *buf = NULL;
2306
2307 if ((err = mp_init_multi(&a, &b, &c, NULL)) != MP_OKAY) {
2308 goto LTM_ERR;
2309 }
2310
2311 if ((err = mp_rand(&a, 15)) != MP_OKAY) goto LTM_ERR;
2312 if ((err = mp_neg(&a, &b)) != MP_OKAY) goto LTM_ERR;
2313
2314 size = mp_ubin_size(&a);
2315 printf("mp_to_ubin_size %zu\n", size);
2316 buf = malloc(sizeof(*buf) * size);
2317 if (buf == NULL) {
2318 fprintf(stderr, "test_read_write_binaries (u) failed to allocate %zu bytes\n",
2319 sizeof(*buf) * size);
2320 goto LTM_ERR;
2321 }
2322
2323 if ((err = mp_to_ubin(&a, buf, size, &len)) != MP_OKAY) goto LTM_ERR;
2324 printf("mp_to_ubin len = %zu\n", len);
2325
2326 if ((err = mp_from_ubin(&c, buf, len)) != MP_OKAY) goto LTM_ERR;
2327
2328 if (mp_cmp(&a, &c) != MP_EQ) {
2329 fprintf(stderr, "to/from ubin cycle failed\n");
2330 goto LTM_ERR;
2331 }
2332 free(buf);
2333 mp_clear_multi(&a, &b, &c, NULL);
2334 return EXIT_SUCCESS;
2335 LTM_ERR:
2336 free(buf);
2337 mp_clear_multi(&a, &b, &c, NULL);
2338 return EXIT_FAILURE;
2339 }
2340
2341 static int test_mp_read_write_sbin(void)
2342 {
2343 mp_int a, b, c;
2344 int err;
2345 size_t size, len;
2346 unsigned char *buf = NULL;
2347
2348 if ((err = mp_init_multi(&a, &b, &c, NULL)) != MP_OKAY) {
2349 goto LTM_ERR;
2350 }
2351
2352 if ((err = mp_rand(&a, 15)) != MP_OKAY) goto LTM_ERR;
2353 if ((err = mp_neg(&a, &b)) != MP_OKAY) goto LTM_ERR;
2354
2355 size = mp_sbin_size(&a);
2356 printf("mp_to_sbin_size %zu\n", size);
2357 buf = malloc(sizeof(*buf) * size);
2358 if (buf == NULL) {
2359 fprintf(stderr, "test_read_write_binaries (s) failed to allocate %zu bytes\n",
2360 sizeof(*buf) * size);
2361 goto LTM_ERR;
2362 }
2363
2364 if ((err = mp_to_sbin(&b, buf, size, &len)) != MP_OKAY) goto LTM_ERR;
2365 printf("mp_to_sbin len = %zu\n", len);
2366
2367 if ((err = mp_from_sbin(&c, buf, len)) != MP_OKAY) goto LTM_ERR;
2368
2369 if (mp_cmp(&b, &c) != MP_EQ) {
2370 fprintf(stderr, "to/from ubin cycle failed\n");
2371 goto LTM_ERR;
2372 }
2373
2374 free(buf);
2375 mp_clear_multi(&a, &b, &c, NULL);
2376 return EXIT_SUCCESS;
2377 LTM_ERR:
2378 free(buf);
2379 mp_clear_multi(&a, &b, &c, NULL);
2380 return EXIT_FAILURE;
2381 }
2382
2383 static int test_mp_pack_unpack(void)
2384 {
2385 mp_int a, b;
2386 int err;
2387 size_t written, count;
2388 unsigned char *buf = NULL;
2389
2390 mp_order order = MP_LSB_FIRST;
2391 mp_endian endianess = MP_NATIVE_ENDIAN;
2392
2393 if ((err = mp_init_multi(&a, &b, NULL)) != MP_OKAY) goto LTM_ERR;
2394 if ((err = mp_rand(&a, 15)) != MP_OKAY) goto LTM_ERR;
2395
2396 count = mp_pack_count(&a, 0, 1);
2397
2398 buf = malloc(count);
2399 if (buf == NULL) {
2400 fprintf(stderr, "test_pack_unpack failed to allocate\n");
2401 goto LTM_ERR;
2402 }
2403
2404 if ((err = mp_pack((void *)buf, count, &written, order, 1,
2405 endianess, 0, &a)) != MP_OKAY) goto LTM_ERR;
2406 if ((err = mp_unpack(&b, count, order, 1,
2407 endianess, 0, (const void *)buf)) != MP_OKAY) goto LTM_ERR;
2408
2409 if (mp_cmp(&a, &b) != MP_EQ) {
2410 fprintf(stderr, "pack/unpack cycle failed\n");
2411 goto LTM_ERR;
2412 }
2413
2414 free(buf);
2415 mp_clear_multi(&a, &b, NULL);
2416 return EXIT_SUCCESS;
2417 LTM_ERR:
2418 free(buf);
2419 mp_clear_multi(&a, &b, NULL);
2420 return EXIT_FAILURE;
2421 }
2422
2423 static int unit_tests(int argc, char **argv)
2424 {
2425 static const struct {
2426 const char *name;
2427 int (*fn)(void);
2428 } test[] = {
2429 #define T0(n) { #n, test_##n }
2430 #define T1(n, o) { #n, MP_HAS(o) ? test_##n : NULL }
2431 #define T2(n, o1, o2) { #n, MP_HAS(o1) && MP_HAS(o2) ? test_##n : NULL }
2432 T0(feature_detection),
2433 T0(trivial_stuff),
2434 T2(mp_get_set_i32, MP_GET_I32, MP_GET_MAG_U32),
2435 T2(mp_get_set_i64, MP_GET_I64, MP_GET_MAG_U64),
2436 T1(mp_and, MP_AND),
2437 T1(mp_cnt_lsb, MP_CNT_LSB),
2438 T1(mp_complement, MP_COMPLEMENT),
2439 T1(mp_decr, MP_DECR),
2440 T1(mp_div_3, MP_DIV_3),
2441 T1(mp_dr_reduce, MP_DR_REDUCE),
2442 T2(mp_pack_unpack,MP_PACK, MP_UNPACK),
2443 T2(mp_fread_fwrite, MP_FREAD, MP_FWRITE),
2444 T1(mp_get_u32, MP_GET_I32),
2445 T1(mp_get_u64, MP_GET_I64),
2446 T1(mp_get_ul, MP_GET_L),
2447 T1(mp_log_u32, MP_LOG_U32),
2448 T1(mp_incr, MP_INCR),
2449 T1(mp_invmod, MP_INVMOD),
2450 T1(mp_is_square, MP_IS_SQUARE),
2451 T1(mp_kronecker, MP_KRONECKER),
2452 T1(mp_montgomery_reduce, MP_MONTGOMERY_REDUCE),
2453 T1(mp_root_u32, MP_ROOT_U32),
2454 T1(mp_or, MP_OR),
2455 T1(mp_prime_is_prime, MP_PRIME_IS_PRIME),
2456 T1(mp_prime_next_prime, MP_PRIME_NEXT_PRIME),
2457 T1(mp_prime_rand, MP_PRIME_RAND),
2458 T1(mp_rand, MP_RAND),
2459 T1(mp_read_radix, MP_READ_RADIX),
2460 T1(mp_read_write_ubin, MP_TO_UBIN),
2461 T1(mp_read_write_sbin, MP_TO_SBIN),
2462 T1(mp_reduce_2k, MP_REDUCE_2K),
2463 T1(mp_reduce_2k_l, MP_REDUCE_2K_L),
2464 #if defined(MP_HAS_SET_DOUBLE)
2465 T1(mp_set_double, MP_SET_DOUBLE),
2466 #endif
2467 T1(mp_signed_rsh, MP_SIGNED_RSH),
2468 T1(mp_sqrt, MP_SQRT),
2469 T1(mp_sqrtmod_prime, MP_SQRTMOD_PRIME),
2470 T1(mp_xor, MP_XOR),
2471 T1(s_mp_balance_mul, S_MP_BALANCE_MUL),
2472 T1(s_mp_karatsuba_mul, S_MP_KARATSUBA_MUL),
2473 T1(s_mp_karatsuba_sqr, S_MP_KARATSUBA_SQR),
2474 T1(s_mp_toom_mul, S_MP_TOOM_MUL),
2475 T1(s_mp_toom_sqr, S_MP_TOOM_SQR)
2476 #undef T2
2477 #undef T1
2478 };
2479 unsigned long i, ok, fail, nop;
2480 uint64_t t;
2481 int j;
2482
2483 ok = fail = nop = 0;
2484
2485 t = (uint64_t)time(NULL);
2486 printf("SEED: 0x%"PRIx64"\n\n", t);
2487 s_mp_rand_jenkins_init(t);
2488 mp_rand_source(s_mp_rand_jenkins);
2489
2490 for (i = 0; i < sizeof(test) / sizeof(test[0]); ++i) {
2491 if (argc > 1) {
2492 for (j = 1; j < argc; ++j) {
2493 if (strstr(test[i].name, argv[j]) != NULL) {
2494 break;
2495 }
2496 }
2497 if (j == argc) continue;
2498 }
2499 printf("TEST %s\n\n", test[i].name);
2500 if (test[i].fn == NULL) {
2501 nop++;
2502 printf("NOP %s\n\n", test[i].name);
2503 } else if (test[i].fn() == EXIT_SUCCESS) {
2504 ok++;
2505 printf("\n\n");
2506 } else {
2507 fail++;
2508 printf("\n\nFAIL %s\n\n", test[i].name);
2509 }
2510 }
2511 printf("Tests OK/NOP/FAIL: %lu/%lu/%lu\n", ok, nop, fail);
2512
2513 if (fail != 0) return EXIT_FAILURE;
2514 else return EXIT_SUCCESS;
2515 }
2516
2517 int main(int argc, char **argv)
2518 {
2519 print_header();
2520
2521 return unit_tests(argc, argv);
2522 }
2523