Показать меню

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

17.12.2020
20

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

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

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

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

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

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

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

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:

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

Еще по этой теме:
Среднее кубическое
04:36, 17 декабрь
Среднее кубическое
Среднее кубическое (также средняя кубическая) — число x {displaystyle x} , равное кубическому корню из среднего арифметического кубов данных чисел
Группа Гейзенберга
12:26, 14 декабрь
Группа Гейзенберга
Группа Гейзенберга — группа, состоящая из квадратных матриц вида ( 1
123 (число)
08:12, 12 декабрь
123 (число)
123 (сто двадцать три) — натуральное число, расположенное между числами 122 и 124. Оно не является простым числом, а относительно последовательности простых чисел расположено между 113 и 127. 123
Алгебраическая теория чисел
14:00, 08 декабрь
Алгебраическая теория чисел
Алгебраическая теория чисел — раздел теории чисел, основная задача которого — изучение свойств целых элементов числовых полей. В алгебраической теории чисел понятие числа расширяется, в качестве
Максимальный тор
12:52, 03 декабрь
Максимальный тор
Максимальный тор связной вещественной группы Ли G {displaystyle G} — связная компактная коммутативная подгруппа Ли T
Квадратное треугольное число
05:27, 02 декабрь
Квадратное треугольное число
В теории чисел квадратным треугольным числом (или треугольным квадратным числом) называется число, являющееся как треугольным, так и квадратным. Существует бесконечное число квадратных треугольных
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent