Jacobi symbol: Difference between revisions
Content added Content deleted
(Creating task (Legendre symbol description from Tonelli-Shanks algorithm)) |
(Add Factor) |
||
Line 9: | Line 9: | ||
;Task: |
;Task: |
||
Calculate the Jacobi symbol (a | n). |
Calculate the Jacobi symbol (a | n). |
||
=={{header|Factor}}== |
|||
The <code>jacobi</code> word already exists in the <code>math.extras</code> vocabulary. See the implementation [https://docs.factorcode.org/content/word-jacobi%2Cmath.extras.html here]. |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 15:28, 7 January 2020
Jacobi symbol is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
The Jacobi symbol is a multiplicative function that generalizes the Legendre symbol. Specifically, the Jacobi symbol (a | n) equals the product of the Legendre symbols (a | p_i)^(k_i), where n = p_1^(k_1)*p_2^(k_2)*...*p_i^(k_i) and the Legendre symbol (a | p) denotes the value of a ^ ((p-1)/2) (mod p)
- (a | p) ≡ 1 if a is a square (mod p)
- (a | p) ≡ -1 if a is not a square (mod p)
- (a | p) ≡ 0 if a ≡ 0
If n is prime, then the Jacobi symbol (a | n) equals the Legendre symbol (a | n).
- Task
Calculate the Jacobi symbol (a | n).
Factor
The jacobi
word already exists in the math.extras
vocabulary. See the implementation here.
Python
<lang python>def jacobi(a, n):
a %= n result = 1 while a != 0: while a % 2 == 0: a /= 2 n_mod_8 = n % 8 if n_mod_8 in (3, 5): result = -result a, n = n, a if a % 4 == 3 and n % 4 == 3: result = -result a %= n if n == 1: return result else: return 0</lang>