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