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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Цепь Каннингема первого рода длины n — это последовательность простых чисел (p1,…,pn), таких что для всех 1 ≤ i < n, pi+1 = 2 pi + 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 — это последовательность простых чисел (p1,…,pn), таких что для всех 1 ≤ i < n, pi+1 = 2 pi — 1 :  p_i = 2^{i-1}p_1 + (2^{i-1}+1) \,

Цепи Каннингема иногда обобщают как последовательность простых чисел (p1,…,pn), таких что для всех 1 ≤ i < n, pi+1 = api + 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]

Совмещаемость цепей Каннингема[править | править исходный текст]

Пусть нечётное простое число 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
  • последовательность A005602 в OEIS: первый член минимальной полной цепи Каннингема первого рода длины n, для 1 \le n \le 14
  • последовательность A005603 в OEIS: первый член минимальной полной цепи Куннингама второго рода длины n, для 1 \le n \le 15