Сеть Каннингема

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

Определение

Цепочка Каннингема первого рода длины n — это последовательность простых чисел ( p ₁ , ..., p _n ) такая, что p _{i +1} = 2 p _i + 1 для всех 1 ≤ i < n . (Следовательно, каждый член такой цепочки, кроме последнего, является простым числом Софи Жермен , а каждый член, кроме первого, является безопасным простым числом ).

Отсюда следует, что

{\begin{aligned}p_{2}&=2p_{1}+1,\\p_{3}&=4p_{1}+3,\\p_{4}&=8p_{1}+7,\\&{}\ \vdots \\p_{i}&=2^{i-1}p_{1}+(2^{i-1}-1),\end{aligned}}

или, установив $a={\frac {p_{1}+1}{2}}$ (число $a$ не является частью последовательности и не обязательно должно быть простым числом), мы имеем $p_{i}=2^{i}a-1.$

Аналогично, цепь Каннингема второго рода длины n представляет собой последовательность простых чисел ( p ₁ , ..., p _n ) такую, что p _{i +1} = 2 p _i − 1 для всех 1 ≤ i < n .

Отсюда следует, что общий термин

p_{i}=2^{i-1}p_{1}-(2^{i-1}-1).

Теперь, установив $a={\frac {p_{1}-1}{2}}$ , у нас есть $p_{i}=2^{i}a+1$ .

Цепи Каннингема также иногда обобщаются на последовательности простых чисел ( p ₁ , ..., p _n ) такие, что p _{i +1} = ap _i + b для всех 1 ≤ i ≤ n для фиксированных взаимно простых целых чисел a и b ; полученные цепи называются обобщенными цепями Каннингема .

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

Примеры

Примеры полных цепей Каннингема первого рода включают в себя:

2, 5, 11, 23, 47 (Следующее число будет 95, но оно не простое.)

3, 7 (Следующее число будет 15, но оно не простое.)

29, 59 (Следующее число будет 119, но оно не простое.)

41, 83, 167 (Следующее число будет 335, но оно не простое.)

89, 179, 359, 719, 1439, 2879 (Следующее число будет 5759, но оно не является простым.)

Примеры полных цепей Каннингема второго рода включают в себя:

2, 3, 5 (Следующее число будет 9, но оно не простое.)

7, 13 (Следующее число будет 25, но оно не простое.)

19, 37, 73 (Следующее число будет 145, но оно не простое.)

31, 61 (Следующее число будет 121 = 11 ², но это не простое число.)

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

Крупнейшие известные сети Cunningham

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

Существуют вычислительные соревнования на самую длинную цепочку Каннингема или на цепочку, составленную из самых больших простых чисел, но в отличие от прорыва Бена Дж. Грина и Теренса Тао – теоремы Грина – Тао , о том, что существуют арифметические прогрессии простых чисел произвольной длины – на сегодняшний день не существует общего результата по крупным цепям Каннингема.

Самая большая известная цепочка Каннингема длины k (по состоянию на 17 марта 2023 г.) ^[2])
к	Добрый	п ₁ (начальный штрих)	Цифры	Год	Первооткрыватель
1	1-й/2-й	2 ^82589933 − 1	24862048	2018	Патрик Ларош, GIMPS
2	1-й	2618163402417×2 ^1290000 − 1	388342	2016	ПраймГрид
2	2-й	213778324725×2 ⁵⁶¹⁴¹⁷ + 1	169015	2023	Райан Проппер и Серж Баталов
3	1-й	1128330746865×2 ⁶⁶⁴³⁹ − 1	20013	2020	Майкл Паридон
3	2-й	742478255901×2 ⁴⁰⁰⁶⁷ + 1	12074	2016	Майкл Энджел и Дирк Огюстин
4	1-й	13720852541×7877# − 1	3384	2016	Майкл Энджел и Дирк Огюстин
4	2-й	49325406476×9811# + 1	4234	2019	Оскар Остлин
5	1-й	31017701152691334912×4091# − 1	1765	2016	Андрей Балякин
5	2-й	181439827616655015936×4673# + 1	2018	2016	Андрей Балякин
6	1-й	2799873605326×2371# - 1	1016	2015	Серж Баталов
6	2-й	52992297065385779421184×1531# + 1	668	2015	Андрей Балякин
7	1-й	82466536397303904×1171# − 1	509	2016	Андрей Балякин
7	2-й	25802590081726373888×1033# + 1	453	2015	Андрей Балякин
8	1-й	89628063633698570895360×593# − 1	265	2015	Андрей Балякин
8	2-й	2373007846680317952×761# + 1	337	2016	Андрей Балякин
9	1-й	553374939996823808×593# − 1	260	2016	Андрей Балякин
9	2-й	173129832252242394185728×401# + 1	187	2015	Андрей Балякин
10	1-й	3696772637099483023015936×311# − 1	150	2016	Андрей Балякин
10	2-й	2044300700000658875613184×311# + 1	150	2016	Андрей Балякин
11	1-й	73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	Праймкоин ( блок 95569 )
11	2-й	341841671431409652891648×311# + 1	149	2016	Андрей Балякин
12	1-й	288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 1	113	2014	Праймкоин ( блок 558800 )
12	2-й	906644189971753846618980352×233# + 1	121	2015	Андрей Балякин
13	1-й	106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1	107	2014	Праймкоин ( блок 368051 )
13	2-й	38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 1	101	2014	Праймкоин ( блок 539977 )
14	1-й	4631673892190914134588763508558377441004250662630975370524984655678678526944768×47# − 1	97	2018	Праймкоин ( блок 2659167 )
14	2-й	5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1	100	2014	Праймкоин ( блок 547276 )
15	1-й	14354792166345299956567113728×43# - 1	45	2016	Андрей Балякин
15	2-й	67040002730422542592×53# + 1	40	2016	Андрей Балякин
16	1-й	91304653283578934559359	23	2008	Ярослав Врублевский
16	2-й	2×1540797425367761006138858881 − 1	28	2014	Чермони и Вроблевски
17	1-й	2759832934171386593519	22	2008	Ярослав Врублевский
17	2-й	1540797425367761006138858881	28	2014	Чермони и Вроблевски
18	2-й	658189097608811942204322721	27	2014	Чермони и Вроблевски
19	2-й	79910197721667870187016101	26	2014	Чермони и Вроблевски

q # обозначает первоначальный 2×3×5×7×...× q .

По состоянию на 2018 год ^[update]Самая длинная известная цепь Каннингема любого типа имеет длину 19 и открыта Ярославом Вроблевским в 2014 году. ^[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}}$ и так далее.

Вышеупомянутое свойство можно неофициально наблюдать, рассматривая простые числа цепи по основанию 2 . (Обратите внимание, что, как и во всех системах счисления, умножение на базу «сдвигает» цифры влево; например, в десятичной системе счисления мы имеем 314 × 10 = 3140.) Когда мы рассматриваем $p_{i+1}=2p_{i}+1$ по основанию 2, мы видим, что, умножив $p_{i}$ на 2, младшая значащая цифра $p_{i}$ становится второй наименее значащей цифрой $p_{i+1}$ . Потому что $p_{i}$ нечетно, то есть младшая значащая цифра равна 1 по основанию 2; мы знаем, что вторая наименее значащая цифра $p_{i+1}$ также равно 1. И, наконец, мы видим, что $p_{i+1}$ будет нечетным из-за добавления 1 к $2p_{i}$ . Таким образом, последовательные простые числа в цепочке Каннингема по существу сдвигаются влево в двоичном виде, при этом заполняются младшие значащие цифры. Например, вот полная цепочка длиной 6, которая начинается с 141361469:

Двоичный	десятичный
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}$ . Как и в случае с цепями Каннингема первого рода, биты слева от шаблона смещаются влево на одну позицию с каждым последующим простым числом.

Аналогично, потому что $p_{i}=2^{i-1}p_{1}+(2^{i-1}-1)\,$ отсюда следует, что $p_{i}\equiv 2^{i-1}-1{\pmod {p_{1}}}$ . Но по малой теореме Ферма , $2^{p_{1}-1}\equiv 1{\pmod {p_{1}}}$ , так $p_{1}$ делит $p_{p_{1}}$ (т.е. с $i=p_{1}$ ). Таким образом, ни одна цепь Каннингема не может иметь бесконечную длину. ^[3]

См. также

Primecoin , который использует цепочки Каннингема в качестве системы доказательства работы.
Двойная цепь
Простые числа в арифметической прогрессии

Ссылки

^ Джо Бюлер, Алгоритмическая теория чисел: Третий международный симпозиум, ANTS-III . Нью-Йорк: Спрингер (1998): 290.
^ Jump up to: Перейти обратно: ^а ^б Норман Лун и Дирк Огюстин, Cunningham Chain Records . Проверено 8 июня 2018 г.
^ Лё, Гюнтер (октябрь 1989 г.). «Длинные цепочки почти удвоенных простых чисел» . Математика вычислений . 53 (188): 751–759. дои : 10.1090/S0025-5718-1989-0979939-8 .

Внешние ссылки

Главный глоссарий: сеть Cunningham
Находки Primecoin (primes.zone): онлайн-база данных находок Primecoin со списком записей и визуализацией.
PrimeLinks++: сеть Каннингема
Последовательность OEIS A005602 (Наименьшее простое число, начинающее полную цепочку Каннингема длины n (первого рода)) — первый член наименьших полных цепочек Каннингема первого рода длины n , для 1 ≤ n ≤ 14
Последовательность OEIS A005603 (Цепочки длины n почти удвоенных простых чисел) — первый член наименьших полных цепочек Каннингема второго рода с длиной n для 1 ≤ n ≤ 15.

[1] Джо Бюлер, Алгоритмическая теория чисел: Третий международный симпозиум, ANTS-III . Нью-Йорк: Спрингер (1998): 290.

[records-2] Jump up to: Перейти обратно: ^а ^б Норман Лун и Дирк Огюстин, Cunningham Chain Records . Проверено 8 июня 2018 г.

[3] Лё, Гюнтер (октябрь 1989 г.). «Длинные цепочки почти удвоенных простых чисел» . Математика вычислений . 53 (188): 751–759. дои : 10.1090/S0025-5718-1989-0979939-8 .

[1]

[2]

[3]

v т и Классы простых чисел
По формуле	Ферма ( $2 2 н + 1$ ) Мерсенн ( $2 п - 1$ ) Двойной Мерсенн ( $2 2 п -1 - 1$ ) Вагстафф $(2 п + 1)/3$ Прот ( $k \cdot2 н + 1$ ) Факториал ( $n! \pm 1$ ) Первобытный ( $p n # \pm 1$ ) Евклид ( $p n # + 1$ ) Пифагорейский ( $4 n + 1$ ) Пьерпон ( $2 м \cdot3 н + 1$ ) Квартан ( $х 4 + и 4$ ) Солинас ( $2 м \pm 2 н \pm 1$ ) Каллен ( $n \cdot2 н + 1$ ) Вудалл ( $n \cdot2 н - 1$ ) Кубинский ( $х 3 - и 3)/(Икс - у$ ) Лейланд ( $x и + и х$ ) Сабит ( $3\cdot2 н - 1$ ) Уильямс ( $(b -1)\cdot b н - 1$ ) Миллс ( $⌊ А 3 н ⌋$ )
По целочисленной последовательности	Фибоначчи Лукас Пелл Ньюман–Шэнкс–Уильямс Перрин
По свойству	Виферих ( пара ) Стена–Солнце–Солнце Вулстенхолм Уилсон Удачливый удачливый Рамануджан Пиллаи Обычный Сильный Стерн Суперсингулярная (эллиптическая кривая) Суперсингулярная (теория самогона) Хороший Супер Хиггс Высокий коэффициент Уникальный
Базово -зависимый	палиндромный Эмирп Репунит $(10 н - 1)/9$ Перестановочный Круговой Усекаемый Минимальный Нежный Первобытный Полный отчет Уникальный Счастливый Себя Смарандаш-Веллин Стробограмматический двугранный тетрадный
Узоры	Твин ( $р, р + 2$ ) Двойная цепь ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Тройка ( $p, p +2 или p +4, p +6$ ) Четверка ( $р, р +2, р +6, р +8$ ) k -кортеж Двоюродный брат ( $п, р + 4$ ) Сексуальный ( $п, п + 6$ ) Чен Софи Жермен/Сейф ( $п, 2п +1$ ) Каннингем ( $п, 2 п \pm 1, 4 п \pm 3, 8 п \pm 7, ...$ ) Арифметическая прогрессия ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Сбалансированный ( $последовательные p - n, p, p + n$ )
По размеру	Мега (1 000 000+ цифр) Самый крупный известный список
Комплексные числа	Айронстоун прайм Гауссово простое число
Составные числа	Псевдопростой каталанский Эллиптический Эйлер Эйлер – Якоби Ферма Фробениус Лукас Перрин Сомер-Лукас Сильный Число Кармайкла Почти премьер Полупервоклассный Сфеническое число Интерпрайм Пагубный
Связанные темы	Вероятное простое число Промышленный класс Prime Незаконный премьер Формула простых чисел Премьер-разрыв
Первые 60 простых чисел	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
Список простых чисел