jacobiSymbol
Syntax
Description
returns the value of the Jacobi symbol for
integer J
= jacobiSymbol(a
,n
)a
and positive odd integer n
.
Examples
Periodicity of Jacobi Symbol
Find the Jacobi symbol for and .
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 if .
Completely Multiplicative Property of Jacobi Symbol
Find the Jacobi symbol for and .
J = jacobiSymbol(28,9)
J = 1
The Jacobi symbol is a completely multiplicative function, where the Jacobi symbol satisfies the relation for . Show that the Jacobi symbol follows this relation for .
Ja = jacobiSymbol(2,9)*jacobiSymbol(2,9)*jacobiSymbol(7,9)
Ja = 1
The Jacobi symbol also satisfies the relation for . Show that the Jacobi symbol follows this relation for .
Jb = jacobiSymbol(28,3)*jacobiSymbol(28,3)
Jb = 1
Primality Test Using Jacobi Symbol
You can use the Jacobi symbol for the Solovay–Strassen primality test. If an odd integer is prime, then the congruence
must hold for all integers . If there is an integer in such that the congruence relation is not satisfied, then is not prime.
Check if is prime or not. Choose 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 is not prime since it does not satisfy the congruence relation for .
checkPrime = mod(J,n) == m
checkPrime = logical
0
Next, check if is prime or not. Choose and perform the primality test.
n = 557; a = 19; J = jacobiSymbol(a,n); m = powermod(a,(n-1)/2,n);
The integer is probably prime since it satisfies the congruence relation for .
checkPrime = mod(J,n) == m
checkPrime = logical
1
Perform the primality test for all in to confirm that the integer 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 is defined as the product of the Legendre symbols
for an integer a and a positive odd integer n with prime factorization
The Legendre symbol for an integer a and an odd prime p is defined as
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.
Version History
Introduced in R2020a
MATLAB Command
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)