Prime Chain Applications

Primecoin recognises three distinct types of prime chain, each with its own mathematical structure and level of rarity. Understanding the difference between them is the key to reading the data displayed throughout this explorer.

All three types share a common feature: each prime in the chain is related to the previous one by a factor of approximately two. This "near-doubling" property is what makes Cunningham chains special — and what makes them useful in cryptography, as explored in the companion article on Primecoin & Cryptography.

In a Cunningham chain of the first kind, each prime is exactly double its predecessor plus one:

The first prime in the chain is called the root. Every subsequent prime is a safe prime — a number of the form 2p + 1 where p is also prime. This is the chain type most directly relevant to cryptography.

The second example above is a 1CC of length 6. Notice how each term is almost exactly double the previous one. The longest known 1CC has length 17, beginning at the 26-digit prime 2,759,832,934,171,386,593,519.

In a Cunningham chain of the second kind, each prime is double its predecessor minus one:

The root of a 2CC chain is a prime p such that 2p − 1 is also prime. These are sometimes called "Cunningham primes of the second kind." They are slightly more common than 1CC chains of the same length, because the condition 2p − 1 is prime is marginally easier to satisfy than 2p + 1 is prime.

Note: in the first example, 9 = 2×5 − 1 is not prime, so this is actually only a 2CC of length 2. The second example (19, 37, 73) is a valid 2CC of length 3. The longest known 2CC has length 19.

A bi-twin chain is the rarest and most mathematically beautiful of the three types. It requires a number n such that both:

In other words, a bi-twin chain simultaneously satisfies both the 1CC and 2CC conditions, interleaved around a central value n. The pairs (n − 1, n + 1) are twin primes, and the pairs at each subsequent step are also twin primes.

Here n = 6: the pairs are (5, 7) and (11, 13), both twin prime pairs. The chain has length 2. Bi-twin chains of length 3 or more are extraordinarily rare.

A bi-twin chain of length k contains 2k primes simultaneously satisfying both Cunningham conditions. Finding one is roughly the square of the difficulty of finding a 1CC or 2CC of the same length.

The prime number theorem tells us that the probability a random number near N is prime is approximately 1/ln(N). For a Cunningham chain of length k, we need k consecutive numbers (each roughly double the last) to all be prime. Assuming rough independence, the probability is approximately:

At the current Primecoin block height, the origin numbers are hundreds of digits long. For such numbers, ln(N) is on the order of 700. A chain of length 10 has probability roughly (1/700)¹⁰ ≈ 3.5 × 10⁻²⁸ — vanishingly small. This is why Primecoin adjusts its difficulty by requiring longer chains as more mining power joins the network.

These figures are approximate and depend on the size of the numbers being searched. The key insight is that each additional link in the chain multiplies the rarity by roughly ln(N), making the search exponentially harder.

Because chain length is an integer, using it directly as a difficulty metric would cause large jumps in required work. Primecoin instead uses a fractional chain length as its difficulty measure:

Here k is the integer chain length, pₖ is the last prime in the chain, and r is the remainder when testing the next candidate for primality. The fractional part (pₖ − r) / pₖ measures how "close" the chain came to having one more link. This allows smooth, continuous difficulty adjustment — the same elegance that characterises the rest of Primecoin's design.