ref: e4509d40cc9759baddf1c2571247b95d2f5b61a5
dir: /sys/src/libmp/bigtest.c/
#include <u.h> #include <libc.h> #include <mp.h> char *sfactors[] = { "3", "5", "17", "257", "641", "65537", "274177", "2424833", "6700417", "45592577", "6487031809", "67280421310721", "1238926361552897", "59649589127497217", "5704689200685129054721", "4659775785220018543264560743076778192897", "7455602825647884208337395736200454918783366342657", "93461639715357977769163558199606896584051237541638188580280321", "741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737", "130439874405488189727484768796509903946608530841611892186895295776832416251471863574140227977573104895898783928842923844831149032913798729088601617946094119449010595906710130531906171018354491609619193912488538116080712299672322806217820753127014424577" }; long start; void printmp(mpint *b, char *tag) { int n; char *p; print("%s (%d) ", tag, b->top); p = mptoa(b, 10, nil, 0); write(1, p, strlen(p)); free(p); print("\n"); } int timing(void) { long now, span; now = time(0); span = now-start; start = now; return span; } int expdebug; void main(int argc, char **argv) { mpint *p, *k, *d, *b, *e, *x, *r; int i; start = time(0); fmtinstall('B', mpfmt); mpsetminbits(2*Dbits); x = mpnew(0); e = mpnew(0); r = mpnew(0); p = mpnew(0); // b = 2^32 b = mpcopy(mpone); mpleft(b, 32, b); // 2^29440 p = mpcopy(mpone); mpleft(p, 29440, p); // 2^27392 k = mpcopy(mpone); mpleft(k, 27392, k); // k = 2^29440 - 2^27392 mpsub(p, k, k); // p = 2^29440 - 2^27392 + 1 mpadd(k, mpone, p); // if(!probably_prime(p, 18)){ // print("not a prime\n"); // exits(0); // } // print("probably prime\n"); mpright(k, 10, k); printmp(k, "k ="); expdebug = 1; mpexp(b, k, p, x); printmp(x, "x ="); print("timing %d\n", timing()); for(i = 0; i < nelem(sfactors); i++){ d = strtomp(sfactors[i], nil, 10, nil); // e = k/d mpdiv(k, d, e, r); printmp(r, "r ="); // x = b^e mod p mpexp(b, e, p, x); printmp(x, "x ="); print("timing %d\n", timing()); } }