In number theory, an odd integer n is called an EulerâJacobi probable prime (or, more commonly, an Euler probable prime) to base a, if a and n are coprime, and
where is the Jacobi symbol.
If n is an odd composite integer that satisfies the above congruence, then n is called an EulerâJacobi pseudoprime (or, more commonly, an Euler pseudoprime) to base a.
The motivation for this definition is the fact that all prime numbers n satisfy the above equation, as explained in the Euler's criterion article. The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are over twice as strong as tests based on Fermat's little theorem.
Every EulerâJacobi pseudoprime is also a Fermat pseudoprime and an Euler pseudoprime. There are no numbers which are EulerâJacobi pseudoprimes to all bases as Carmichael numbers are. Solovay and Strassen showed that for every composite n, for at least n/2 bases less than n, n is not an EulerâJacobi pseudoprime. [1]
The smallest EulerâJacobi pseudoprime base 2 is 561. There are 11347 EulerâJacobi pseudoprimes base 2 that are less than 25·109 (see OEIS: A047713) (page 1005 of [2]).
In the literature (for example, [2]), an EulerâJacobi pseudoprime as defined above is often called simply an Euler pseudoprime.
function EulerJacobiTest(k) a = 2 if k == 1 then return false elseif k == 2 then return true else if( modPow(a,(k-1)/2,k) == Jacobi(a,k)) then return true else return false end end end
In number theory, an odd integer n is called an EulerâJacobi probable prime (or, more commonly, an Euler probable prime) to base a, if a and n are coprime, and
where is the Jacobi symbol.
If n is an odd composite integer that satisfies the above congruence, then n is called an EulerâJacobi pseudoprime (or, more commonly, an Euler pseudoprime) to base a.
The motivation for this definition is the fact that all prime numbers n satisfy the above equation, as explained in the Euler's criterion article. The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are over twice as strong as tests based on Fermat's little theorem.
Every EulerâJacobi pseudoprime is also a Fermat pseudoprime and an Euler pseudoprime. There are no numbers which are EulerâJacobi pseudoprimes to all bases as Carmichael numbers are. Solovay and Strassen showed that for every composite n, for at least n/2 bases less than n, n is not an EulerâJacobi pseudoprime. [1]
The smallest EulerâJacobi pseudoprime base 2 is 561. There are 11347 EulerâJacobi pseudoprimes base 2 that are less than 25·109 (see OEIS: A047713) (page 1005 of [2]).
In the literature (for example, [2]), an EulerâJacobi pseudoprime as defined above is often called simply an Euler pseudoprime.
function EulerJacobiTest(k) a = 2 if k == 1 then return false elseif k == 2 then return true else if( modPow(a,(k-1)/2,k) == Jacobi(a,k)) then return true else return false end end end