Primecoin primality test

When I wrote about how Primecoin uses prime chains for proof of work, I left out a detail.

To mine a new Primecoin block, you have to find a prime chain of specified length that starts with a number that is a multiple of the block header hash. According to the Primecoin whitepaper

Another important property of proof-of-work for cryptocurrency is non-reusability. ... To achieve this, the prime chain is linked to the block header hash by requiring that its origin be divisible by the block header hash.

So given a hashh, you have to findk such thatkh is the origin of a prime chain, where origin" is defined in footnote [2] here.

Strictly speaking, the primes in a Primecoin prime chain areprobable primes. Someone verifying a Primecoin blockchain will be satisfied that the block is authentic if the necessary numbers are primeaccording to the test used by the Primecoin software. Whether the numbers are actually prime is irrelevant.

Probabilistic primality tests are much more efficient than deterministic tests, and most applications requiring primes, such as RSA encryption, actually use probable primes. If a number is rejected as a probable prime, it's certainly not a prime. If it is accepted as a prime, it very like is prime. More on probable primes here.

If you write your own Primecoin mining software using a different primality test, that's fine as long as you actually find primes. But if one time you find pseudoprimes, composite numbers that pass your primality test, then your block will be rejected unless your pseudoprimes also pass the Primecoin software's primality test.

Primecoin's primality test

So what is Primecoin's (probable) primality test? We quote the Primecoin whitepaper:

The classical Fermat test of base 2 is used together with Euler-Lagrange-Lifchitz test to verify probable primality for the prime chains. Note we do not require strict primality proof during verification, as it would unnecessarily burden the efficiency of verification. Composite number that passes Fermat test is commonly known as pseudoprime. Since it is known by the works of Erdos and Pomerance that pseudoprimes of base 2 are much more rare than primes, it suffices to only verify probable primality.

Fermat's test

The Fermat test with base b says to test whether a candidate number n satisfies

b^{n - 1} = 1 mod n.

If n is prime, the equation above will hold. The converse is usually true: if the equation above hold, n is likely to be prime. There are exceptions, such as b = 2 and n = 561 = 3 * 11 * 17.

Euler-Lagrange-Lifchitz test

But what is the Euler-Lagrange-Lifchitz test? The whitepaper links here, a page by Henri Lifchitz that gives results generalizing those of Leonard Euler and Joseph-Louis Lagrange.

Testing 2p + 1

Supposep is an odd prime. Then the Euler-Lagrange test says that ifp = 3 mod 4, thenq = 2p + 1 is also prime if and only if

2^p = 1 mod q.

Lifchitz gives three variations on this result. First, ifp = 1 mod 4, then q = 2p + 1 is also prime if and only if

2^p = -1 mod q.

Together these two theorems give a way to testwith certainty whether 2p + 1, i.e. the next term in a Cunningham chain of the first kind, is prime. However, the test is still probabilistic if we don't know for certain thatp is prime.

Testing 2p - 1

The last two results of Lifchitz are as follows. If p andq = 2p - 1 are prime, then

2^{p - 1} = 1 mod q

if p = 1 mod 4 and

2^{p - 1} = -1 mod q

ifp = 3 mod 4.

The converses of these two statements giveprobable prime tests forq if we know p is prime.

So we can verify a (probable) prime chain by using Fermat's test to verify that the first element is (probably) prime and use the Euler-Lagrange-Lifchitz test that the rest of the numbers in the chain are (probably) prime.

Related posts

• Fermat's factoring trick
• False witnesses
• Zero-knowledge proof of compositeness

The post Primecoin primality test first appeared on John D. Cook.