1*7dd7cddfSDavid du Colombier #include <u.h>
2*7dd7cddfSDavid du Colombier #include <libc.h>
3*7dd7cddfSDavid du Colombier #include <mp.h>
4*7dd7cddfSDavid du Colombier #include <libsec.h>
5*7dd7cddfSDavid du Colombier
6*7dd7cddfSDavid du Colombier char *sfactors[] =
7*7dd7cddfSDavid du Colombier { "3", "5", "17", "257", "641", "65537", "274177", "2424833", "6700417", "45592577",
8*7dd7cddfSDavid du Colombier "6487031809", "67280421310721", "1238926361552897", "59649589127497217",
9*7dd7cddfSDavid du Colombier "5704689200685129054721", "4659775785220018543264560743076778192897",
10*7dd7cddfSDavid du Colombier "7455602825647884208337395736200454918783366342657",
11*7dd7cddfSDavid du Colombier "93461639715357977769163558199606896584051237541638188580280321",
12*7dd7cddfSDavid du Colombier
13*7dd7cddfSDavid du Colombier "741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737",
14*7dd7cddfSDavid du Colombier
15*7dd7cddfSDavid du Colombier "130439874405488189727484768796509903946608530841611892186895295776832416251471863574140227977573104895898783928842923844831149032913798729088601617946094119449010595906710130531906171018354491609619193912488538116080712299672322806217820753127014424577"
16*7dd7cddfSDavid du Colombier };
17*7dd7cddfSDavid du Colombier
18*7dd7cddfSDavid du Colombier long start;
19*7dd7cddfSDavid du Colombier
20*7dd7cddfSDavid du Colombier void
printmp(mpint * b,char * tag)21*7dd7cddfSDavid du Colombier printmp(mpint *b, char *tag)
22*7dd7cddfSDavid du Colombier {
23*7dd7cddfSDavid du Colombier int n;
24*7dd7cddfSDavid du Colombier char *p;
25*7dd7cddfSDavid du Colombier
26*7dd7cddfSDavid du Colombier print("%s (%d) ", tag, b->top);
27*7dd7cddfSDavid du Colombier p = mptoa(b, 10, nil, 0);
28*7dd7cddfSDavid du Colombier write(1, p, strlen(p));
29*7dd7cddfSDavid du Colombier free(p);
30*7dd7cddfSDavid du Colombier print("\n");
31*7dd7cddfSDavid du Colombier }
32*7dd7cddfSDavid du Colombier
33*7dd7cddfSDavid du Colombier int
timing(void)34*7dd7cddfSDavid du Colombier timing(void)
35*7dd7cddfSDavid du Colombier {
36*7dd7cddfSDavid du Colombier long now, span;
37*7dd7cddfSDavid du Colombier
38*7dd7cddfSDavid du Colombier now = time(0);
39*7dd7cddfSDavid du Colombier span = now-start;
40*7dd7cddfSDavid du Colombier start = now;
41*7dd7cddfSDavid du Colombier
42*7dd7cddfSDavid du Colombier return span;
43*7dd7cddfSDavid du Colombier }
44*7dd7cddfSDavid du Colombier
45*7dd7cddfSDavid du Colombier int expdebug;
46*7dd7cddfSDavid du Colombier
47*7dd7cddfSDavid du Colombier
48*7dd7cddfSDavid du Colombier void
main(int argc,char ** argv)49*7dd7cddfSDavid du Colombier main(int argc, char **argv)
50*7dd7cddfSDavid du Colombier {
51*7dd7cddfSDavid du Colombier mpint *p, *k, *d, *b, *e, *x, *r;
52*7dd7cddfSDavid du Colombier int i;
53*7dd7cddfSDavid du Colombier
54*7dd7cddfSDavid du Colombier start = time(0);
55*7dd7cddfSDavid du Colombier fmtinstall('B', mpconv);
56*7dd7cddfSDavid du Colombier mpsetminbits(2*Dbits);
57*7dd7cddfSDavid du Colombier
58*7dd7cddfSDavid du Colombier x = mpnew(0);
59*7dd7cddfSDavid du Colombier e = mpnew(0);
60*7dd7cddfSDavid du Colombier r = mpnew(0);
61*7dd7cddfSDavid du Colombier p = mpnew(0);
62*7dd7cddfSDavid du Colombier
63*7dd7cddfSDavid du Colombier // b = 2^32
64*7dd7cddfSDavid du Colombier b = mpcopy(mpone);
65*7dd7cddfSDavid du Colombier mpleft(b, 32, b);
66*7dd7cddfSDavid du Colombier
67*7dd7cddfSDavid du Colombier // 2^29440
68*7dd7cddfSDavid du Colombier p = mpcopy(mpone);
69*7dd7cddfSDavid du Colombier mpleft(p, 29440, p);
70*7dd7cddfSDavid du Colombier // 2^27392
71*7dd7cddfSDavid du Colombier k = mpcopy(mpone);
72*7dd7cddfSDavid du Colombier mpleft(k, 27392, k);
73*7dd7cddfSDavid du Colombier // k = 2^29440 - 2^27392
74*7dd7cddfSDavid du Colombier mpsub(p, k, k);
75*7dd7cddfSDavid du Colombier // p = 2^29440 - 2^27392 + 1
76*7dd7cddfSDavid du Colombier mpadd(k, mpone, p);
77*7dd7cddfSDavid du Colombier
78*7dd7cddfSDavid du Colombier // if(!probably_prime(p, 18)){
79*7dd7cddfSDavid du Colombier // print("not a prime\n");
80*7dd7cddfSDavid du Colombier // exits(0);
81*7dd7cddfSDavid du Colombier // }
82*7dd7cddfSDavid du Colombier // print("probably prime\n");
83*7dd7cddfSDavid du Colombier
84*7dd7cddfSDavid du Colombier mpright(k, 10, k);
85*7dd7cddfSDavid du Colombier printmp(k, "k =");
86*7dd7cddfSDavid du Colombier
87*7dd7cddfSDavid du Colombier expdebug = 1;
88*7dd7cddfSDavid du Colombier mpexp(b, k, p, x);
89*7dd7cddfSDavid du Colombier printmp(x, "x =");
90*7dd7cddfSDavid du Colombier print("timing %d\n", timing());
91*7dd7cddfSDavid du Colombier
92*7dd7cddfSDavid du Colombier for(i = 0; i < nelem(sfactors); i++){
93*7dd7cddfSDavid du Colombier d = strtomp(sfactors[i], nil, 10, nil);
94*7dd7cddfSDavid du Colombier // e = k/d
95*7dd7cddfSDavid du Colombier mpdiv(k, d, e, r);
96*7dd7cddfSDavid du Colombier printmp(r, "r =");
97*7dd7cddfSDavid du Colombier
98*7dd7cddfSDavid du Colombier // x = b^e mod p
99*7dd7cddfSDavid du Colombier mpexp(b, e, p, x);
100*7dd7cddfSDavid du Colombier printmp(x, "x =");
101*7dd7cddfSDavid du Colombier print("timing %d\n", timing());
102*7dd7cddfSDavid du Colombier }
103*7dd7cddfSDavid du Colombier }
104