Lucas primality test
The Lucas test is a further development of the Fermat primality tests by the mathematician Édouard Lucas. The test was improved in the 50s by Derrick Lehmer and again later by John Brillhart and John L. Selfridge. It should not be confused with the Lucas- Lehmer test for Mersenne numbers.
Fermat's primality test
Given a natural number n> 1, for which you would like to check if it is prime.
After the Fermat primality test n is not prime if the following condition for a coprime to n number a, 1
The Fermat test therefore never delivers the statement that a number is prime, but can only exclude the prim - being.
For the Carmichael numbers of Fermat test does not provide information.
In 1876 won Édouard Lucas following converse of Fermat's little theorem:
( Forerunner of the Lucas- tests) A natural number n is a prime number if and only if there is an a with 1
As well as
1 applies - for all natural numbers m
This result can be difficult to apply, since so many meters must be tested.
In 1891 Lucas improved the sentence and was named after him primality test:
(Lucas test) A natural number n is a prime number if and only if there is an a with 1
As well as
For all proper divisors m
Since here only the divisors of n - 1 must be tested, less computational steps are greatly needed.
One drawback, however, is that one the prime factorization of n - 1 needs to know.
n - 1 must therefore be factored.
This method is a number with a special structure but very efficient, such as with numbers of the form 2 k 1.
Is not the condition of the Lucas test for a base a is not satisfied, it follows that the number n is composite.
For this you should in fact consider 1
Example:
For the number n = 59 is considered 258 ≡ 1 mod 59 The proper divisors of n - 1 = 58 are 1, 2 and 29, 21 ≡ 2 mod applies Next 59, 22 ≡ 4 mod 59 and 229 ≡ -1 mod 59
it follows that 59 is a prime number.
Derrick Lehmer found 1953 improved Lucas- test.
In 1967, another version ( flexible Lucas test) by John Brillhart and John L. Selfridge was discovered.
The improved test is based on the following Lucas- feature:
n is a prime number if and only if there exists an integer a with 1 < a < n for which
As well as
For all prime factors q of n - 1 applies.
The use of this test on Fermat numbers is denoted by Pépin test.
Lucas, the flexible test based on the following property:
For the natural number n is the prime factorization of n is - 1 is given by
Then n is a prime number if and only if, for every prime factor a natural number with 1 < ai < n for which
As well as
Applies.
We consider the prime number n = 911
The previous number n -1 = 910 has the prime factor q = 2, 5, 7 and 13 The following table shows matching a and as the conditions are fulfilled:
Lucas test
Extensions of Lehmer, Brillhart and Selfridge
Improved Lucas test
Flexible Lucas test
Example