annotate etc/2kprime.c @ 203:e109027b9edf libtommath LTM_DB_0.46 LTM_DB_0.47

Don't remove ~ files on make clean (and find -type was wrong anyway)
author Matt Johnston <matt@ucc.asn.au>
date Wed, 11 May 2005 16:27:28 +0000
parents 22d5cf7d4b1a
children 97db060d0ef5
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 /* Makes safe primes of a 2k nature */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 #include <tommath.h>
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 #include <time.h>
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 int sizes[] = {256, 512, 768, 1024, 1536, 2048, 3072, 4096};
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 int main(void)
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 char buf[2000];
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 int x, y;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 mp_int q, p;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12 FILE *out;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 clock_t t1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 mp_digit z;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16 mp_init_multi(&q, &p, NULL);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 out = fopen("2kprime.1", "w");
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 for (x = 0; x < (int)(sizeof(sizes) / sizeof(sizes[0])); x++) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 top:
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 mp_2expt(&q, sizes[x]);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 mp_add_d(&q, 3, &q);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23 z = -3;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25 t1 = clock();
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26 for(;;) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 mp_sub_d(&q, 4, &q);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28 z += 4;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30 if (z > MP_MASK) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31 printf("No primes of size %d found\n", sizes[x]);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 break;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35 if (clock() - t1 > CLOCKS_PER_SEC) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36 printf("."); fflush(stdout);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37 // sleep((clock() - t1 + CLOCKS_PER_SEC/2)/CLOCKS_PER_SEC);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38 t1 = clock();
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41 /* quick test on q */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42 mp_prime_is_prime(&q, 1, &y);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
43 if (y == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
44 continue;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
46
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47 /* find (q-1)/2 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48 mp_sub_d(&q, 1, &p);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 mp_div_2(&p, &p);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50 mp_prime_is_prime(&p, 3, &y);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 if (y == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 continue;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
53 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
54
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55 /* test on q */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
56 mp_prime_is_prime(&q, 3, &y);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
57 if (y == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
58 continue;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
59 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
60
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
61 break;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
62 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
63
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64 if (y == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
65 ++sizes[x];
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
66 goto top;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
67 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
68
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
69 mp_toradix(&q, buf, 10);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
70 printf("\n\n%d-bits (k = %lu) = %s\n", sizes[x], z, buf);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
71 fprintf(out, "%d-bits (k = %lu) = %s\n", sizes[x], z, buf); fflush(out);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
72 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
73
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
74 return 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
75 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
77
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
80