Euler–Jacobi Pseudoprime
   HOME

TheInfoList



OR:

In
number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, an odd
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
''n'' is called an Euler–Jacobi probable prime (or, more commonly, an Euler probable prime) to base ''a'', if ''a'' and ''n'' are
coprime In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
, and :a^ \equiv \left(\frac\right)\pmod where \left(\frac\right) is the
Jacobi symbol Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
. The Jacobi symbol evaluates to 0 if ''a'' and ''n'' are not coprime, so the test can alternatively be expressed as: :a^ \equiv \left(\frac\right) \neq 0 \pmod. If ''n'' is an odd
composite Composite or compositing may refer to: Materials * Composite material, a material that is made from several different substances ** Metal matrix composite, composed of metal and other parts ** Cermet, a composite of ceramic and metallic material ...
integer that satisfies the above congruence, then ''n'' is called an Euler–Jacobi pseudoprime (or, more commonly, an Euler pseudoprime) to base ''a''. As long as ''a'' is not a multiple of ''n'' (usually 2 ≤ ''a'' < ''n''), then if ''a'' and ''n'' are not coprime, ''n'' is definitely composite, as 1 < gcd(''a'',''n'') < ''n'' is a factor of ''n''.


Properties

The motivation for this definition is the fact that all
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s ''n'' satisfy the above equation, as explained in the
Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely, Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then : a^ \equiv \begin \;\;\,1\pmod& \text ...
article. The equation can be tested rather quickly, which can be used for probabilistic
primality testing A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating wheth ...
. These tests are over twice as strong as tests based on
Fermat's little theorem In number theory, Fermat's little theorem states that if is a prime number, then for any integer , the number is an integer multiple of . In the notation of modular arithmetic, this is expressed as a^p \equiv a \pmod p. For example, if and , t ...
. 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 number In number theory, a Carmichael number is a composite number which in modular arithmetic satisfies the congruence relation: : b^n\equiv b\pmod for all integers . The relation may also be expressed in the form: : b^\equiv 1\pmod for all integers b ...
s 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. The smallest Euler–Jacobi pseudoprime base 2 is 561. There are 11347 Euler–Jacobi pseudoprimes base 2 that are less than 25·109 (see ) (page 1005 of ). In the literature (for example,), an Euler–Jacobi pseudoprime as defined above is often called simply an Euler pseudoprime.


Implementation in Lua

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


See also

*
Probable prime In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific co ...


References

{{DEFAULTSORT:Euler-Jacobi Pseudoprime Pseudoprimes