Cunningham chain

From Wikipedia, the free encyclopedia

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 2 = 2 p 1 + 1$ , $p 3 = 4 p 1 + 3$ , $p 4 = 8 p 1 + 7$ , ..., $p i = 2 i - 1 p 1 + (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]

1 Largest known Cunningham chains
2 Congruences of Cunningham chains
3 References
4 External links

[edit] 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 May 2008^[2])
k	Kind	p₁ (starting prime)	Digits	Year	Discoverer
2	1st	48047305725×2¹⁷²⁴⁰³ − 1	51910	2007	D. Underbakke
3	1st	164210699973×2²⁶³²⁶ − 1	7937	2006	M. Paridon
4	1st	119184698×5501# − 1	2354	2005	J. Sun
5	1st	357487161295×1693# − 1	727	2008	D. Augustin
6	2nd	37783362904×1097# + 1	475	2006	D. Augustin
7	2nd	668302064×593# + 786153598231	251	2008	T. Wolter, J. K. Andersen
8	1st	2×65728407627×431# − 1	186	2005	D. Augustin
9	1st	65728407627×431# − 1	185	2005	D. Augustin
10	2nd	145683282311×181# + 1	84	2005	D. Augustin
11	2nd	2×(8428860×127# + 212148902055091) − 1	56	2006	J. K. Andersen
12	2nd	8428860×127# + 212148902055091	56	2006	J. K. Andersen
13	1st	1753286498051×71# − 1	39	2005	D. Augustin
14	1st	9510321949318457733566099	25	2004	J. K. Andersen
15	1st	11993367147962683402919	23	2004	T. Alm, J. K. Andersen
16	1st	892390227741617675069	21	2002	P. Carmody, P. Jobling

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

As of May 2008, the longest known Cunningham chain of either kind is of length 16. Such a chain of the second kind was discovered by Tony Forbes in 1997, starting with 3203000719597029781. A chain of the first kind was discovered by Phil Carmody and Paul Jobling in 2002, starting with 810433818265726529159.^[2]

[edit] 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 = 2 p 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 = 2 p 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 $2 p 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.

[edit] References

^ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
^ ^a ^b Dirk Augustin, Cunningham Chain records. Retrieved on 2008-05-18

[edit] 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