Lucas test (mathematics)

This article explains the general test of prime numbers for natural numbers n , discovered by Édouard Lucas , for which the factorization of n - 1 is known. The (independent) prime number test for Mersenne numbers can be found in the article Lucas-Lehmer test .

The Lucas test is a further development of Fermat's primality test by the mathematician Édouard Lucas . The test was improved in the 1950s by Derrick Henry Lehmer and later again by John Brillhart and John L. Selfridge . It should not be confused with the Lucas-Lehmer test for Mersenne numbers .

Fermatscher primality test

A natural number is given , for which one would like to check whether it is prime. According to the Fermat's primality test is not a prime number if the following condition for too relatively prime number with true: ${\displaystyle n>1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle 1<a<n}$

${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$

The Fermat test never provides the statement that a number is prime, but can only rule out being prime. The Fermat test does not provide any information about the Carmichael numbers .

Lucas test

In 1876, Édouard Lucas succeeded in reversing Fermat's little sentence:

(Forerunner of the Lucas test) A natural number is a prime number if and only if there is a with for that ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle 1<a<n}$

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

such as

${\displaystyle a^{m}\not \equiv 1{\pmod {n}}}$

holds for all natural numbers . ${\displaystyle m<n-1}$

This finding is difficult to apply because there are so many to test. In 1891 Lucas corrected the sentence and received the prime number test named after him: ${\displaystyle m}$

(Lucas test) A natural number is a prime number if and only if there is a with for that ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle 1<a<n}$

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

such as

${\displaystyle a^{m}\not \equiv 1{\pmod {n}}}$

holds for all real divisors of . ${\displaystyle m<n-1}$ ${\displaystyle n-1}$

Since only the divisors of have to be tested here, considerably fewer calculation steps are necessary. A disadvantage, however, is that you have to know the prime factorization of . must therefore be factored . However, this method is very efficient for numbers with a special structure, for example numbers of the form . ${\displaystyle n-1}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$ ${\displaystyle 2^{k}+1}$

If the condition of the Lucas test for a basis is not fulfilled, it does not follow that the number is composed. For that you would have to check all bases . ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle 1<a<n}$

Example:

The following applies to the number . The real dividers of are and . Further applies and . It follows that is a prime number. ${\displaystyle n=59}$ ${\displaystyle 2^{58}\equiv 1\ mod\ 59}$ ${\displaystyle n-1=58}$ ${\displaystyle 1,2}$ ${\displaystyle 29}$ ${\displaystyle 2^{1}\equiv 2\ mod\ 59,2^{2}\equiv 4\ mod\ 59}$ ${\displaystyle 2^{29}\equiv -1\ mod\ 59}$ ${\displaystyle 59}$

Extensions by Lehmer, Brillhart and Selfridge

Derrick Henry Lehmer found the improved Lucas test in 1953 . In 1967 another version ( flexible Lucas test ) was discovered by John Brillhart and John L. Selfridge .

Improved Lucas test

The improved Lucas test is based on the following property: is a prime number if and only if there is a natural number with for which
${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle 1<a<n}$

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

such as

${\displaystyle a^{\frac {n-1}{q_{i}}}\not \equiv 1{\pmod {n}}}$

for all prime factors of . ${\displaystyle q_{i}}$ ${\displaystyle n-1}$

The application of this test to Fermat numbers is called the Pépin test .

Flexible Lucas test

The flexible Lucas test is based on the following property:
The prime factorization of the natural number is given by ${\displaystyle n}$ ${\displaystyle n-1}$

${\displaystyle n-1=q_{1}^{e_{1}}\cdot \ldots \cdot q_{r}^{e_{r}}}$.

Then the following applies: is a prime number if and only if there is a natural number with for every prime factor for which ${\displaystyle n}$ ${\displaystyle q_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle 1<a_{i}<n}$

${\displaystyle a_{i}^{n-1}\equiv 1{\pmod {n}}}$

such as

${\displaystyle a_{i}^{\frac {n-1}{q_{i}}}\not \equiv 1{\pmod {n}}}$

applies.

example

We consider the prime number . The previous number has the prime divisors and . The following table shows suitable and how the conditions are met: ${\displaystyle n=911}$ ${\displaystyle n-1=910}$ ${\displaystyle q=2,5,7}$ ${\displaystyle 13}$ ${\displaystyle a}$

q	a	a n-1 ≡ 1 (mod n)	a (n-1) / q ≢ 1 (mod n)
2	7th	7 910 ≡ 1 (mod 911)	7 910/2 ≡ -1 (mod 911)
5	3	3 910 ≡ 1 (mod 911)	3 910/5 ≡ 482 (mod 911)
7th	2	2 910 ≡ 1 (mod 911)	2 910/7 ≡ 568 (mod 911)
13	2	2 910 ≡ 1 (mod 911)	2 910/13 ≡ 577 (mod 911)

Pratt prime number test

The Pratt test is an iterated Lucas test. In turn, it is checked for all prime factors of whether these are prime numbers. ${\displaystyle n-1}$

Fermat couple

${\displaystyle (a,b)}$is a Fermat pair if ${\displaystyle (a,b)=(1,2)\lor (a\geq 2\land a^{n-1}\not \equiv 1\mod n)}$

Pratt sequence

${\displaystyle (a_{1},b_{1})\dots (a_{k},b_{k})}$is a Pratt sequence if for each Fermat pair from the sequence it is true that for each prime factor of a Fermat pair is contained in the Pratt sequence and the following applies: ${\displaystyle (a,b)}$ ${\displaystyle p}$ ${\displaystyle b}$ ${\displaystyle (a',p)}$ ${\displaystyle a^{\frac {n-1}{p}}\not \equiv 1}$

For every prime number there is a Pratt sequence the length of the representation of the prime number, which is why . ${\displaystyle Prime\in NP}$

example

For the following is a possible Pratt sequence ${\displaystyle 797}$

${\displaystyle (5,797),(1,2),(6,199),(5,3),(3,11)}$

to check is now even whether , and on whether the prime divisors of true ${\displaystyle a^{b-1}\equiv 1}$ ${\displaystyle p}$ ${\displaystyle b-1}$ ${\displaystyle a^{\frac {b-1}{2}}\not \equiv }$

${\displaystyle (5,797)}$

${\displaystyle 5^{797-1}\mod 797\equiv 5^{796}\mod 797\equiv 1}$

${\displaystyle 5^{\frac {796}{2}}\mod 797\equiv 5^{398}\mod 797\equiv 796\not \equiv 1}$

${\displaystyle 5^{\frac {796}{199}}\mod 797\equiv 5^{4}\mod 797\equiv 625\not \equiv 1}$

${\displaystyle (6,199)}$

${\displaystyle 6^{199-1}\mod 199\equiv 6^{198}\mod 199\equiv 1}$

${\displaystyle 6^{\frac {198}{2}}\mod 199\equiv 6^{99}\mod 199\equiv 198\not \equiv 1}$

${\displaystyle 6^{\frac {198}{3}}\mod 199\equiv 6^{66}\mod 199\equiv 192\not \equiv 1}$

${\displaystyle 6^{\frac {198}{11}}\mod 199\equiv 6^{18}\mod 199\equiv 63\not \equiv 1}$

${\displaystyle (5,3)}$

${\displaystyle 5^{3-1}\mod 3\equiv 5^{2}\mod 3\equiv 1}$

${\displaystyle 5^{\frac {2}{2}}\mod 3\equiv 5^{1}\mod 3\equiv 2\not \equiv 1}$

${\displaystyle (2,5)}$

${\displaystyle 2^{5-1}\mod 5\equiv 2^{4}\mod 5\equiv 1}$

${\displaystyle 2^{\frac {2}{2}}\mod 5\equiv 2^{1}\mod 5\equiv 2\not \equiv 1}$

literature

• Paulo Ribenboim : The world of prime numbers. Secrets and Records. Springer, Berlin et al. 2006, ISBN 3-540-34283-4 ( Springer textbook ).
• John Brillhart , DH Lehmer , JL Selfridge : New Primality Criteria and factorizations of . ${\displaystyle 2^{n}\pm 1}$In: Mathematics of Computation. 29, 1975, ISSN  0025-5718 , pp. 620-647, online (PDF; 2.14 MB) .

Individual evidence

1. ↑ Proof of this: see Ribenboim, Die Welt der Prime Numbers , page 40.
2. ↑ To prove this and the previous theorem, see Ribenboim, Die Welt der Prime Numbers , page 42.
3. ^ Daniela Steidl: Pratt certificate of prime numbers. April 17, 2008, accessed May 7, 2020 . 
4. ↑ apl. Prof. Dr. Klaus Reinhardt: Pratt prime number test. Retrieved on May 7, 2020 (German, English).