Cunningham chain

Last updated March 18, 2023

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 (p₁, ..., p_n) such that p_i+1 = 2p_i + 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

{\begin{aligned}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{aligned}}

or, by setting $a={\frac {p_{1}+1}{2}}$ (the number $a$ is not part of the sequence and need not be a prime number), we have $p_{i}=2^{i}a-1.$

Similarly, a Cunningham chain of the second kind of length n is a sequence of prime numbers (p₁, ..., p_n) such that p_i+1 = 2p_i − 1 for all 1 ≤ i < n.

It follows that the general term is

p_{i}=2^{i-1}p_{1}-(2^{i-1}-1).

Now, by setting $a={\frac {p_{1}-1}{2}}$ , we have $p_{i}=2^{i}a+1$ .

Cunningham chains are also sometimes generalized to sequences of prime numbers (p₁, ..., p_n) such that p_i+1 = ap_i + 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 = 11², 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	p₁ (starting prime)	Digits	Year	Discoverer
1	1st / 2nd	2^82589933 − 1	24862048	2018	Patrick Laroche, GIMPS
2	1st	2618163402417×2^1290000 − 1	388342	2016	PrimeGrid
2	2nd	213778324725×2⁵⁶¹⁴¹⁷ + 1	169015	2023	Ryan Propper & Serge Batalov
3	1st	1128330746865×2⁶⁶⁴³⁹ − 1	20013	2020	Michael Paridon
3	2nd	742478255901×2⁴⁰⁰⁶⁷ + 1	12074	2016	Michael Angel & Dirk Augustin
4	1st	13720852541×7877# − 1	3384	2016	Michael Angel & Dirk Augustin
4	2nd	49325406476×9811# + 1	4234	2019	Oscar Östlin
5	1st	31017701152691334912×4091# − 1	1765	2016	Andrey Balyakin
5	2nd	181439827616655015936×4673# + 1	2018	2016	Andrey Balyakin
6	1st	2799873605326×2371# - 1	1016	2015	Serge Batalov
6	2nd	52992297065385779421184×1531# + 1	668	2015	Andrey Balyakin
7	1st	82466536397303904×1171# − 1	509	2016	Andrey Balyakin
7	2nd	25802590081726373888×1033# + 1	453	2015	Andrey Balyakin
8	1st	89628063633698570895360×593# − 1	265	2015	Andrey Balyakin
8	2nd	2373007846680317952×761# + 1	337	2016	Andrey Balyakin
9	1st	553374939996823808×593# − 1	260	2016	Andrey Balyakin
9	2nd	173129832252242394185728×401# + 1	187	2015	Andrey Balyakin
10	1st	3696772637099483023015936×311# − 1	150	2016	Andrey Balyakin
10	2nd	2044300700000658875613184×311# + 1	150	2016	Andrey Balyakin
11	1st	73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	Primecoin (block 95569)
11	2nd	341841671431409652891648×311# + 1	149	2016	Andrey Balyakin
12	1st	288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 1	113	2014	Primecoin (block 558800)
12	2nd	906644189971753846618980352×233# + 1	121	2015	Andrey Balyakin
13	1st	106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1	107	2014	Primecoin (block 368051)
13	2nd	38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 1	101	2014	Primecoin (block 539977)
14	1st	4631673892190914134588763508558377441004250662630975370524984655678678526944768×47# − 1	97	2018	Primecoin (block 2659167)
14	2nd	5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1	100	2014	Primecoin (block 547276)
15	1st	14354792166345299956567113728×43# - 1	45	2016	Andrey Balyakin
15	2nd	67040002730422542592×53# + 1	40	2016	Andrey Balyakin
16	1st	91304653283578934559359	23	2008	Jaroslaw Wroblewski
16	2nd	2×1540797425367761006138858881 − 1	28	2014	Chermoni & Wroblewski
17	1st	2759832934171386593519	22	2008	Jaroslaw Wroblewski
17	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^[update], 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 $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 base "shifts" the digits to the left; e.g. in decimal we have 314 × 10 = 3140.) 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}=2p_{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.

Similarly, because $p_{i}=2^{i-1}p_{1}+(2^{i-1}-1)\,$ it follows that $p_{i}\equiv 2^{i-1}-1{\pmod {p_{1}}}$ . But, by Fermat's little theorem, $2^{p_{1}-1}\equiv 1{\pmod {p_{1}}}$ , so $p_{1}$ divides $p_{p_{1}}$ (i.e. with $i=p_{1}$ ). Thus, no Cunningham chain can be of infinite length.^[3]

Related Research Articles

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number $, which in modular arithmetic satisfies the congruence relation:$

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.

The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence.

In mathematics, the Euler numbers are a sequence E_n of integers defined by the Taylor series expansion

In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form

This article collects together a variety of proofs of Fermat's little theorem, which states that

The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.

In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite (called pseudoprimes), the condition is generally chosen in order to make such exceptions rare.

In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

In number theory, quadratic Gauss sums are certain finite sums of roots of unity. A quadratic Gauss sum can be interpreted as a linear combination of the values of the complex exponential function with coefficients given by a quadratic character; for a general character, one obtains a more general Gauss sum. These objects are named after Carl Friedrich Gauss, who studied them extensively and applied them to quadratic, cubic, and biquadratic reciprocity laws.

Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exchange and RSA public/private keys.

A divisibility rule is a shorthand and useful way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits. Although there are divisibility tests for numbers in any radix, or base, and they are all different, this article presents rules and examples only for decimal, or base 10, numbers. Martin Gardner explained and popularized these rules in his September 1962 "Mathematical Games" column in Scientific American.

Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.

In number theory the Agoh–Giuga conjecture on the Bernoulli numbers B_k postulates that p is a prime number if and only if

A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes".

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity.

In mathematics, Pépin's test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth's test. The test is named for a French mathematician, Théophile Pépin.

In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain, in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing followed quickly.

References

↑ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
1 2 Norman Luhn & Dirk Augustin, Cunningham Chain records. Retrieved on 2018-06-08.
↑ 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 .

External links

The Prime Glossary: Cunningham chain
Primecoin discoveries (primes.zone): online database of primecoin findings with list of records and visualization
PrimeLinks++: Cunningham chain
OEIS sequenceA005602(Smallest prime beginning a complete Cunningham chain of length n (of the first kind)) -- the first term of the lowest complete Cunningham chains of the first kind of length n, for 1 ≤ n ≤ 14
OEIS sequenceA005603(Chains of length n of nearly doubled primes) -- the first term of the lowest complete Cunningham chains of the second kind with length n, for 1 ≤ n ≤ 15

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290

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

[1]

[2]

[3]

v t e Prime number classes
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partitions Bell Motzkin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient Unique
Base-dependent	Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Minimal Delicate Primeval Full reptend Unique Happy Self Smarandache–Wellin Strobogrammatic Dihedral Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k-tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain/Safe ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Mega (1,000,000+ digits) Largest known list
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Somer–Lucas Strong Carmichael number Almost prime Semiprime Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers