Information as of 2020-04-07: Inserting more history entries for

**Riesel primes k<300****Collected:**MersenneForum thread "POST LOTS AND LOTS OF PRIMES HERE":**#1 (2010-03-17) - #1945 (2020-03-11)**(**100%**) done.**Collected:**IDs for Riesel primes of the The Prime Pages:*k*= 1 - 299**100%**) done.**DONE**: MersenneForum thread "Riesel Primes k*2^n-1, k<300 (Part II)" (#1 (2007-07-08) - #986 (2020-04-06)).**Please check your reservations here****.**

# 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^{4} × 5

Let's start with b = 3.

- [math]3^{810/2}\,= \,3^{405}\,\equiv \, 810\,\pmod{811}[/math]
- [math]3^{810/3}\,= \,3^{270}\,\equiv \, 680\,\pmod{811}[/math]
- [math]3^{810/5}\,= \,3^{162}\,\equiv \, 212\,\pmod{811}[/math]
- [math]3^{810}\,\equiv \, 1\,\pmod{811}[/math]

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:

- [math]7^{810/2}\,= \,7^{405}\,\equiv \, 1\,\pmod{811}[/math]