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