WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

К 2011 году самая большая известная цепь Каннингема любого рода имеет длину 17. Первая найдена была цепь первого рода, начинающаяся с 2759832934171386593519, (найдена Ярославом Вроблевским в 2008 году).^[2]

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

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

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

Аналогичный результат можно получить и для цепей второго рода. Заметим, что из ${\displaystyle p_{1}\equiv 1{\pmod {2}}}$ и отношения ${\displaystyle p_{i+1}=2p_{i}-1}$ следует, что ${\displaystyle p_{i}\equiv 1{\pmod {2^{i}}}}$ . В двоичной записи простые числа в цепи Каннингема второго рода кончаются на «0…01», где для любого ${\displaystyle i}$ число нулей для ${\displaystyle p_{i+1}}$ на единицу больше числа нулей ${\displaystyle 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: первый член минимальной полной цепи Каннингема первого рода длины ${\displaystyle n}$ , для ${\displaystyle 1\leq n\leq 14}$
• последовательность A005603 в OEIS: первый член минимальной полной цепи Куннингама второго рода длины ${\displaystyle n}$ , для ${\displaystyle 1\leq n\leq 15}$