Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Cunningham chain
Summary
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:
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 .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.