Computing Jacobi symbols

We use the function jacobi to compute the Jacobi symbols for the given numbers.

In [1]:
from algorithms.modular import jacobi
In [3]:
jacobi(7411, 9283, trace=True)
7411 9283 1
	9283 mod 8 = 3
	7411 mod 4 = 3
	9283 mod 4 = 3
9283 7411 -1
1872 7411 -1
	7411 mod 8 = 3
936 7411 1
468 7411 -1
234 7411 1
117 7411 -1
	117 mod 4 = 1
	7411 mod 4 = 3
7411 117 -1
40 117 -1
	117 mod 8 = 5
20 117 1
10 117 -1
5 117 1
	5 mod 4 = 1
	117 mod 4 = 1
117 5 1
2 5 1
	5 mod 8 = 5
1 5 -1
Out[3]:
-1
In [4]:
jacobi(20964, 1987, trace=True)
1094 1987 1
	1987 mod 8 = 3
547 1987 -1
	547 mod 4 = 3
	1987 mod 4 = 3
1987 547 1
346 547 1
	547 mod 8 = 3
173 547 -1
	173 mod 4 = 1
	547 mod 4 = 3
547 173 -1
28 173 -1
	173 mod 8 = 5
14 173 1
7 173 -1
	7 mod 4 = 3
	173 mod 4 = 1
173 7 -1
5 7 -1
	7 mod 8 = 7
	5 mod 4 = 1
	7 mod 4 = 3
7 5 -1
2 5 -1
	5 mod 8 = 5
1 5 1
Out[4]:
1
In [5]:
jacobi(1234567, 11111111, trace=True)
1234567 11111111 1
	11111111 mod 8 = 7
	1234567 mod 4 = 3
	11111111 mod 4 = 3
11111111 1234567 -1
8 1234567 -1
	1234567 mod 8 = 7
4 1234567 -1
2 1234567 -1
1 1234567 -1
Out[5]:
-1