Lucas test (mathematics)
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:
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
such as
holds for all natural numbers .
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:
(Lucas test) A natural number is a prime number if and only if there is a with for that
such as
holds for all real divisors of .
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 .
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 .
Example:
The following applies to the number . The real dividers of are and . Further applies and . It follows that is a prime number.
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
such as
for all prime factors of .
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
- .
Then the following applies: is a prime number if and only if there is a natural number with for every prime factor for which
such as
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:
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.
Fermat couple
is a Fermat pair if
Pratt sequence
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:
For every prime number there is a Pratt sequence the length of the representation of the prime number, which is why .
example
For the following is a possible Pratt sequence
to check is now even whether , and on whether the prime divisors of true
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 . In: Mathematics of Computation. 29, 1975, ISSN 0025-5718 , pp. 620-647, online (PDF; 2.14 MB) .
Individual evidence
- ↑ Proof of this: see Ribenboim, Die Welt der Prime Numbers , page 40.
- ↑ To prove this and the previous theorem, see Ribenboim, Die Welt der Prime Numbers , page 42.
- ^ Daniela Steidl: Pratt certificate of prime numbers. April 17, 2008, accessed May 7, 2020 .
- ↑ apl. Prof. Dr. Klaus Reinhardt: Pratt prime number test. Retrieved on May 7, 2020 (German, English).