tests/timesqrtmodp.cc

   1 #include <cln/number.h>
   2 #include <cln/io.h>
   3 #include <cln/integer.h>
   4 #include <cln/integer_io.h>
   5 #include <cln/modinteger.h>
   6 #include <cln/numtheory.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9 #include <cln/timing.h>
  10
  11 int main (int argc, char * argv[])
  12 {
  13         int repetitions = 1;
  14         if ((argc >= 3) && !strcmp(argv[1],"-r")) {
  15                 repetitions = atoi(argv[2]);
  16                 argc -= 2; argv += 2;
  17         }
  18         if (argc < 2)
  19                 exit(1);
  20         cl_I len = cl_I(argv[1]);
  21         int e = (argc > 2 ? atoi(argv[2]) : 0);
  22         if (e < 1)
  23                 e = 1;
  24         if (len <= e)
  25                 exit(0);
  26         cl_I p;
  27         do {
  28                 p = ((random_I((cl_I)1 << (len-1-e))*2+1) << e) + 1;
  29         } while (!isprobprime(p));
  30         cout << "p = " << p << endl;
  31         cl_modint_ring R = find_modint_ring(p);
  32         cl_MI x = R->random();
  33         cl_MI a = square(x);
  34         sqrt_mod_p_t sol;
  35 #if 0
  36         extern int cl_sqrt_algo;
  37         cl_sqrt_algo = 1;
  38         { CL_TIMING;
  39           for (int rep = repetitions; rep > 0; rep--)
  40             { sol = sqrt_mod_p(R,a); }
  41         }
  42         if (sol.condition)
  43                 cerr << "p not prime!" << endl;
  44         else {
  45                 if (sol.solutions == 0)
  46                         cerr << "No sqrt found!" << endl;
  47                 if (!(sol.solution[0] == x || sol.solution[0] == -x))
  48                         cerr << "Wrong result!" << endl;
  49         }
  50         cl_sqrt_algo = 2;
  51         { CL_TIMING;
  52           for (int rep = repetitions; rep > 0; rep--)
  53             { sol = sqrt_mod_p(R,a); }
  54         }
  55         if (sol.condition)
  56                 cerr << "p not prime!" << endl;
  57         else {
  58                 if (sol.solutions == 0)
  59                         cerr << "No sqrt found!" << endl;
  60                 if (!(sol.solution[0] == x || sol.solution[0] == -x))
  61                         cerr << "Wrong result!" << endl;
  62         }
  63         cl_sqrt_algo = 3;
  64 #endif
  65         { CL_TIMING;
  66           for (int rep = repetitions; rep > 0; rep--)
  67             { sol = sqrt_mod_p(R,a); }
  68         }
  69         if (sol.condition)
  70                 cerr << "p not prime!" << endl;
  71         else {
  72                 if (sol.solutions == 0)
  73                         cerr << "No sqrt found!" << endl;
  74                 if (!(sol.solution[0] == x || sol.solution[0] == -x))
  75                         cerr << "Wrong result!" << endl;
  76         }
  77 }