Added to Favorites

Popular Searches

Definitions

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.## Largest known Cunningham chains

## Congruences of Cunningham chains

## References

## External links

A Cunningham chain of the first kind of length n is a sequence of prime numbers (p_{1},...,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\; =\; 2p\_1+1$, $p\_3\; =\; 4p\_1+3$, $p\_4\; =\; 8p\_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_{1},...,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_{1},...,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.

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.

k | Kind | p_{1} (starting prime)
| Digits | Year | Discoverer |
---|---|---|---|---|---|

2 | 1st | 48047305725×2^{172403} − 1
| 51910 | 2007 | D. Underbakke |

3 | 1st | 164210699973×2^{26326} − 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 | 1st | 1178137903623×661# − 1 | 291 | 2008 | D. Augustin |

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 | 2nd | 2×28320350134887132315879689643841 − 1 | 32 | 2008 | J. Wroblewski |

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 July 2008, 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.

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.

- 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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday October 11, 2008 at 11:39:24 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday October 11, 2008 at 11:39:24 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.