Lucas primality test

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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. It is the basis of the Pratt certificate that gives a concise verification that n is prime.

Concepts

Let n be a positive integer. If there exists an integer a, 1  a^{n-1}\ \equiv\ 1 \pmod n \, and for every prime factor q of n − 1 a^{({n-1})/q}\ \not\equiv\ 1 \pmod n \, then n is prime. If no such number a exists, then n is either 1, 2, or composite.

The reason for the correctness of this claim is as follows: if the first equivalence holds for a, we can deduce that a and n are coprime. If a also survives 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 (because the order of every element of a group divides the order of the group), implying that n is prime.

Conversely, if n is prime, then there exists a primitive root modulo n, or generator of the group (Z/nZ)*. Such a generator has order |(Z/nZ)*| = n − 1 and both equivalences will hold for any such primitive root. Note that if there exists an a  17^{70}\ \equiv\ 1 \pmod {71}.

For all integers a it is known that a^{n - 1}\equiv 1 \pmod{n}\ \text{ if and only if } \text{ ord}(a)\mid(n-1). Therefore, the multiplicative order of 17 (mod 71) is not necessarily 70 because some factor of 70 may also work above.

So check 70 divided by its prime factors: 17^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71} 17^{14}\ \equiv\ 25\ \not\equiv\ 1 \pmod {71} 17^{10}\ \equiv\ 1\ \equiv\ 1 \pmod {71}. Unfortunately, we get that 17 10  ≡ 1 (mod 71). So we still do not know if 71 is prime or not.

We try another random a, this time choosing a = 11. Now we compute: 11^{70}\ \equiv\ 1 \pmod {71}. Again, this does not show that the multiplicative order of 11 (mod 71) is 70 because some factor of 70 may also work.

So check 70 divided by its prime factors: 11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71} 11^{14}\ \equiv\ 54\ \not\equiv\ 1 \pmod {71} 11^{10}\ \equiv\ 32\ \not\equiv\ 1 \pmod {71}. So the multiplicative order of 11 (mod 71) is 70, and thus 71 is prime. (To carry out these modular exponentiations, one could use a fast exponentiation algorithm like binary or addition-chain exponentiation).

Algorithm

The algorithm can be written in pseudocode as follows: algorithm lucas_primality_test is input: n > 2, an odd integer to be tested for primality. k, a parameter that determines the accuracy of the test. output: prime if n is prime, otherwise composite or possibly composite. determine the prime factors of n−1. LOOP1: repeat k times: pick a randomly in the range [2, n − 1] return composite else {{nowrap| \color{Gray}{a^{n-1} \equiv 1 \pmod n} }} LOOP2: for all prime factors q of n−1: if we checked this equality for all prime factors of n−1 then return prime else continue LOOP2 else {{nowrap| \color{Gray}{a^\frac{n-1}q \equiv 1 \pmod n} }} continue LOOP1 return possibly composite.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1350389211 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001350389211 · captured 2026-04-21 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Lucas primality test”, snapshot enwiki-001350389211. https://encyclopegia.org/a/lucas-primality-test

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.