1 /* $NetBSD: 2kprime.c,v 1.1.1.1 2011/04/13 18:15:06 elric Exp $ */ 2 3 /* Makes safe primes of a 2k nature */ 4 #include <tommath.h> 5 #include <time.h> 6 7 int sizes[] = {256, 512, 768, 1024, 1536, 2048, 3072, 4096}; 8 9 int main(void) 10 { 11 char buf[2000]; 12 int x, y; 13 mp_int q, p; 14 FILE *out; 15 clock_t t1; 16 mp_digit z; 17 18 mp_init_multi(&q, &p, NULL); 19 20 out = fopen("2kprime.1", "w"); 21 for (x = 0; x < (int)(sizeof(sizes) / sizeof(sizes[0])); x++) { 22 top: 23 mp_2expt(&q, sizes[x]); 24 mp_add_d(&q, 3, &q); 25 z = -3; 26 27 t1 = clock(); 28 for(;;) { 29 mp_sub_d(&q, 4, &q); 30 z += 4; 31 32 if (z > MP_MASK) { 33 printf("No primes of size %d found\n", sizes[x]); 34 break; 35 } 36 37 if (clock() - t1 > CLOCKS_PER_SEC) { 38 printf("."); fflush(stdout); 39 // sleep((clock() - t1 + CLOCKS_PER_SEC/2)/CLOCKS_PER_SEC); 40 t1 = clock(); 41 } 42 43 /* quick test on q */ 44 mp_prime_is_prime(&q, 1, &y); 45 if (y == 0) { 46 continue; 47 } 48 49 /* find (q-1)/2 */ 50 mp_sub_d(&q, 1, &p); 51 mp_div_2(&p, &p); 52 mp_prime_is_prime(&p, 3, &y); 53 if (y == 0) { 54 continue; 55 } 56 57 /* test on q */ 58 mp_prime_is_prime(&q, 3, &y); 59 if (y == 0) { 60 continue; 61 } 62 63 break; 64 } 65 66 if (y == 0) { 67 ++sizes[x]; 68 goto top; 69 } 70 71 mp_toradix(&q, buf, 10); 72 printf("\n\n%d-bits (k = %lu) = %s\n", sizes[x], z, buf); 73 fprintf(out, "%d-bits (k = %lu) = %s\n", sizes[x], z, buf); fflush(out); 74 } 75 76 return 0; 77 } 78 79 80 81 82 83 84 /* Source: /cvs/libtom/libtommath/etc/2kprime.c,v */ 85 /* Revision: 1.2 */ 86 /* Date: 2005/05/05 14:38:47 */ 87