Введение
Математический проект по факторизации целых чисел
Проект Каннингема — это совместная работа, начатая в 1925 году, целью которой является разложение на множители чисел вида bn ± 1 для b = 2, 3, 5, 6, 7, 10, 11, 12 и больших n. Проект назван в честь Аллана Джозефа Шампнейса Каннингема, который опубликовал первую версию таблицы вместе с Гербертом Дж. Вудоллом. Существует три печатных издания таблицы, последнее из которых было опубликовано в 2002 году, а также онлайн-версия, созданная Сэмюэлем Вагстаффом. Текущие пределы степеней:
Основание23567101112 Предел1500900600550500450400400Aurifeuillean (LM) Предел30001800120011001000900800800
The Cunningham Project is a collaborative effort started in 1925 to factor numbers of the form bn ± 1 for b = 2, 3, 5, 6, 7, 10, 11, 12 and large n. The project is named after Allan Joseph Champneys Cunningham, who published the first version of the table together with Herbert J. Woodall. There are three printed versions of the table, the most recent published in 2002, as well as an online version by Samuel Wagstaff. The current limits of the exponents are:
Base23567101112 Limit1500900600550500450400400Aurifeuillean (LM) limit30001800120011001000900800800
Факторы числа Каннингема
Из числа Каннингема можно выделить два типа факторов без применения алгоритма факторизации: алгебраические факторы биномиальных чисел (например, разность двух квадратов и сумма двух кубов), зависящие от показателя степени, и факторы Орифея, зависящие как от основания, так и от показателя степени.
Другие факторы
После удаления алгебраических и аурифельевских факторов, остальные факторы вида bn ± 1 всегда имеют форму 2kn + 1, поскольку все они являются факторами. Когда n является простым числом, алгебраические и аурифельевские факторы невозможны, за исключением тривиальных факторов (b − 1 для bn − 1 и b + 1 для bn + 1). Для чисел Мерсена тривиальные факторы невозможны при простом n, поэтому все факторы имеют форму 2kn + 1. В общем случае, все факторы (bn − 1) / (b − 1) имеют форму 2kn + 1, где b ≥ 2 и n – простое число, за исключением случаев, когда n делит b − 1, в этом случае (bn − 1) / (b − 1) делится на само n. Числа Каннингема вида bn − 1 могут быть простыми только если b = 2 и n простое, при условии, что n ≥ 2; это числа Мерсена. Числа вида bn + 1 могут быть простыми только если b четное, а n является степенью 2, опять же при условии n ≥ 2; это обобщенные числа Ферма, которые совпадают с числами Ферма при b = 2. Любой фактор числа Ферма вида 2^(2n) + 1 имеет форму k2^(n+1) + 1.
Обозначение
bn − 1 обозначается как b,n−. Аналогично, bn + 1 обозначается как b,n+. При работе с числами вида, необходимого для аурифеуильской факторизации, b,nL и b,nM используются для обозначения L и M в указанных выше произведениях. Ссылки на b,n− и b,n+ относятся к числу, из которого удалены все алгебраические и аурифеуильские множители. Например, числа Мерсенна имеют вид 2,n−, а числа Ферма — вид 2,2n+; число Аурифеуиля, разложенное на множители в 1871 году, было произведением 2,58L и 2,58M.