Lucas primality test

The Lucas primality test invented in 1891 by Édouard Lucas, determines whether a number N is prime or not, using the complete factorization of N-1.

If, for some integer b, the quantity b^N-1 is congruent to 1 modulo N, and if b^(N-1)/q is not congruent to 1 modulo N for any prime divisor q of N-1, then N is a prime.

Example

Prove that N = 811 is prime knowing that N-1 = 2 × 3⁴ × 5

Let's start with b = 3.

$3^{810/2}=3^{405}\equiv 810(\mathrm{mod}811)$

$3^{810/3}=3^{270}\equiv 680(\mathrm{mod}811)$

$3^{810/5}=3^{162}\equiv 212(\mathrm{mod}811)$

$3^{810}\equiv 1(\mathrm{mod}811)$

All conditions of the test hold so 811 is prime.

The fourth computation is not needed: compute b^(N-1)/2 as done in the example, if it is congruent to 1, the value b must be changed, if it is congruent to N-1, the first condition of the test holds, otherwise N is composite.

Notice the b = 7 is a bad choice because:

$7^{810/2}=7^{405}\equiv 1(\mathrm{mod}811)$

External links

• Wikipedia