Последовательности Куннингама

Цепь Каннингема (цепь почти удвоенных чисел) — последовательность простых чисел определённого вида, названо в честь математика .
Цепь Каннингема первого рода длины n — это последовательность простых чисел (p1,\ldots,pn), таких что для всех 1 ≤ i \textless n, pi+1 = 2 pi + 1 (следовательно, каждый член этой цепи, за исключением последнего, является числом Софи Жермен, а за исключением первого — безопасным простым числом): p2=2p1+1, p3=4p1+3, p4=8p1+7, \ldots, pi=2i1p1+(2i11).
Цепь Каннингема второго рода длины n — это последовательность простых чисел (p1,\ldots,pn), таких что для всех 1 ≤ i \textless n, pi+1 = 2 pi — 1 : pi=2i1p1+(2i1+1)
 Цепи Каннингема иногда обобщают как последовательность простых чисел (p1,\ldots,pn), таких что для всех 1 ≤ i \textless n, pi+1 = api + b для фиксированных взаимно простых целых a, b. Такая цепь называется обобщённой цепью Каннингема.
 Цепь Каннингема называется полной, если не может быть продолжена, то есть если предшествующий и последующий член последовательности не будут простыми.
 Цепи Каннингема сейчас признаны полезными для криптографических систем, поскольку «они обеспечивают две конкурентные приемлемые установки для схемы шифрования Эль-Гамаля, которые могут быть использованы в любом месте, где проблема вычисления дискретного логарифма трудна».

Самые большие известные цепи Каннингема


 Согласно гипотезе Диксона и более общей гипотезе H Шинцеля, большинством учёных полагающимся верными, для любого k имеется бесконечное число цепей Каннингема длины k. Нет, однако, известного метода генерации таких цепей.
BinaryDecimal
1000011011010000000100111101141361469
10000110110100000001001111011282722939
100001101101000000010011110111565445879
10000110110100000001001111011111130891759
100001101101000000010011110111112261783519
1000011011010000000100111101111114523567039

 Аналогичный результат можно получить и для цепей второго рода. Заметим, что из p11(mod2) и отношения pi+1=2pi1 следует, что pi1(mod2i). В двоичной записи простые числа в цепи Каннингема второго рода кончаются на «0\ldots01», где для любого i число нулей для pi+1 на единицу больше числа нулей pi. Как и в случае чисел первого рода, биты слева от этих сдвигаются влево на одну позицию в каждом последующем члене цепи.