A Cunningham chain of the first kind of length n is a sequence of prime numbers (p1,...,pn) such that for all 1 ≤ i < n, pi+1 = 2 pi + 1. (Hence each term of such a chain except the last one is a Sophie Germain prime, and each term except the first is a safe prime).
It follows that, ..., .
Similarly, a Cunningham chain of the second kind of length n is a sequence of prime numbers (p1,...,pn) such that for all 1 ≤ i < n, pi+1 = 2 pi - 1.
Cunningham chains are also sometimes generalized to sequences of prime numbers (p1,...,pn) such that for all 1 ≤ i < n, pi+1 = api + b for fixed coprime integers a, 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 or next term in the chain would not be a prime number anymore.
Cunningham chains are now considered useful in cryptographic systems since "they provide two concurrent suitable settings for the ElGamal cryptosystem ... can be implemented in any field where the discrete logarithm problem is difficult."
Other articles related to "cunningham chain, chain":
... Let the odd prime be the first prime of a Cunningham chain of the first kind ... Since each successive prime in the chain is it follows that ... above property can be informally observed by considering the primes of a chain in base 2 ...
Famous quotes containing the words chain and/or cunningham:
“Nae living man Ill love again,
Since that my lovely knight is slain.
Wi ae lock of his yellow hair
Ill chain my heart for evermair.”
—Unknown. The Lament of the Border Widow (l. 2528)
“A wet sheet and a flowing sea,
A wind that follows fast
And fills the white and rustling sail
And bends the gallant mast;”
—Allan Cunningham (17841842)