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.

A Cunningham chain of the first kind of length n is a sequence of prime numbers (p₁,...,p_n) such that for all 1 ≤ i < n, p_i+1 = 2 p_i + 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 p₂ = 2p₁ + 1, p₃ = 4p₁ + 3, p₄ = 8p₁ + 7, ..., p_i = 2^{i − 1}p₁ + (2^{i − 1} − 1).

Similarly, a Cunningham chain of the second kind of length n is a sequence of prime numbers (p₁,...,p_n) such that for all 1 ≤ i < n, p_i+1 = 2 p_i - 1.

Cunningham chains are also sometimes generalized to sequences of prime numbers (p₁,...,p_n) such that for all 1 ≤ i < n, p_i+1 = ap_i + b for fixed coprime integers a, b; 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.

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.

Largest known Cunningham chain of length k (as of 8 November 2011 (2011 -11-08)^[update][2])

k	Kind	p1 (starting prime)	Digits	Year	Discoverer
1	1st	243112609 − 1	12978189	2008	GIMPS / Edson Smith
2	1st	183027×2265440 − 1	79911	2010	T. Wu
3	1st	914546877×234772 − 1	10477	2010	T. Wu
4	1st	119184698×5501# − 1	2354	2005	J. Sun
5	2nd	45008010405×2621# + 1	1116	2010	D. Broadhurst
6	1st	37488065464×1483# − 1	633	2010	D. Augustin
7	1st	162597166369×827# − 1	356	2010	D. Augustin
8	2nd	1148424905221×509# + 1	224	2010	D. Augustin
9	1st	65728407627×431# − 1	185	2005	D. Augustin
10	2nd	1070828503293×239# + 1	109	2009	D. Augustin
11	2nd	2×13931865163581×127# + 1	63	2008	D. Augustin
12	2nd	13931865163581×127# + 1	62	2008	D. Augustin
13	1st	1753286498051×71# − 1	39	2005	D. Augustin
14	2nd	335898524600734221050749906451371	33	2008	J. K. Andersen
15	2nd	28320350134887132315879689643841	32	2008	J. Wroblewski
16	2nd	2368823992523350998418445521	28	2008	J. Wroblewski
17	2nd	1302312696655394336638441	25	2008	J. Wroblewski

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

As of 2011^[update], the longest known Cunningham chain of either kind is of length 17. The first known was of the 1st kind starting at 2759832934171386593519, discovered by Jaroslaw Wroblewski in 2008 where he also found some of the 2nd kind.^[2]

Congruences of Cunningham chains

Let the odd prime p₁ 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} = 2p_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.

References

1. ^ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
2. ^ ^{a b} Dirk Augustin, Cunningham Chain records. Retrieved on 2011-11-08.

External links

• The Prime Glossary: Cunningham chain
• PrimeLinks++: Cunningham chain
• Sequence A005602 in OEIS: the first term of the lowest complete Cunningham Chains of the first kind of length n, for 1 <= n <= 14
• Sequence A005603 in OEIS: the first term of the lowest complete Cunningham Chains of the second kind with length n, for 1 <= n <= 15