Цепь Каннингема

Цепь Каннингема (цепь почти удвоенных чисел) — последовательность простых чисел определённого вида, названо в честь математика Алана Каннингема^[англ.].

Цепь Каннингема первого рода длины n — это последовательность простых чисел (p₁,…,p_n), таких что для всех 1 ≤ i < n, p_i+1 = 2 p_i + 1 (следовательно, каждый член этой цепи, за исключением последнего, является числом Софи Жермен, а за исключением первого — безопасным простым числом): ${\displaystyle p_{2}=2p_{1}+1}$, ${\displaystyle p_{3}=4p_{1}+3}$, ${\displaystyle p_{4}=8p_{1}+7}$, …, ${\displaystyle p_{i}=2^{i-1}p_{1}+(2^{i-1}-1)}$.

Цепь Каннингема второго рода длины n — это последовательность простых чисел (p₁,…,p_n), таких что для всех 1 ≤ i < n, p_i+1 = 2 p_i — 1 : ${\displaystyle p_{i}=2^{i-1}p_{1}+(2^{i-1}+1)}$

Цепи Каннингема иногда обобщают как последовательность простых чисел (p₁,…,p_n), таких что для всех 1 ≤ i < n, p_i+1 = ap_i + b для фиксированных взаимно простых целых a, b. Такая цепь называется обобщённой цепью Каннингема.

Цепь Каннингема называется полной, если не может быть продолжена, то есть если предшествующий и последующий член последовательности не будут простыми.

Цепи Каннингема сейчас признаны полезными для криптографических систем, поскольку «они обеспечивают две конкурентные приемлемые установки для схемы шифрования Эль-Гамаля, которые могут быть использованы в любом месте, где проблема вычисления дискретного логарифма трудна»^[1].

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

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

Самая большая известная цепь Каннингема длины k на 06/08/2013^[2])

k	Тип	p1 (начальное простое)	Число цифр	Год	Обнаружил
1		257885161 − 1	17425170	2013	GIMPS / Curtis Cooper
2	1st	183027×2265440 − 1	200701	2012	T. Wu
3	1st	914546877×234772 − 1	10477	2010	T. Wu
4	1st	1249097877×6599# − 1	2835	2011	Michael Angel
5	1st	4250172704×2749# − 1	1183	2012	D. Augustin
6	1st	37488065464×1483# − 1	633	2010	D. Augustin
7	1st	162597166369×827# − 1	356	2010	D. Augustin
8	2nd	1148424905221×509# + 1	224	2010	D. Augustin
9	1st	65728407627×431# − 1	185	2005	D. Augustin
10	1st	2×73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	Primecoin
11	1st	73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	Primecoin
12	2nd	263663326886409378473341387047271336974122837948496277769621396327294641140893808×43# + 1	97	2013	Primecoin
13	1st	1753286498051×71# − 1	39	2005	D. Augustin
14	2nd	335898524600734221050749906451371	33	2008	J. K. Andersen
15	2nd	28320350134887132315879689643841	32	2008	J. Wroblewski
16	2nd	2368823992523350998418445521	28	2008	J. Wroblewski
17	2nd	1302312696655394336638441	25	2008	J. Wroblewski

q# обозначает примориал 2×3×5×7×…×q.

К 2011 году самая большая известная цепь Каннингема любого рода имеет длину 17. Первая найдена была цепь первого рода, начинающаяся с 2759832934171386593519, (найдена Ярославом Вроблевским в 2008 году).^[2]

Совмещаемость цепей Каннингема

Пусть нечётное простое число ${\displaystyle p_{1}}$ — первое число в цепи Каннингема первого рода. Поскольку первое число нечётное, ${\displaystyle p_{1}\equiv 1{\pmod {2}}}$. Так как все последующие числа в цепи равны ${\displaystyle p_{i+1}=2p_{i}+1}$, то ${\displaystyle p_{i}\equiv 2^{i}-1{\pmod {2^{i}}}}$. Отсюда, ${\displaystyle p_{2}\equiv 3{\pmod {4}}}$, ${\displaystyle p_{3}\equiv 7{\pmod {8}}}$, и так далее.

Это свойство неформально можно наблюдать при представлении чисел в двоичном виде (заметьте, что для любого основания умножение числа на основание приводит к сдвигу цифр влево) Если мы представим ${\displaystyle p_{i+1}=2p_{i}+1}$ в двоичном виде, мы увидим, что при умножении ${\displaystyle p_{i}}$ на 2 младший знак числа ${\displaystyle p_{i}}$ становится вторым знаком числа ${\displaystyle p_{i+1}}$. Поскольку ${\displaystyle p_{i}}$ нечетно, младший знак равен 1 и он становится вторым справа знаком ${\displaystyle p_{i+1}}$. И, наконец, мы видим, что ${\displaystyle p_{i+1}}$ станет нечётным при прибавлении 1 к ${\displaystyle 2p_{i}}$. Таким образом, производные простые в цепи Каннингема получаются сдвигом двоичного числа влево на одну позицию и заполнением освободившейся позиции единицей. Для примера приводим полную цепь длины 6, начинающуюся с 141361469:

Binary	Decimal
1000011011010000000100111101	141361469
10000110110100000001001111011	282722939
100001101101000000010011110111	565445879
1000011011010000000100111101111	1130891759
10000110110100000001001111011111	2261783519
100001101101000000010011110111111	4523567039

Аналогичный результат можно получить и для цепей второго рода. Заметим, что из ${\displaystyle p_{1}\equiv 1{\pmod {2}}}$ и отношения ${\displaystyle p_{i+1}=2p_{i}-1}$ следует, что ${\displaystyle p_{i}\equiv 1{\pmod {2^{i}}}}$. В двоичной записи простые числа в цепи Каннингема второго рода кончаются на «0…01», где для любого ${\displaystyle i}$ число нулей для ${\displaystyle p_{i+1}}$ на единицу больше числа нулей ${\displaystyle p_{i}}$. Как и в случае чисел первого рода, биты слева от этих сдвигаются влево на одну позицию в каждом последующем члене цепи.