# Lucas Primality Test

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), ```

Examples :

```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
•  `// CPP Program for Lucas Primality Test ` `#include ` `using` `namespace` `std; ` ` `  `// function to generate prime factors of n ` `void` `primeFactors(``int` `n, vector<``int``>& factors) ` `{ ` `    ``// if 2 is a factor ` `    ``if` `(n % 2 == 0) ` `        ``factors.push_back(2); ` `    ``while` `(n % 2 == 0) ` `        ``n = n / 2; ` `         `  `    ``// if prime > 2 is factor ` `    ``for` `(``int` `i = 3; i <= ``sqrt``(n); i += 2) { ` `        ``if` `(n % i == 0) ` `            ``factors.push_back(i); ` `        ``while` `(n % i == 0) ` `            ``n = n / i; ` `    ``} ` `    ``if` `(n > 2) ` `      ``factors.push_back(n); ` `} ` ` `  `// this function produces power modulo  ` `// some number. It can be optimized to  ` `// using  ` `int` `power(``int` `n, ``int` `r, ``int` `q) ` `{ ` `    ``int` `total = n; ` `    ``for` `(``int` `i = 1; i < r; i++) ` `        ``total = (total * n) % q; ` `    ``return` `total; ` `} ` ` `  `string lucasTest(``int` `n) ` `{ ` `    ``// Base cases  ` `    ``if` `(n == 1) ` `        ``return` `"neither prime nor composite"``; ` `    ``if` `(n == 2) ` `        ``return` `"prime"``; ` `    ``if` `(n % 2 == 0) ` `        ``return` `"composite1"``; ` `         `  `         `  `    ``// Generating and storing factors  ` `    ``// of n-1 ` `    ``vector<``int``> factors; ` `    ``prime_factors(n - 1, factors); ` ` `  `    ``// Array for random generator. This array  ` `    ``// is to ensure one number is generated  ` `    ``// only once ` `    ``int` `random[n - 3]; ` `    ``for` `(``int` `i = 0; i < n - 2; i++) ` `        ``random[i] = i + 2; ` `         `  `    ``// shuffle random array to produce randomness ` `    ``shuffle(random, random + n - 3,  ` `               ``default_random_engine(``time``(0))); ` ` `  `    ``// Now one by one perform Lucas Primality ` `    ``// Test on random numbers generated. ` `    ``for` `(``int` `i = 0; i < n - 2; i++) { ` `        ``int` `a = random[i];  ` `        ``if` `(power(a, n - 1, n) != 1)  ` `            ``return` `"composite"``; ` ` `  `        ``// this is to check if every factor  ` `        ``// of n-1 satisfy the condition ` `        ``bool` `flag = ``true``; ` `        ``for` `(``int` `k = 0; k < factors.size(); k++) { ` `            ``// if a^((n-1)/q) equal 1 ` `            ``if` `(power(a, (n - 1) / factors[k], n) == 1) { ` `                ``flag = ``false``; ` `                ``break``; ` `            ``} ` `        ``} ` ` `  `        ``// if all condition satisfy ` `        ``if` `(flag) ` `            ``return` `"prime"``; ` `    ``} ` `    ``return` `"probably composite"``; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``cout << 7 << ``" is "` `<< lucasTest(7) << endl; ` `    ``cout << 9 << ``" is "` `<< lucasTest(9) << endl; ` `    ``cout << 37 << ``" is "` `<< lucasTest(37) << endl; ` `    ``return` `0; ` `} `

Output:

```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: