Lucas primality test
From Wikipedia, the free encyclopedia
For the test for Mersenne numbers, see Lucas–Lehmer primality test. For the Lucas–Lehmer–Riesel test, see Lucas–Lehmer–Riesel test. For the Lucas probable prime test, see Lucas pseudoprime.
In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known.[1][2] It is the basis of the Pratt certificate that gives a concise verification that n is prime.