jacobiSymbol

Jacobi symbol

Syntax

J = jacobiSymbol(a,n)

Description

J = jacobiSymbol(a,n) returns the value of the Jacobi symbol for integer a and positive odd integer n.

Examples

Periodicity of Jacobi Symbol

Find the Jacobi symbol for $$a=1,2,\dots ,9$$ and $$n=3$$.

a = 1:9;
n = 3;
J = jacobiSymbol(a,n)

J = 1×9

     1    -1     0     1    -1     0     1    -1     0

The Jacobi symbol is periodic with respect to its first argument, where $$\left(\frac{a}{n}\right)=\left(\frac{b}{n}\right)$$ if $$a\equiv b(modn)$$.

Completely Multiplicative Property of Jacobi Symbol

Find the Jacobi symbol for $$a=28$$ and $$n=9$$.

J = jacobiSymbol(28,9)

J = 1

The Jacobi symbol is a completely multiplicative function, where the Jacobi symbol satisfies the relation $$\left(\frac{a}{n}\right)=\left(\frac{a_1}{n}\right)\times \left(\frac{a_2}{n}\right)\times \dots \left(\frac{a_r}{n}\right)$$ for $$a=a_1\times a_2\times \dots a_r$$. Show that the Jacobi symbol follows this relation for $$a=28=2\times 2\times 7$$.

Ja = jacobiSymbol(2,9)*jacobiSymbol(2,9)*jacobiSymbol(7,9)

Ja = 1

The Jacobi symbol also satisfies the relation $$\left(\frac{a}{n}\right)=\left(\frac{a}{n_1}\right)\times \left(\frac{a}{n_2}\right)\times \dots \left(\frac{a}{n_r}\right)$$ for $$n=n_1\times n_2\times \dots n_r$$. Show that the Jacobi symbol follows this relation for $$n=9=3\times 3$$.

Jb = jacobiSymbol(28,3)*jacobiSymbol(28,3)

Jb = 1

Primality Test Using Jacobi Symbol

You can use the Jacobi symbol $$\left(\frac{a}{n}\right)$$ for the Solovay–Strassen primality test. If an odd integer $$n>1$$ is prime, then the congruence

$$\left(\frac{a}{n}\right)\equiv a^{(n-1)/2}(modn)$$

must hold for all integers $$a$$. If there is an integer $$a$$ in $$\{1,2,\dots ,n-1\}$$ such that the congruence relation is not satisfied, then $$n$$ is not prime.

Check if $$n=561$$ is prime or not. Choose $$a=19$$ and perform the primality test. Compare the two values in the congruence relation.

First calculate the left side of the congruence relation using the Jacobi symbol.

n = 561;
a = 14;
J = jacobiSymbol(a,n)

J = 1

Calculate the right side of the congruence relation.

m = powermod(a,(n-1)/2,n)

m = 67

The integer $$n=561$$ is not prime since it does not satisfy the congruence relation for $$a=19$$.

checkPrime = mod(J,n) == m

checkPrime = logical
   0

Next, check if $$n=557$$ is prime or not. Choose $$a=19$$ and perform the primality test.

n = 557;
a = 19;
J = jacobiSymbol(a,n);
m = powermod(a,(n-1)/2,n);

The integer $$n=557$$ is probably prime since it satisfies the congruence relation for $$a=19$$.

checkPrime = mod(J,n) == m

checkPrime = logical
   1

Perform the primality test for all $$a$$ in $$\{1,2,\dots ,556\}$$ to confirm that the integer $$n=557$$ is indeed prime.

a = 1:n-1;
J = jacobiSymbol(a,n);
m = powermod(a,(n-1)/2,n);
checkPrime = all(mod(J,n) == m)

checkPrime = logical
   1

Verify the result with isprime.

isprime(n)

ans = logical
   1

Input Arguments

a — Input

number | vector | matrix | array | symbolic number | symbolic array

Input, specified as a number, vector, matrix, array, symbolic number, or symbolic array. The elements of a must be integers. a and n must be the same size, or else one of them must be a scalar.

Data Types: single | double | sym

n — Input

number | vector | matrix | array | symbolic number | symbolic array

Input, specified as a number, vector, matrix, array, symbolic number, or symbolic array. The elements of n must be positive odd integers. a and n must be the same size, or else one of them must be a scalar.

Data Types: single | double | sym

Output Arguments

J — Output value

–1 | 0 | 1

Output value, returned as –1, 0, or 1.

Data Types: single | double | sym

More About

Jacobi Symbol

The Jacobi symbol $$\left(\frac{a}{n}\right)$$ is defined as the product of the Legendre symbols

$$\left(\frac{a}{n}\right)={\left(\frac{a}{p_1}\right)}^{k_1}{\left(\frac{a}{p_2}\right)}^{k_2}\dots {\left(\frac{a}{p_r}\right)}^{k_r}$$

for an integer a and a positive odd integer n with prime factorization

$$n=p_1^{k_1}{p}_2^{k_2}\dots p_r^{k_r}.$$

The Legendre symbol $$\left(\frac{a}{p}\right)$$ for an integer a and an odd prime p is defined as

$$\left(\frac{a}{p}\right)=\{\begin{array}{ll}0\hfill & \text{if }a\equiv \text{0 (mod }p)\hfill \\ 1\hfill & \text{if }a\text{ is a quadratic residue modulo }p\text{ or }{x}^2\equiv a\text{ (mod }p)\text{ has a nonzero solution for }x\hfill \\ -1\hfill & \text{if }a\text{ is a quadratic nonresidue modulo }p\text{ or }{x}^2\equiv a\text{ (mod }p)\text{ has no solutions for }x\text{.}\hfill \end{array}$$

When n is an odd prime, the Jacobi symbol is equal to the Legendre symbol.

References

[1] Dietzfelbinger, M. Primality Testing in Polynomial Time: From Randomized Algorithms to "PRIMES Is in P". Springer, 2004.