jacobiSymbol

Description

example

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

Examples

collapse all

Find the Jacobi symbol for a=1,2,,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 (an)=(bn) if ab(modn).

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 (an)=(a1n)×(a2n)×(arn) for a=a1×a2×ar. Show that the Jacobi symbol follows this relation for a=28=2×2×7.

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

The Jacobi symbol also satisfies the relation (an)=(an1)×(an2)×(anr) for n=n1×n2×nr. Show that the Jacobi symbol follows this relation for n=9=3×3.

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

You can use the Jacobi symbol (an) for the Solovay–Strassen primality test. If an odd integer n>1 is prime, then the congruence

(an)a(n-1)/2(modn)

must hold for all integers a. If there is an integer a in {1,2,,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,,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

collapse all

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

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

collapse all

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

Data Types: single | double | sym

More About

collapse all

Jacobi Symbol

The Jacobi symbol (an) is defined as the product of the Legendre symbols

(an)=(ap1)k1(ap2)k2(apr)kr

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

n=p1k1p2k2prkr.

The Legendre symbol (ap) for an integer a and an odd prime p is defined as

(ap)={0if a0 (mod p)1if a is a quadratic residue modulo p or x2a (mod p) has a nonzero solution for x1if a is a quadratic nonresidue modulo p or x2a (mod p) has no solutions for x.

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.

See Also

| |

Introduced in R2020a