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

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

Цепь Каннингема первого рода длины n — это последовательность простых чисел (p₁,…,p_n), таких что для всех 1 ≤ i < n, p_i+1 = 2 p_i + 1 (следовательно, каждый член этой цепи, за исключением последнего, является числом Софи Жермен, а за исключением первого — безопасным простым числом): $p_{2}=2p_{1}+1$ , $p_{3}=4p_{1}+3$ , $p_{4}=8p_{1}+7$ , …, $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 : $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	Тип	p₁ (начальное простое)	Число цифр	Год	Обнаружил
1		2^57885161 − 1	17425170	2013	GIMPS / Curtis Cooper
2	1st	183027×2²⁶⁵⁴⁴⁰ − 1	200701	2012	T. Wu
3	1st	914546877×2³⁴⁷⁷² − 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]

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

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

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

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

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

Примечания

↑ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
↑ ¹ ² Dirk Augustin, Cunningham Chain records Архивная копия от 12 октября 2014 на Wayback Machine. Retrieved on 2011-11-08.

Ссылки

The Prime Glossary: Cunningham chain
PrimeLinks++: Cunningham chain
последовательность A005602 в OEIS: первый член минимальной полной цепи Каннингема первого рода длины $n$ , для $1\leq n\leq 14$
последовательность A005603 в OEIS: первый член минимальной полной цепи Куннингама второго рода длины $n$ , для $1\leq n\leq 15$

[1] Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290

[records-2] ¹ ² Dirk Augustin, Cunningham Chain records Архивная копия от 12 октября 2014 на Wayback Machine. Retrieved on 2011-11-08.

[1]

[2]