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 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 of complete Cunningham chains of the first kind include these:
Examples of complete Cunningham chains of the second kind include these:
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]
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.
k | Kind | p1 (starting prime) | Digits | Year | Discoverer |
---|---|---|---|---|---|
1 | 1st / 2nd | 2136279841 − 1 | 41024320 | 2024 | Luke Durant, 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 | 214923707595×249073 + 1 | 14784 | 2025 | Serge Batalov | |
4 | 1st | 13720852541×7877# − 1 | 3384 | 2016 | Michael Angel & Dirk Augustin |
2nd | 49325406476×9811# + 1 | 4234 | 2019 | Oscar Östlin | |
5 | 1st | 475676794046977267×4679# − 1 | 2019 | 2024 | Andrey Balyakin |
2nd | 181439827616655015936×4673# + 1 | 2018 | 2016 | Andrey Balyakin | |
6 | 1st | 2799873605326×2371# - 1 | 1016 | 2015 | Serge Batalov |
2nd | 37015322207094×2339# + 1 | 1001 | 2025 | Serge Batalov | |
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 [update] , the longest known Cunningham chain of either kind is of length 19, discovered by Jaroslaw Wroblewski in 2014. [2]
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:
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 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. [3]
In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of 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.
In number theory, Fermat's little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
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, the condition is generally chosen in order to make such exceptions rare.
In modular arithmetic, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gk ≡ a. Such a value k is called the index or discrete logarithm of a to the base g modulo n. So g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n.
In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is, the factorial satisfies
In number theory, a Wieferich prime is a prime number p such that p2 divides 2p − 1 − 1, therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides 2p − 1 − 1. Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's Last Theorem, at which time both of Fermat's theorems were already well known to mathematicians.
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.
In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.
In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that n is prime.
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.
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.
In number theory the Agoh–Giuga conjecture on the Bernoulli numbers Bk 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 mathematics, Wolstenholme's theorem states that for a prime number p ≥ 5, the congruence
In number theory, a branch of mathematics, the Carmichael functionλ(n) of a positive integer n is the smallest positive integer m such that
In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:
The digital root of a natural number in a given radix is the value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached. For example, in base 10, the digital root of the number 12345 is 6 because the sum of the digits in the number is 1 + 2 + 3 + 4 + 5 = 15, then the addition process is repeated again for the resulting number 15, so that the sum of 1 + 5 equals 6, which is the digital root of that number. In base 10, this is equivalent to taking the remainder upon division by 9, which allows it to be used as a divisibility rule.
In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer. The test uses a partial factorization of to prove that an integer is prime.