Interested Article - Цепь Каннингема

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

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

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

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

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

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

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

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

Самая большая известная цепь Каннингема длины k на 06/08/2013 )
k Тип p 1 (начальное простое) Число цифр Год Обнаружил
1 2 57885161 − 1 17425170 2013 GIMPS / Curtis Cooper
2 1st 183027×2 265440 − 1 200701 2012 T. Wu
3 1st 914546877×2 34772 − 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 году).

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

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

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

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

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

Примечания

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

Ссылки

  • последовательность в OEIS : первый член минимальной полной цепи Каннингема первого рода длины n {\displaystyle n} , для 1 n 14 {\displaystyle 1\leq n\leq 14}
  • последовательность в OEIS : первый член минимальной полной цепи Куннингама второго рода длины n {\displaystyle n} , для 1 n 15 {\displaystyle 1\leq n\leq 15}

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