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.

One application for Cunningham chains is using computing power to identify them, in order to generate virtual currency, similar to how Bitcoin is mined.[1]

Definition

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

It follows that

or, by setting (the number is not part of the sequence and need not be a prime number), we have

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

It follows that the general term is

Now, by setting , we have .

Cunningham chains are also sometimes generalized to sequences of prime numbers (p1, ..., pn) such that pi+1 = api + b for all 1  i  n for fixed coprime integers a and 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 and the next terms in the chain are not prime numbers.

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.)

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."[2]

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 – the Green–Tao theorem, that there are arithmetic progressions of primes of arbitrary length – there is no general result known on large Cunningham chains to date.

Largest known Cunningham chain of length k (as of 5 June 2018[3])
kKindp1 (starting prime)DigitsYearDiscoverer
11st / 2nd282589933 − 1248620482020Curtis Cooper, GIMPS
21st2618163402417×21290000 − 13883422016PrimeGrid
2nd7775705415×2175115 + 1527252017Serge Batalov
31st1815615642825×244044 − 1132712016Serge Batalov
2nd742478255901×240067 + 1120742016Michael Angel & Dirk Augustin
41st13720852541×7877# − 133842016Michael Angel & Dirk Augustin
2nd17285145467×6977# + 130052016Michael Angel & Dirk Augustin
51st31017701152691334912×4091# − 117652016Andrey Balyakin
2nd181439827616655015936×4673# + 120182016Andrey Balyakin
61st2799873605326×2371# - 110162015Serge Batalov
2nd52992297065385779421184×1531# + 16682015Andrey Balyakin
71st82466536397303904×1171# − 15092016Andrey Balyakin
2nd25802590081726373888×1033# + 14532015Andrey Balyakin
81st89628063633698570895360×593# − 12652015Andrey Balyakin
2nd2373007846680317952×761# + 13372016Andrey Balyakin
91st553374939996823808×593# − 12602016Andrey Balyakin
2nd173129832252242394185728×401# + 11872015Andrey Balyakin
101st3696772637099483023015936×311# − 11502016Andrey Balyakin
2nd2044300700000658875613184×311# + 11502016Andrey Balyakin
111st73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 11402013Primecoin (block 95569)
2nd341841671431409652891648×311# + 11492016Andrey Balyakin
121st288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 11132014Primecoin (block 558800)
2nd906644189971753846618980352×233# + 11212015Andrey Balyakin
131st106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 11072014Primecoin (block 368051)
2nd38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 11012014Primecoin (block 539977)
141st4631673892190914134588763508558377441004250662630975370524984655678678526944768×47# − 1972018Primecoin (block 2659167)
2nd5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 11002014Primecoin (block 547276)
151st14354792166345299956567113728×43# - 1452016Andrey Balyakin
2nd67040002730422542592×53# + 1402016Andrey Balyakin
161st91304653283578934559359232008Jaroslaw Wroblewski
2nd2×1540797425367761006138858881 − 1282014Chermoni & Wroblewski
171st2759832934171386593519222008Jaroslaw Wroblewski
2nd1540797425367761006138858881282014Chermoni & Wroblewski
182nd658189097608811942204322721272014Chermoni & Wroblewski
192nd79910197721667870187016101262014Chermoni & Wroblewski

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

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

Congruences of Cunningham chains

Let the odd prime be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus . Since each successive prime in the chain is it follows that . Thus, , , 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 base "shifts" the digits to the left; e.g. in decimal we have 314×10 = 3140.) When we consider   in base 2, we see that, by multiplying   by 2, the least significant digit of   becomes the secondmost least significant digit of  . Because is odd—that is, the least significant digit is 1 in base 2–we know that the secondmost least significant digit of   is also 1. And, finally, we can see that   will be odd due to the addition of 1 to . 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:

BinaryDecimal
1000011011010000000100111101141361469
10000110110100000001001111011282722939
100001101101000000010011110111565445879
10000110110100000001001111011111130891759
100001101101000000010011110111112261783519
1000011011010000000100111101111114523567039

A similar result holds for Cunningham chains of the second kind. From the observation that and the relation it follows that . In binary notation, the primes in a Cunningham chain of the second kind end with a pattern "0...01", where, for each , the number of zeros in the pattern for is one more than the number of zeros for . 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 it follows that . But, by Fermat's little theorem, , so divides (i.e. with ). Thus, no Cunningham chain can be of infinite length.[4]

See also

References

  1. "Cunningham Chains Mining" (PDF). lirmm.fr. Retrieved 2018-11-07.
  2. Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
  3. Dirk Augustin, Cunningham Chain records. Retrieved on 2018-06-08.
  4. Löh, Günter (October 1989). "Long chains of nearly doubled primes". Mathematics of Computation. 53 (188): 751–759. doi:10.1090/S0025-5718-1989-0979939-8.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.