Цепочка Каннингема

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

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

• 1 Определение
• 2 Примеры
• 3 Крупнейшие известные цепи Каннингема
• 4 Конгруэнции цепей Каннингема
• 5 См. Также
• 6 Ссылки
• 7 Внешние ссылки

A Цепь Каннингема первого вида длины n - это последовательность простых чисел (p 1,..., p n) таких, что для всех 1 ≤ i простым числом Софи Жермен, и каждое член, за исключением первого, является безопасным простым числом ).

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

$p\; 2\; =\; 2\; p\; 1\; +\; 1,\; p\; 3\; =\; 4\; p\; 1\; +\; 3,\; p\; 4\; =\; 8\; p\; 1\; +\; 7,\; ⋮\; pi\; =\; 2\; i\; -\; 1\; p\; 1\; +\; (\; 2\; i\; -\; 1\; -\; 1).\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; p\_\; \{2\}\; =\; 2p\_\; \{1\}\; +1,\; \backslash \backslash \; p\_\; \{3\}\; =\; 4p\_\; \{1\}\; +3,\; \backslash \backslash \; p\_\; \{4\}\; =\; 8p\_\; \{1\}\; +\; 7,\; \backslash \backslash \; \{\}\; \backslash \; \backslash \; vdots\; \backslash \backslash \; p\_\; \{i\}\; =\; 2\; ^\; \{i-1\}\; p\_\; \{1\}\; +\; (2\; ^\; \{i-1\}\; -1).\; \backslash \; End\; \{align\}\}\}$

Или, задав $a\; =\; p\; 1\; +\; 1\; 2\; \{\backslash \; displaystyle\; a\; =\; \{\backslash \; frac\; \{p\_\; \{1\}\; +1\}\; \{2\}\}\}$(число $a\; \{\backslash \; displaystyle\; a\}$не является частью последовательности и не обязательно должно быть простым числом), мы имеем $pi\; =\; 2\; ia\; -\; 1\; \{\backslash \; displaystyle\; p\_\; \{i\}\; =\; 2\; ^\; \{i\}\; a-1\}$

Аналогично, цепочка Каннингема второго вида длины n представляет собой последовательность простых чисел (p 1,..., p n) такой, что для всех 1 ≤ i

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

$пи\; =\; 2\; я\; -\; 1\; п\; 1\; -\; (2\; я\; -\; 1\; -\; 1)\; \{\backslash \; displaystyle\; p\_\; \{i\}\; =\; 2\; ^\; \{i-1\}\; p\_\; \{1\}\; -\; (2\; ^\; \{i-1\}\; -1)\; \backslash ,\}$

Теперь, установив $a\; =\; p\; 1\; -\; 1\; 2\; \{\backslash \; displaystyle\; a\; =\; \{\backslash \; frac\; \{p\_\; \{1\}\; -1\}\; \{2\}\}\}$, мы имеем $pi\; =\; 2\; ia\; +\; 1\; \{\backslash \; displaystyle\; p\_\; \{i\}\; =\; 2\; ^\; \{i\}\; a\; +\; 1\}$.

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

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

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

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, но это не простое число.)

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

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

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

q # обозначает примориал 2 × 3 × 5 × 7 ×... × q.

На 2018 год самая длинная из известных цепей Каннингема любого типа имеет длину 19, что было обнаружено Ярославом Вроблевски в 2014 году.

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

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

Двоичный	Десятичный
1000011011010000000100111101	141361469
10000110110100000001001111011	282722939	282722939
100001101101000000010011110111	565445879
1000011011010000000100111101111	1130891759
10000110110100000001001111011111	226178351910011111	22617835191001101103103>Цепи Каннингема второго вида. Из наблюдения, что $p\; 1\; \equiv \; 1\; (mod\; 2)\; \{\backslash \; displaystyle\; p\_\; \{1\}\; \backslash \; Equiv\; 1\; \{\backslash \; pmod\; \{2\}\}\}$и отношение $pi\; +\; 1\; =\; 2\; pi\; -\; 1\; \{\backslash \; displaystyle\; p\_\; \{i\; +\; 1\}\; =\; 2p\_\; \{i\}\; -1\}$следует, что $pi\; \equiv \; 1\; (mod\; 2\; i)\; \{\backslash \; displaystyle\; p\_\; \{i\}\; \backslash \; Equiv\; 1\; \{\backslash \; pmod\; \{2\; ^\; \{i\}\}\}\}$. В двоичной системе счисления простые числа в цепочке Каннингема второго рода оканчиваются шаблоном «0... 01», где для каждого $i\; \{\backslash \; displaystyle\; i\}$количество нулей в шаблоне для $pi\; +\; 1\; \{\backslash \; displaystyle\; p\_\; \{i\; +\; 1\}\}$на единицу больше, чем количество нулей для $pi\; \{\backslash \; displaystyle\; p\_\; \{i\}\}$. Как и в случае с цепями Каннингема первого типа, биты слева от шаблона сдвигаются влево на одну позицию с каждым последующим простым числом. Аналогично, поскольку $pi\; =\; 2\; i\; -\; 1\; p\; 1\; +\; (2\; i\; -\; 1\; -\; 1)\; \{\backslash \; displaystyle\; p\_\; \{i\}\; =\; 2\; ^\; \{i-1\}\; p\_\; \{1\}\; +\; (\; 2\; ^\; \{i-1\}\; -1)\; \backslash ,\}$следует, что $pi\; \equiv \; 2\; i\; -\; 1-1\; (mod\; p\; 1)\; \{\backslash \; displaystyle\; p\_\; \{i\}\; \backslash \; Equiv\; 2\; ^\; \{\; i-1\}\; -1\; \{\backslash \; pmod\; \{p\_\; \{1\}\}\}\}$. Но согласно маленькой теореме Ферма, $2\; p\; 1\; -\; 1\; \equiv \; 1\; (mod\; p\; 1)\; \{\backslash \; displaystyle\; 2\; ^\; \{p\_\; \{1\}\; -1\}\; \backslash \; Equiv\; 1\; \{\backslash \; pmod\; \{p\_\; \{\; 1\}\}\}\}$, поэтому $p\; 1\; \{\backslash \; displaystyle\; p\_\; \{1\}\}$делит $pp\; 1\; \{\backslash \; displaystyle\; p\_\; \{p\_\; \{1\}\}\}$(то есть с $i\; =\; p\; 1\; \{\backslash \; displaystyle\; i\; =\; p\_\; \{1\}\}$). Таким образом, ни одна цепочка Каннингема не может иметь бесконечную длину. См. Также Primecoin, в котором цепи Каннингема используются в качестве системы доказательства работы Цепи двойных двойников Простые числа в арифметической прогрессии Литература ^«Cunningham Chains Mining» (PDF). lirmm.fr. Проверено 7 ноября 2018 г. ^Джо Бюлер, Алгоритмическая теория чисел: Третий международный симпозиум, ANTS-III. Нью-Йорк: Springer (1998): 290 ^ Дирк Огюстин, Cunningham Chain records. Проверено 8 июня 2018. ^Лё, Гюнтер (октябрь 1989 г.). «Длинные цепочки почти удвоенных простых чисел». Математика вычислений. 53 (188): 751–759. doi : 10.1090 / S0025-5718-1989-0979939-8. Внешние ссылки The Prime Glossary: ​​Cunningham chain Открытия Primecoin (primes.zone): онлайн-база данных Выводы праймкойнов со списком записей и визуализацией PrimeLinks ++: Цепочка Каннингема OEIS последовательность A005602 (Наименьшее простое число, начинающееся полной цепочкой Каннингема длины n (первого вида)) - первый член младших полных цепей Каннингема первого вида длины n для 1 ≤ n ≤ 14 OEIS последовательность A005603 (Цепи длины n почти удвоенных простых чисел) - первый член младших полных цепей Каннингема второго рода с длиной n для 1 ≤ n ≤ 15 Последняя правка сделана 2021-05-16 11:26:22 Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное). Обратная связь: support@alphapedia.ru Соглашение О проекте