Проект Каннингема

Проект Каннингема - это проект, начатый в 1925 году, чтобы разложить на множители числа вида b ⁿ ± 1 для b = 2, 3, 5, 6, 7, 10, 11, 12 и большого n . Проект назван в честь Аллана Джозефа Чампни Каннингема , который опубликовал первую версию таблицы вместе с Гербертом Дж. Вудаллом . ^[1] Существует три печатных версии таблицы, последняя из которых опубликована в 2002 г. ^[2], а также онлайн-версия. ^[3]

Текущие пределы показателей:

Факторы чисел Каннингема [ править ]

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

Алгебраические факторы [ править ]

Из элементарной алгебры,

${\displaystyle (b^{kn}-1)=(b^{n}-1)\sum _{r=0}^{k-1}b^{rn}}$

для всех k , и

${\displaystyle (b^{kn}+1)=(b^{n}+1)\sum _{r=0}^{k-1}(-1)^{r}\cdot b^{rn}}$

для нечетных k . Кроме того, b ^{2 n}  - 1 = ( b ⁿ  - 1) ( b ⁿ  + 1). Таким образом, когда m делит n , b ^m  - 1 и b ^m  + 1 делятся на b ⁿ  - 1, если частное n по m четное; только первое число является множителем, если частное нечетное. b ^m  + 1 делится на b ⁿ  - 1, если m делит n и частное нечетное.

По факту,

${\displaystyle b^{n}-1=\prod _{d\mid n}\Phi _{d}(b)}$

а также

${\displaystyle b^{n}+1=\prod _{d\mid 2n,d!\mid n}\Phi _{d}(b)}$

Факторы Аурифейля [ править ]

Когда число имеет определенную форму (точное выражение зависит от основания), может использоваться факторизация Орифейля, которая дает произведение двух или трех чисел. Следующие уравнения дают коэффициенты Орифейля для баз проекта Каннингема как произведение F , L и M : ^[4]

Пусть b = s ² · k с бесквадратным k , если одно из условий выполнено, то имеет факторизацию Орифейля.${\displaystyle \Phi _{n}(b)}$

(i) и${\displaystyle k\equiv 1\mod 4}$${\displaystyle n\equiv k{\pmod {2k}};}$

(ii) и${\displaystyle k\equiv 2,3{\pmod {4}}}$${\displaystyle n\equiv 2k{\pmod {4k}}.}$

Другие факторы [ править ]

После удаления алгебраических факторов и множителей Орифейля другие множители b ⁿ ± 1 всегда имеют форму 2 kn  + 1, поскольку все они являются факторами ^{[ необходима цитата ]} . Когда n простое, невозможно использовать как алгебраические множители, так и множители Орифейля, за исключением тривиальных множителей ( b  - 1 для b ⁿ  - 1 и b  + 1 для b ⁿ  + 1). Для чисел Мерсенна тривиальные множители для простого n невозможны  , поэтому все множители имеют вид 2 kn  + 1. В общем случае все множители ( b ⁿ${\displaystyle \Phi _{n}(b)}$ - 1) / ( b  - 1) имеют вид 2 kn  + 1, где b  ≥ 2 и n простое, за исключением  случая , когда n делит b - 1, и в этом случае ( b ⁿ  - 1) / ( b  - 1) делится на само n .

Числа Каннингема вида b ⁿ  - 1 могут быть простыми, только если b = 2 и n простое, при условии, что n ≥ 2; это числа Мерсенна. Числа вида b ⁿ  + 1 могут быть простыми, только если b четно и n является степенью двойки, опять же при условии, что n  ≥ 2; это обобщенные числа Ферма, которые являются числами Ферма при b = 2. Любой множитель числа Ферма 2 ^{2 n}  + 1 имеет вид k 2 ^{n  + 2}  + 1.

Обозначение [ править ]

b ⁿ  - 1 обозначается как b , n -. Аналогично, b ⁿ  + 1 обозначается как b , n +. При работе с числами в форме, требуемой для факторизации Аурифейля, b , n L и b , n M используются для обозначения L и M в приведенных выше продуктах . ^[5] Ссылки на b , n - и b , n + относятся к числу без всех алгебраических факторов и множителей Орифейля. Например, числа Мерсенна имеют вид 2, n- и числа Ферма имеют вид 2,2 ⁿ +; число Aurifeuille, вычисленное в 1871 году, было произведением 2,58L и 2,58M.

См. Также [ править ]

• Число Каннингема
• ECMNET и NFS @ Home , две совместные работы над проектом Cunningham

Ссылки [ править ]

Внешние ссылки [ править ]

• Домашняя страница проекта Cunningham
• Таблица Брента-Монтгомери-те Риле (таблицы Каннингема для более высоких оснований)
• Столы Каннингема на Mersennewiki