tests/test_nt_jacobi.cc

   1 #include "test_nt.h"
   2
   3 int test_nt_jacobi (int iterations)
   4 {
   5         int error = 0;
   6         int i;
   7         // Check special cases.
   8         for (i = iterations; i > 0; i--) {
   9                 cl_I b = 1+2*abs(testrandom_I());
  10                 cl_I c = testrandom_I();
  11                 if (b==1) {
  12                         ASSERT2(jacobi(b*c,b) == 1, b,c);
  13                 } else {
  14                         ASSERT2(jacobi(b*c,b) == 0, b,c);
  15                 }
  16         }
  17         for (i = iterations; i > 0; i--) {
  18                 cl_I b = 1+2*abs(testrandom_I());
  19                 if (mod(b,4)==1) {
  20                         ASSERT1(jacobi(-1,b) == 1, b);
  21                 } else {
  22                         ASSERT1(jacobi(-1,b) == -1, b);
  23                 }
  24                 if (abs(mod(b,8)-4)==1) {
  25                         ASSERT1(jacobi(2,b) == -1, b);
  26                 } else {
  27                         ASSERT1(jacobi(2,b) == 1, b);
  28                 }
  29         }
  30         // Check quadratic residues.
  31         for (i = iterations; i > 0; i--) {
  32                 cl_I b = 1+2*abs(testrandom_I());
  33                 cl_I c = testrandom_I();
  34                 cl_I a = mod(square(c),b);
  35                 if (gcd(a,b)==1) {
  36                         ASSERT2(jacobi(a,b) == 1, b,c);
  37                 } else {
  38                         ASSERT2(jacobi(a,b) == 0, b,c);
  39                 }
  40         }
  41         // Check homomorphism (fixed b).
  42         for (i = iterations; i > 0; i--) {
  43                 cl_I b = 1+2*abs(testrandom_I());
  44                 cl_I a1 = testrandom_I();
  45                 cl_I a2 = testrandom_I();
  46                 ASSERT3(jacobi(a1,b)*jacobi(a2,b) == jacobi(a1*a2,b), b,a1,a2);
  47         }
  48         // Check homomorphism (fixed a).
  49         for (i = iterations; i > 0; i--) {
  50                 cl_I a = testrandom_I();
  51                 cl_I b1 = 1+2*abs(testrandom_I());
  52                 cl_I b2 = 1+2*abs(testrandom_I());
  53                 ASSERT3(jacobi(a,b1)*jacobi(a,b2) == jacobi(a,b1*b2), a,b1,b2);
  54         }
  55         return error;
  56 }