Проект Каннингема
Проект Каннингема — это проект, начатый в 1925 году, по факторизации чисел формы b n ± 1 для b = 2, 3, 5, 6, 7, 10, 11, 12 и больших n . Проект назван в честь Аллана Джозефа Чампни Каннингема , опубликовавшего первую версию таблицы вместе с Гербертом Дж. Вудаллом . [1] Существует три печатных версии таблицы, последняя из которых опубликована в 2002 г. [2] , а также онлайн-версия. [3]
Два типа множителей могут быть получены из числа Каннингема без использования алгоритма факторизации: алгебраические множители, которые зависят от показателя степени, и множители Аурифейля, которые зависят как от основания, так и от показателя степени.
для нечетного k . Кроме того, b 2 n - 1 = ( b n - 1)( b n + 1). Таким образом, когда m делит n , b m - 1 и b m + 1 являются множителями b n - 1, если частное n по m четно; только первое число является множителем, если частное нечетно. b m + 1 является множителем b n − 1, если m делит n и частное нечетно.
Когда число имеет определенную форму (точное выражение зависит от основания), можно использовать факторизацию Орифейля, которая дает произведение двух или трех чисел. Следующие уравнения дают факторы Орифейля для базисов проекта Каннингема как произведение F , L и M : [4]
Пусть b = s 2 · k с бесквадратным k , если выполняется одно из условий, то имеет место факторизация Аурифейля.
Как только алгебраический и аурифейлев множители удалены, другие множители b n ± 1 всегда имеют вид 2 kn + 1, поскольку все они являются множителями [ нужна ссылка ] . Когда n простое число, и алгебраические, и орифейлевы множители невозможны, за исключением тривиальных множителей ( b - 1 для b n - 1 и b + 1 для b n + 1). Для чисел Мерсенна тривиальные множители невозможны для простых n , поэтому все множители имеют вид 2 kn + 1. В общем, все множители ( b n − 1)/( b − 1) имеют вид 2 kn + 1, где b ≥ 2 и n простое число, за исключением случаев, когда n делится на b − 1, и в этом случае ( b n − 1)/( b − 1) делится на само n .