Сеть Каннингем - Cunningham chain

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

Одно приложение для сетей Cunningham использует вычислительную мощность для их идентификации с целью создания виртуальной валюты, аналогично тому, как Биткойн добывается.^[1]

Определение

А Каннингемская цепь первого вида длины п последовательность простых чисел (п₁, ..., п_п) такое, что для всех 1 ≤я < п, п_я+1 = 2п_я + 1. (Следовательно, каждый член такой цепочки, кроме последнего, является Софи Жермен прайм, и каждый член, кроме первого, является безопасный прайм ).

Следует, что

{ displaystyle { begin {align} 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 {выравнивается}}}

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

Аналогично Каннингемская цепь второго вида длины п последовательность простых чисел (п₁,...,п_п) такое, что для всех 1 ≤я < п, п_я+1 = 2п_я − 1.

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

{ displaystyle p_ {i} = 2 ^ {i-1} p_ {1} - (2 ^ {i-1} -1) ,}

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

Цепи Каннингема также иногда обобщают на последовательности простых чисел (п₁, ..., п_п) такое, что для всех 1 ≤я ≤ п, п_я+1 = ap_я + б для фиксированного совмещать целые числа а, б; получившиеся цепочки называются обобщенные цепи Каннингема.

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

Примеры

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

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

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

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

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

89, 179, 359, 719, 1439, 2879 (следующее число будет 5759 = 13 * 443, но это не простое число).

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

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

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

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

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

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

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

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

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

Самая большая известная длина цепи Каннингема k (по состоянию на 5 июня 2018 г.^[3])
k	вид	п₁ (начальный штрих)	Цифры	Год	Первооткрыватель
1	1-й / 2-й	2^77232917 − 1	23249425	2017	Кертис Купер, GIMPS
2	1-й	2618163402417×2^1290000 − 1	388342	2016	PrimeGrid
2	2-й	7775705415×2¹⁷⁵¹¹⁵ + 1	52725	2017	Серж Баталов
3	1-й	1815615642825×2⁴⁴⁰⁴⁴ − 1	13271	2016	Серж Баталов
3	2-й	742478255901×2⁴⁰⁰⁶⁷ + 1	12074	2016	Майкл Энджел и Дирк Огюстен
4	1-й	13720852541*7877# − 1	3384	2016	Майкл Энджел и Дирк Огюстен
4	2-й	17285145467*6977# + 1	3005	2016	Майкл Энджел и Дирк Огюстен
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	Primecoin (блок 95569 )
11	2-й	341841671431409652891648*311# + 1	149	2016	Андрей Балякин
12	1-й	288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 1	113	2014	Primecoin (блок 558800 )
12	2-й	906644189971753846618980352*233# + 1	121	2015	Андрей Балякин
13	1-й	106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1	107	2014	Primecoin (блок 368051 )
13	2-й	38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 1	101	2014	Primecoin (блок 539977 )
14	1-й	4631673892190914134588763508558377441004250662630975370524984655678678526944768*47# - 1	97	2018	Primecoin (блок 2659167 )
14	2-й	5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1	100	2014	Primecoin (блок 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 год^{[Обновить]}, самая длинная из известных цепей Каннингема любого типа имеет длину 19, обнаруженную Ярославом Вроблевски в 2014 году.^[3]

Конгруэнции цепей Каннингема

Пусть нечетное простое число ${ displaystyle p_ {1}}$ быть первым простым числом в цепи Каннингема первого типа. Первое простое число нечетное, поэтому ${ Displaystyle p_ {1} Equiv 1 { pmod {2}}}$ . Поскольку каждое последующее простое число в цепочке равно ${ displaystyle p_ {i + 1} = 2p_ {i} +1}$ следует, что ${ Displaystyle р_ {я} эквив 2 ^ {я} -1 { pmod {2 ^ {я}}}}$ . Таким образом, ${ Displaystyle p_ {2} Equiv 3 { pmod {4}}}$ , ${ Displaystyle p_ {3} Equiv 7 { pmod {8}}}$ , и так далее.

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

Двоичный	Десятичный
1000011011010000000100111101	141361469
10000110110100000001001111011	282722939
100001101101000000010011110111	565445879
1000011011010000000100111101111	1130891759
10000110110100000001001111011111	2261783519
100001101101000000010011110111111	4523567039

Аналогичный результат верен для цепей Каннингема второго рода. Из наблюдения, что ${ Displaystyle p_ {1} Equiv 1 { pmod {2}}}$ и отношение ${ displaystyle p_ {i + 1} = 2p_ {i} -1}$ следует, что ${ Displaystyle р_ {я} эквив 1 { pmod {2 ^ {я}}}}$ . В двоичной системе счисления простые числа в цепочке Каннингема второго рода оканчиваются шаблоном "0 ... 01", где для каждого ${ displaystyle i}$ , количество нулей в шаблоне для ${ displaystyle p_ {я + 1}}$ на единицу больше, чем количество нулей для ${ displaystyle p_ {i}}$ . Как и в случае с цепями Каннингема первого типа, биты слева от шаблона сдвигаются влево на одну позицию с каждым последующим простым числом.

Точно так же, потому что ${ displaystyle p_ {i} = 2 ^ {i-1} p_ {1} + (2 ^ {i-1} -1) ,}$ следует, что ${ Displaystyle р_ {я} эквив 2 ^ {я-1} -1 { pmod {р_ {1}}}}$ . Но, по Маленькая теорема Ферма, ${ Displaystyle 2 ^ {p_ {1} -1} Equiv 1 { pmod {p_ {1}}}}$ , так ${ displaystyle p_ {1}}$ разделяет ${ displaystyle p_ {p_ {1}}}$ (т.е. с ${ displaystyle i = p_ {1}}$ ). Таким образом, никакая цепь Каннингема не может быть бесконечной длины.^[4]

Смотрите также

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

внешняя ссылка

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

[1] "Cunningham Chains Mining" (PDF). lirmm.fr. Получено 2018-11-07.

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

[records-3] а ^б Дирк Огюстен, Рекорды Cunningham Chain. Проверено 8 июня 2018.

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

[1]

[2]

[3]

[4]

простое число классы
По формуле	Ферма ( $2 2 п + 1$ ) Мерсенн ( $2 п - 1$ ) Двойной Мерсенн ( $2 2 п -1 - 1$ ) Wagstaff $(2 п + 1)/3$ Proth ( $k \cdot2 п + 1$ ) Факториал ( $п! \pm 1$ ) Первобытный ( $п п # \pm 1$ ) Евклид ( $п п # + 1$ ) Пифагорейский ( $4 п + 1$ ) Pierpont ( $2 м \cdot3 п + 1$ ) Квартан ( $Икс 4 + у 4$ ) Солинас ( $2 м \pm 2 п \pm 1$ ) Каллен ( $п \cdot2 п + 1$ ) Вудалл ( $п \cdot2 п - 1$ ) Кубинский ( $Икс 3 - у 3)/(Икс - у$ ) Кэрол $(2 п - 1) 2 - 2$ Kynea $(2 п + 1) 2 - 2$ Лейланд ( $Икс у + у Икс$ ) Табит ( $3\cdot2 п - 1$ ) Уильямс ( $(б -1)\cdot б п - 1$ ) Миллс ( $⌊ А 3 п ⌋$ )
По целочисленной последовательности	Фибоначчи Лукас Пелл Ньюман – Шанкс – Уильямс Перрин Перегородки Колокол Моцкин
По собственности	Виферих (пара ) Стена – Солнце – Солнце Wolstenholme Уилсон Счастливчик Удачливый Рамануджан Пиллаи Обычный Сильный Штерн Суперсингулярный (эллиптическая кривая) Суперсингулярный (теория самогона) Хороший супер Хиггс Очень cototient
Основание -зависимый	Палиндромный Эмирп Repunit $(10 п - 1)/9$ Перестановочный Круговой Усекаемый Минимальный Слабо Первобытный Полное повторение Уникальный Счастливый Себя Смарандаче – Веллин Стробограмматический Двугранный Тетрадич
Узоры	Близнец ( $п, п + 2$ ) Двусторонняя цепь ( $п - 1, п + 1, 2 п - 1, 2 п + 1, \dots$ ) Триплет ( $п, п + 2 или п + 4, п + 6$ ) Четверной ( $п, п + 2, п + 6, п + 8$ ) k−Tuple Двоюродная сестра ( $п, п + 4$ ) Сексуальный ( $п, п + 6$ ) Чен Софи Жермен / Сейф ( $п, 2 п + 1$ ) Каннингем ( $п, 2 п \pm 1, 4 п \pm 3, 8 п \pm 7, ...$ ) Арифметическая прогрессия ( $п + а \cdot п, п = 0, 1, 2, 3, ...$ ) Сбалансированный ( $последовательный п - п, п, п + п$ )
По размеру	Титаник (Более 1000 цифр) Гигантский (10 000+ цифр) Мега (Более 1000000 цифр) Самый большой известный
Сложные числа	Эйзенштейн простое Гауссово простое число
Составные числа	Псевдопремия Каталонский Эллиптический Эйлер Эйлер – Якоби Ферма Фробениус Лукас Сомер – Лукас Сильный Число Кармайкла Почти премьер Полупростой Interprime Пагубный
похожие темы	Вероятное простое число Прайм промышленного класса Незаконный премьер Формула для простых чисел Главный разрыв
Первые 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
Список простых чисел