Cunningham chain

From HandWiki

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.

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

[math]\displaystyle{ \begin{align} p_2 & = 2p_1+1, \\ p_3 & = 4p_1+3, \\ p_4 & = 8p_1+7, \\ & {}\ \vdots \\ p_i & = 2^{i-1}p_1 + (2^{i-1}-1), \end{align} }[/math]

or, by setting [math]\displaystyle{ a = \frac{p_1 + 1}{2} }[/math] (the number [math]\displaystyle{ a }[/math] is not part of the sequence and need not be a prime number), we have [math]\displaystyle{ p_i = 2^{i} a - 1. }[/math]

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

[math]\displaystyle{ p_i = 2^{i-1}p_1 - (2^{i-1}-1). }[/math]

Now, by setting [math]\displaystyle{ a = \frac{p_1 - 1}{2} }[/math], we have [math]\displaystyle{ p_i = 2^{i} a + 1 }[/math].

Cunningham chains are also sometimes generalized to sequences of prime numbers (p1, ..., pn) such that pi+1api + 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."[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.

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 17 March 2023[2])
k Kind p1 (starting prime) Digits Year Discoverer
1 1st / 2nd 282589933 − 1 24862048 2018 Patrick Laroche, GIMPS
2 1st 2618163402417×21290000 − 1 388342 2016 PrimeGrid
2nd 213778324725×2561417 + 1 169015 2023 Ryan Propper & Serge Batalov
3 1st 1128330746865×266439 − 1 20013 2020 Michael Paridon
2nd 742478255901×240067 + 1 12074 2016 Michael Angel & Dirk Augustin
4 1st 13720852541×7877# − 1 3384 2016 Michael Angel & Dirk Augustin
2nd 49325406476×9811# + 1 4234 2019 Oscar Östlin
5 1st 31017701152691334912×4091# − 1 1765 2016 Andrey Balyakin
2nd 181439827616655015936×4673# + 1 2018 2016 Andrey Balyakin
6 1st 2799873605326×2371# - 1 1016 2015 Serge Batalov
2nd 52992297065385779421184×1531# + 1 668 2015 Andrey Balyakin
7 1st 82466536397303904×1171# − 1 509 2016 Andrey Balyakin
2nd 25802590081726373888×1033# + 1 453 2015 Andrey Balyakin
8 1st 89628063633698570895360×593# − 1 265 2015 Andrey Balyakin
2nd 2373007846680317952×761# + 1 337 2016 Andrey Balyakin
9 1st 553374939996823808×593# − 1 260 2016 Andrey Balyakin
2nd 173129832252242394185728×401# + 1 187 2015 Andrey Balyakin
10 1st 3696772637099483023015936×311# − 1 150 2016 Andrey Balyakin
2nd 2044300700000658875613184×311# + 1 150 2016 Andrey Balyakin
11 1st 73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1 140 2013 Primecoin (block 95569)
2nd 341841671431409652891648×311# + 1 149 2016 Andrey Balyakin
12 1st 288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 1 113 2014 Primecoin (block 558800)
2nd 906644189971753846618980352×233# + 1 121 2015 Andrey Balyakin
13 1st 106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1 107 2014 Primecoin (block 368051)
2nd 38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 1 101 2014 Primecoin (block 539977)
14 1st 4631673892190914134588763508558377441004250662630975370524984655678678526944768×47# − 1 97 2018 Primecoin (block 2659167)
2nd 5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1 100 2014 Primecoin (block 547276)
15 1st 14354792166345299956567113728×43# - 1 45 2016 Andrey Balyakin
2nd 67040002730422542592×53# + 1 40 2016 Andrey Balyakin
16 1st 91304653283578934559359 23 2008 Jaroslaw Wroblewski
2nd 2×1540797425367761006138858881 − 1 28 2014 Chermoni & Wroblewski
17 1st 2759832934171386593519 22 2008 Jaroslaw Wroblewski
2nd 1540797425367761006138858881 28 2014 Chermoni & Wroblewski
18 2nd 658189097608811942204322721 27 2014 Chermoni & Wroblewski
19 2nd 79910197721667870187016101 26 2014 Chermoni & 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.[2]

Congruences of Cunningham chains

Let the odd prime [math]\displaystyle{ p_1 }[/math] be the first prime of a Cunningham chain of the first kind. The first prime is odd, thus [math]\displaystyle{ p_1 \equiv 1 \pmod{2} }[/math]. Since each successive prime in the chain is [math]\displaystyle{ p_{i+1} = 2p_i + 1 }[/math] it follows that [math]\displaystyle{ p_i \equiv 2^i - 1 \pmod{2^i} }[/math]. Thus, [math]\displaystyle{ p_2 \equiv 3 \pmod{4} }[/math], [math]\displaystyle{ p_3 \equiv 7 \pmod{8} }[/math], 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  [math]\displaystyle{ p_{i+1} = 2p_i + 1 }[/math] in base 2, we see that, by multiplying  [math]\displaystyle{ p_i }[/math] by 2, the least significant digit of  [math]\displaystyle{ p_i }[/math] becomes the secondmost least significant digit of  [math]\displaystyle{ p_{i+1} }[/math]. Because [math]\displaystyle{ p_i }[/math] is odd—that is, the least significant digit is 1 in base 2–we know that the secondmost least significant digit of  [math]\displaystyle{ p_{i+1} }[/math] is also 1. And, finally, we can see that  [math]\displaystyle{ p_{i+1} }[/math] will be odd due to the addition of 1 to [math]\displaystyle{ 2p_i }[/math]. 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 [math]\displaystyle{ p_1 \equiv 1 \pmod{2} }[/math] and the relation [math]\displaystyle{ p_{i+1} = 2 p_i - 1 }[/math] it follows that [math]\displaystyle{ p_i \equiv 1 \pmod{2^i} }[/math]. In binary notation, the primes in a Cunningham chain of the second kind end with a pattern "0...01", where, for each [math]\displaystyle{ i }[/math], the number of zeros in the pattern for [math]\displaystyle{ p_{i+1} }[/math] is one more than the number of zeros for [math]\displaystyle{ p_i }[/math]. 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 [math]\displaystyle{ p_i = 2^{i-1}p_1 + (2^{i-1}-1) \, }[/math] it follows that [math]\displaystyle{ p_i \equiv 2^{i-1} - 1 \pmod{p_1} }[/math]. But, by Fermat's little theorem, [math]\displaystyle{ 2^{p_1-1} \equiv 1 \pmod{p_1} }[/math], so [math]\displaystyle{ p_1 }[/math] divides [math]\displaystyle{ p_{p_1} }[/math] (i.e. with [math]\displaystyle{ i = p_1 }[/math]). Thus, no Cunningham chain can be of infinite length.[3]

See also

References

  1. Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
  2. 2.0 2.1 Norman Luhn & Dirk Augustin, Cunningham Chain records. Retrieved on 2018-06-08.
  3. 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. https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979939-8/. 

External links