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

В математике цепи Куннигама — это некоторая последовательность простых чисел. Цепи Куннигана названы в честь математика А. Дж. Ч. Каннингема (англ.)русск.. Их также называют цепями почти удвоенных чисел.

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

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

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

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

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

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

k	Тип	p1 (начальное простое)	Число цифр	Год	Обнаружил
1	1st	243112609 − 1	12978189	2008	GIMPS / Edson Smith
2	1st	183027×2265440 − 1	79911	2010	T. Wu
3	1st	914546877×234772 − 1	10477	2010	T. Wu
4	1st	119184698×5501# − 1	2354	2005	J. Sun
5	2nd	45008010405×2621# + 1	1116	2010	D. Broadhurst
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	2nd	1070828503293×239# + 1	109	2009	D. Augustin
11	2nd	2×13931865163581×127# + 1	63	2008	D. Augustin
12	2nd	13931865163581×127# + 1	62	2008	D. Augustin
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# обозначает the примориал 2×3×5×7×…×q.

К 2011 году самая большая известная цепь Куннигама любого рода имеет длину 17. Первая найдена была цепь первого рода, начинающаяся с 2759832934171386593519, (найдена Ярославом Вроблевским в 2008 where he also found some of the 2nd kind.^[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} = 2 p_i - 1$ следует, что $p_i \equiv 1 \pmod{2^i}$. В двоичной записи простые числа в цепи Куннигама второго рода кончаются на «0…01», где для любого $i$ число нулей для $p_{i+1}$ на единицу больше числа нулей $p_i$. Как и в случае чисел первого рода, биты слева от этих сдвигаются влево на одну позицию в каждом последующес члене цепи.

Ссылки

1. ↑ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
2. ↑ ^{1 2} Dirk Augustin, Cunningham Chain records. Retrieved on 2011-11-08.

Ссылки

• The Prime Glossary: Cunningham chain
• PrimeLinks++: Cunningham chain
• Sequence A005602 in OEIS: Первый член минимальной полной цепи Куннигама первого рода длины n, for 1 <= n <= 14
• Sequence A005603 in OEIS: Первый член минимальной полной цепи Куннигама второго рода длины n, for 1 <= n <= 15