Luke test

In number theory, the Lucas test is a primality test for a natural number n and requires that the prime factors of n − 1 are known.

If there exists a natural number a less than n and greater than 1 that verifies the conditions

an− − 1≡ ≡ 1(modn){displaystyle a^{n-1}equiv 1{pmod {n}}}

as well as

a(n− − 1)/q 1(modn){displaystyle a^{({n-1})/q}not equiv 1{pmod {n}}}}}

for all prime factors q of n − 1, then n is prime. If no such a can be found, then n is a composite number.

This algorithm is correct since if a passes the first step, we can deduce that a and n are coprime. If a also passes the second step, then the order of a in the group (Z/nZ)* is equal to n − 1, which means that the order of that group is n − 1, implying that n is prime. Conversely, if n is prime, then there exists a primitive root modulo n and any primitive root will pass both steps of the algorithm.

Example

For example, take n = 71. So, n − 1 = 70 = (2)(5)(7). Now take a = 11. First:

1170≡ ≡ 1(mod71){displaystyle 11^{70} equiv 1{pmod {71}}}}

This does not prove that the multiplicative order of 11 mod 71 is 70, because some factor of 70 could still work up. We then verify 70 divided by its prime factors:

1135≡ ≡ 70 1(mod71){displaystyle 11^{35} equiv 70 not equiv 1{pmod {71}}}}

1114≡ ≡ 54 1(mod71){displaystyle 11^{14} equiv 54not equiv 1{pmod {71}}}}

1110≡ ≡ 32 1(mod71){displaystyle 11^{10} equiv 32not equiv 1{pmod {71}}}}

So, the multiplicative order of 11 mod 71 is 70 and thus, 71 is prime.

To realize these modular powers, the accelerated method of binary exponentiation should be used.