Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

Цепь Каннингема (цепь почти удвоенных чисел) —последовательность простых чисел определённого вида, названо в честьматематика .
Цепь Каннингема первого рода длины 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. Как и в случае чисел первого рода, биты слева от этих сдвигаютсявлево на одну позицию в каждом последующем члене цепи.