# Cunningham chain

In mathematics, a Cunningham chain is a certain sequence of prime numbers. Cunningham chains are named after mathematician A. J. C. Cunningham. They are also called chains of nearly doubled primes.

## Definition

A Cunningham chain of the first kind of length n is a sequence of prime numbers (p1, ..., pn) such that for all 1 ≤ i < n, pi+1 = 2pi + 1. (Hence each term of such a chain except the last one is a Sophie Germain prime, and each term except the first is a safe prime).

It follows that

\begin{align} p_2 & = 2p_1+1, \\ p_3 & = 4p_1+3, \\ p_4 & = 8p_1+7, \\ & {}\ \vdots \\ p_i & = 2^{i-1}p_1 + (2^{i-1}-1). \end{align}

Or, by setting $a = \frac{p_1 + 1}{2}$ (the number $a$ is not part of the sequence and need not be a prime number), we have $p_i = 2^{i} a - 1$

Similarly, a Cunningham chain of the second kind of length n is a sequence of prime numbers (p1,...,pn) such that for all 1 ≤ i < n, pi+1 = 2pi − 1.

It follows that the general term is

$p_i = 2^{i-1}p_1 - (2^{i-1}-1) \,$

Now, by setting $a = \frac{p_1 - 1}{2}$, we have $p_i = 2^{i} a + 1$.

Cunningham chains are also sometimes generalized to sequences of prime numbers (p1, ..., pn) such that for all 1 ≤ i ≤ n, pi+1api + b for fixed coprime integers ab; the resulting chains are called generalized Cunningham chains.

A Cunningham chain is called complete if it cannot be further extended, i.e., if the previous or next term in the chain would not be a prime number anymore.

## Examples

Examples of complete Cunningham chains of the first kind include these:

2, 5, 11, 23, 47 (The next number would be 95, but that is not prime.)
3, 7 (The next number would be 15, but that is not prime.)
29, 59 (The next number would be 119 = 7*17, but that is not prime.)
41, 83, 167 (The next number would be 335, but that is not prime.)
89, 179, 359, 719, 1439, 2879 (The next number would be 5759 = 13*443, but that is not prime.)

Examples of complete Cunningham chains of the second kind include these:

2, 3, 5 (The next number would be 9, but that is not prime.)
7, 13 (The next number would be 25, but that is not prime.)
19, 37, 73 (The next number would be 145, but that is not prime.)
31, 61 (The next number would be 121 = 112, but that is not prime.)
151, 301, 601, 1201, 2401, 4801, 9601 (The next number would be 19201 = 7*13*211, but that is not prime.)

Cunningham chains are now considered useful in cryptographic systems since "they provide two concurrent suitable settings for the ElGamal cryptosystem ... [which] can be implemented in any field where the discrete logarithm problem is difficult."[1]

## Largest known Cunningham chains

It follows from Dickson's conjecture and the broader Schinzel's hypothesis H, both widely believed to be true, that for every k there are infinitely many Cunningham chains of length k. There are, however, no known direct methods of generating such chains.

There are computing competitions for the longest Cunningham chain or for the one built up of the largest primes - but unlike the breakthrough of Ben J. Green and Terence Tao, there is no general result known on large Cunningham chains to date. A relevant open problem, Rassias conjecture can be also stated in terms of Cunningham chains, namely: there exist Cunningham chains with parameters $2a, -1$ for $a$ such that $2a-1=p$ is a prime number.

Largest known Cunningham chain of length k (as of 5 May 2013[2])
k Kind p1 (starting prime) Digits Year Discoverer
1 257885161 − 1 17425170 2013 Curtis Cooper, GIMPS
2 1st 18543637900515×2666667 − 1 200701 2012 Philipp Bliedung, PrimeGrid
2nd 648309×2148310 + 1 44652 2010 Tom Wu
3 1st 5110664609396115×234944 − 1 10535 2014 Gevay, Vatai, Farkas & Jarai
2nd 82659189×226997 + 1 8135 2010 Tom Wu
4 1st 1249097877×6599# − 1 2835 2011 Michael Angel
2nd 630698711×4933# + 1 2105 2010 Michael Angel
5 1st 4250172704×2749# − 1 1183 2012 Dirk Augustin
2nd 80670856865×2677# + 1 1140 2011 Michael Angel
6 1st 37488065464×1483# − 1 633 2010 Dirk Augustin
2nd 480112483568×1511# + 1 650 2014 Östlin
7 1st 162597166369×827# − 1 356 2010 Dirk Augustin
2nd 668302064×593# + 786153598231 251 2008 Thomas Wolter & Jens Kruse Andersen
8 1st 2×65728407627×431# − 1 186 2005 Dirk Augustin
2nd 1148424905221×509# + 1 224 2010 Dirk Augustin
9 1st 65728407627×431# − 1 185 2005 Dirk Augustin
2nd 182887101390961871050645934589918687746535370612015546956692154622371784133412186×223# + 1 167 2013 Primecoin (block 79349)
10 1st 44598464649019035883154084128331646888059795218766083584048621139159337786287845212160000×149# − 1 146 2013 Primecoin (block 182690)
2nd 61817679876032272550156670131676808699749929053121752139098662160409729216×179# + 1 145 2014 Primecoin (block 519253)
11 1st 73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1 140 2013 Primecoin (block 95569)
2nd 8026337833619599372491948674562462668692014872229571339857384053514279156849912832×109# + 1 127 2014 Primecoin (block 365304)
12 1st 61592551716229060392971860549140211602858978086524024531871935735163762961673908480×71# − 1 110 2013 Primecoin (block 239833)
2nd 160433998429454286861864982184342218645773889300991352796925862298096263175269000×73# + 1 109 2013 Primecoin (block 323183)
13 1st 106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1 107 2014 Primecoin (block 368051)
2nd 568980826640711977012761168233683848109012030650333480799148348813080407943543452×47# + 1 99 2014 Primecoin (block 519344)
14 1st 2×27353790674175627273118204975428644651729 + 1 41 2014 Jaroslaw Wroblewski
2nd 5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1 100 2014 Primecoin(block 547267)
15 1st 27353790674175627273118204975428644651729 41 2014 Jaroslaw Wroblewski
2nd 28320350134887132315879689643841 32 2008 Jaroslaw Wroblewski
16 1st 91304653283578934559359 23 2008 Jaroslaw Wroblewski
2nd 2×1540797425367761006138858881 − 1 28 2014 Chermoni & Wroblewski
17 1st 2759832934171386593519 22 2008 Jaroslaw Wroblewski
2nd 1540797425367761006138858881 28 2014 Chermoni & Wroblewski
18 2nd 658189097608811942204322721 27 2014 Chermoni & Wroblewski
19 2nd 79910197721667870187016101 26 2014 Chermoni & Wroblewski

q# denotes the primorial 2×3×5×7×...×q.

As of 2014, the longest known Cunningham chain of either kind is of length 19, discovered by Jaroslaw Wroblewski in 2014.[2]

## Congruences of Cunningham chains

Let the odd prime $p_1$ be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus $p_1 \equiv 1 \pmod{2}$. Since each successive prime in the chain is $p_{i+1} = 2p_i + 1$ it follows that $p_i \equiv 2^i - 1 \pmod{2^i}$. Thus, $p_2 \equiv 3 \pmod{4}$, $p_3 \equiv 7 \pmod{8}$, and so forth.

The above property can be informally observed by considering the primes of a chain in base 2. (Note that, as with all bases, multiplying by the number of the base "shifts" the digits to the left.) When we consider $p_{i+1} = 2p_i + 1$ in base 2, we see that, by multiplying $p_i$ by 2, the least significant digit of $p_i$ becomes the secondmost least significant digit of $p_{i+1}$. Because $p_i$ is odd—that is, the least significant digit is 1 in base 2--we know that the secondmost least significant digit of $p_{i+1}$ is also 1. And, finally, we can see that $p_{i+1}$ will be odd due to the addition of 1 to $2p_i$. In this way, successive primes in a Cunningham chain are essentially shifted left in binary with ones filling in the least significant digits. For example, here is a complete length 6 chain which starts at 141361469:

Binary Decimal
1000011011010000000100111101 141361469
10000110110100000001001111011 282722939
100001101101000000010011110111 565445879
1000011011010000000100111101111 1130891759
10000110110100000001001111011111 2261783519
100001101101000000010011110111111 4523567039

A similar result holds for Cunningham chains of the second kind. From the observation that $p_1 \equiv 1 \pmod{2}$ and the relation $p_{i+1} = 2 p_i - 1$ it follows that $p_i \equiv 1 \pmod{2^i}$. In binary notation, the primes in a Cunningham chain of the second kind end with a pattern "0...01", where, for each $i$, the number of zeros in the pattern for $p_{i+1}$ is one more than the number of zeros for $p_i$. As with Cunningham chains of the first kind, the bits left of the pattern shift left by one position with each successive prime.

Similarly, because $p_i = 2^{i-1}p_1 + (2^{i-1}-1) \,$ it follows that $p_i \equiv 2^{i-1} - 1 \pmod{p_1}$. But, by Fermat's little theorem, $2^{p_1-1} \equiv 1 \pmod{p_1}$, so $p_1$ divides $p_{p_1}$ (i.e. with $i = p_1$). Thus, no Cunningham chain can be of infinite length.[3]