A number p greater than one is prime if and only if the only divisors of p are 1 and p. First few prime numbers are 2, 3, 5, 7, 11, 13, …
The Lucas test is a primality test for a natural number n, it can test primality of any kind of number.
It follows from Fermat’s Little Theorem: If p is prime and a is an integer, then a^p is congruent to a (mod p )
Lucas’ Test : A positive number n is prime if there exists an integer a (1 < a < n) such that : And for every prime factor q of (n-1),
Input : n = 7 Output : 7 is Prime Explanation : let's take a = 3, then 3^6 % 7 = 729 % 7 = 1 (1st condition satisfied). Prime factors of 6 are 2 and 3, 3^(6/2) % 7 = 3^3 % 7 = 27 % 7 = 6 3^(6/3) % 7 = 3^2 % 7 = 9 % 7 = 2 Hence, 7 is Prime Input : n = 9 Output : 9 is composite Explanation : Let's take a = 2, then 2^8 % 8 = 256 % 8 = 0 Hence 9 is composite
lucasTest(n): If n is even return composite Else Find all prime factors of n-1 for i=2 to n-1 pick 'a' randomly in range [2, n-1] if a^(n-1) % n not equal 1: return composite else // for all q, prime factors of (n-1) if a^(n-1)/q % n not equal 1 return prime Return probably prime
Problems Associated with Lucas’s test are :
- Knowing all of the prime factors of n-1
- Finding an appropriate choice for a
7 is prime 9 is composite 37 is prime
This method is quite complicated and inefficient as compared to other primality tests. And the main problems are factors of ‘n-1’ and choosing appropriate ‘a’.
Other Primality tests:
- Primality Test | Set 1 (Introduction and School Method)
- Primality Test | Set 2 (Fermat Method)
- Primality Test | Set 3 (Miller–Rabin)
- Primality Test | Set 4 (Solovay-Strassen)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.