Cunningham chain

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 (p1,...,pn) such that for all 1 ≤ i < n, pi+1 = 2 pi + 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 p2 = 2p1 + 1, p3 = 4p1 + 3, p4 = 8p1 + 7, ..., pi = 2i − 1p1 + (2i − 1 − 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 = 2 pi - 1.

Cunningham chains are also sometimes generalized to sequences of prime numbers (p1,...,pn) such that for all 1 ≤ i < n, pi+1 = api + 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]

Contents

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)[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, 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 p1 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 pi + 1 = 2pi + 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 pi + 1 = 2pi + 1 in base 2, we see that, by multiplying pi by 2, the least significant digit of pi becomes the secondmost least significant digit of pi + 1. Because pi is odd--that is, the least significant digit is 1 in base 2--we know that the secondmost least significant digit of pi + 1 is also 1. And, finally, we can see that pi + 1 will be odd due to the addition of 1 to 2pi. 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 pi + 1 = 2pi − 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 pi + 1 is one more than the number of zeros for pi. 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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Cunningham Drug (U.S.) — For the unrelated Canadian chain, see Cunningham Drug (Canada). Cunningham Drug Industry retail Fate acquired Successor various Founded October 1889 Defunct 1991 He …   Wikipedia

  • Cunningham Drug Stores Ltd. — Cunningham Drug Stores Ltd. (Cunningham s for short) was a regional Canadian pharmacy chain, based in British Columbia.Cunningham s was established in 1911 when New Westminster native George Cunningham, a druggist formerly employed by the… …   Wikipedia

  • Cunningham Shore Motel — (Lakes Entrance,Австралия) Категория отеля: 3,5 звезд Адрес: 639 Esplanade, 3 …   Каталог отелей

  • Cunningham Drug (Canada) — For the unrelated chain based in Detroit, see Cunningham Drug (U.S.). Cunningham Drug Stores Ltd. Former type Pharmacy chain Industry Pharmacy Fate Chain purchased by Shoppers Drug Mart Founded 1911 …   Wikipedia

  • Chaine de Cunningham — Chaîne de Cunningham Pour les articles homonymes, voir Cunningham. En mathématiques, une chaîne de Cunningham est une certaine suite de nombres premiers. Les chaînes de Cunningham furent nommées en l honneur du mathématicien Allan Joseph… …   Wikipédia en Français

  • Chaîne De Cunningham — Pour les articles homonymes, voir Cunningham. En mathématiques, une chaîne de Cunningham est une certaine suite de nombres premiers. Les chaînes de Cunningham furent nommées en l honneur du mathématicien Allan Joseph Champneys Cunningham (1842… …   Wikipédia en Français

  • Chaîne de cunningham — Pour les articles homonymes, voir Cunningham. En mathématiques, une chaîne de Cunningham est une certaine suite de nombres premiers. Les chaînes de Cunningham furent nommées en l honneur du mathématicien Allan Joseph Champneys Cunningham (1842… …   Wikipédia en Français

  • Chaîne de Cunningham — Pour les articles homonymes, voir Cunningham. En mathématiques, une chaîne de Cunningham est une certaine suite de nombres premiers. Les chaînes de Cunningham furent nommées en l honneur du mathématicien Allan Cunningham (en) (1842 1928) …   Wikipédia en Français

  • George T. Cunningham — was the founder of Cunningham s, the 52 store pharmacy chain that later became Shoppers Drug Mart. Cunningham was also an alderman, a member of the Vancouver School Board and was on the Board of Governors of the University of British Columbia for …   Wikipedia

  • Harry Cunningham — (born 1907 in Pennsylvania died 1992) was an American businessman and retailer who founded Kmart in 1962, a firm that was previously known as S. S. Kresge. Cunningham had a vision to convert the retail chain into a discounter. He worked at Kmart… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”