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