Cunningham Chain

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 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."

Read more about Cunningham ChainLargest Known Cunningham Chains, Congruences of Cunningham Chains

Other articles related to "cunningham chain, chain":

chains" class="article_title_2">Congruences of Cunningham Chains
... 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 I’ll love again,
    Since that my lovely knight is slain.
    Wi ae lock of his yellow hair
    I’ll chain my heart for evermair.
    —Unknown. The Lament of the Border Widow (l. 25–28)

    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 (1784–1842)