bigtest.c 2.0 KB

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