Каннингемский проект

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

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

База	2	3	5	6	7	10	11	12
Лимит	1500	900	600	550	500	450	400	400
Орифейский предел (LM)	3000	1800	1200	1100	1000	900	800	800

Факторы числа Каннингема

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

Алгебраические факторы

Основная статья: Биномиальное число § Факторизация

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

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

для всех k и

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

для нечетного k . Кроме того, б ^{2 н} − 1 = ( б ^н − 1)( б ^н + 1). Таким образом, когда m делит n , b ^м − 1 и б ^м + 1 – коэффициенты b ^н если фактор n по m четен − 1 , ; только первое число является делителем, если частное нечетное. б ^м + 1 — коэффициент b ^н − 1, если m делит n и частное нечетно.

Фактически,

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

и

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

См. эту страницу для получения дополнительной информации.

Факторы Орифейля

Основная статья: факторизация Орифейля

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

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

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

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

б	Число	Ф	л	М	Другие определения
2	2 4 k +2 + 1	1	2 2к 1 + − 2 к +1 + 1	2 2к 1 + + 2 к +1 + 1
3	3 6 тыс +3 + 1	3 2к 1 + + 1	3 2к 1 + − 3 к +1 + 1	3 2к 1 + + 3 к +1 + 1
5	5 10 тысяч +5 − 1	5 2к 1 + − 1	Т  2 − 5 к +1 Т + 5 2к 1 +	Т  2 + 5 к +1 Т + 5 2к 1 +	Т = 5 2к 1 + + 1
6	6 12 тыс. +6 + 1	6 4 k +2 + 1	Т  2 − 6 к +1 Т + 6 2к 1 +	Т  2 + 6 к +1 Т + 6 2к 1 +	Т = 6 2к 1 + + 1
7	7 14 тыс. +7 + 1	7 2к 1 + + 1	А - Б	А + Б	А = 7 6 тыс +3 + 3(7 4 k +2 ) + 3(7 2к 1 + ) + 1 Б = 7 5 тыс +3 + 7 3 тыс +2 + 7 к +1
10	10 20 тысяч +10 + 1	10 4 k +2 + 1	А - Б	А + Б	А = 10 8 тыс +4 + 5(10 6 тыс +3 ) + 7(10 4 k +2 ) + 5(10 2к 1 + ) + 1 Б = 10 7к 4 + + 2(10 5 тыс +3 ) + 2(10 3 тыс +2 ) + 10 к +1
11	11 22 тыс. +11 + 1	11 2к 1 + + 1	А - Б	А + Б	А = 11 10 тысяч +5 + 5(11 8 тыс +4 ) − 11 6 тыс +3 − 11 4 k +2 + 5(11 2к 1 + ) + 1 Б = 11 9к 5 + + 11 7к 4 + − 11 5 тыс +3 + 11 3 тыс +2 + 11 к +1
12	12 6 тыс +3 + 1	12 2к 1 + + 1	12 2к 1 + − 6(12 к ) + 1	12 2к 1 + + 6(12 к ) + 1

Другие факторы

После удаления алгебраических и аурифейлевых множителей остальные множители b ^н ± 1 всегда имеют вид 2 kn + 1, поскольку множители b ^н − 1 – все факторы $\Phi _{n}(b)$, а факторы b ^н + 1 – все факторы $\Phi _{2n}(b)$. Когда n , простое число невозможны как алгебраические, так и аурифейловы множители, за исключением тривиальных множителей ( b − 1 для b ^н − 1 и b + 1 для b ^н + 1). Для чисел Мерсенна тривиальные множители невозможны для простых n , поэтому все множители имеют вид 2 kn + 1. В общем, все множители ( 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; это числа Мерсенна. Числа вида б ^н + 1 может быть простым только в том случае, если b четно и n является степенью 2 , опять же предполагая, что n ≥ 2; это обобщенные числа Ферма, которые являются числами Ферма, когда b = 2. Любой множитель числа Ферма 2 ^{2 н} + 1 имеет вид k 2 ^{п +2}  + 1.

Обозначения

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

См. также

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

Внешние ссылки

• Домашняя страница проекта Каннингема
• Факторизация b ^н ±1, b = 2, 3, 5, 6, 7, 10, 11, 12 До высоких степеней, второе издание
• Факторизация b ^н ±1, b = 2, 3, 5, 6, 7, 10, 11, 12 До высоких мощностей, третье издание
• Машиночитаемые таблицы Каннингема
• Проект Каннингема
• Таблица Брента-Монтгомери-те Риля (таблицы Каннингема для высших оснований (основания 13 ≤ b ≤ 99, совершенные степени исключены, поскольку степень b ^н тоже степень b ))
• Онлайн-сбор факторов
• Проект Каннингема на Prime Wiki
• Проект Каннингема на PrimePages