2.3.4. Разложение на множители больших целых чисел

С задачей о нахождении делителей больших простых чисел дело обстоит гораздо хуже, чем с проверкой простоты. Мы не знаем даже, существует ли вероятностный алгоритм, который выдает за полиномиальное время делитель большого составного числа с вероятность . Литература по этому предмету также весьма обширна (Dixon, 1981, 1984; Guy, 1976; Knuth, 1969; Lehman, 1974; Morrison et al., 1975; Williams, 1982 и 1984; Wunderlich, 1979); мы представим следующий метод разложения на множители (упрощенный вариант) для чисел общего вида, который является наиболее сильным из известных.

Метод основывается на идее Лежандра (1798): если делит , но

не делит ни ни поэтому , наибольший общий делитель чисел , является нетривиальным делителем и может быть легко вычислен с помощью алгоритма Евклида. Поиск таких и и v происходит в два этапа, как описано ниже.

Пусть мы хотим разложить на множители число . Пусть — максимальное число, не превосходящее и вычислим числа для небольших к (числа к могут быть и отрицательными). [Вместо чисел а Моррисон и Бриллхарт (Morrison, Brillhart, 1975) использовали величины если — цепная дробь, представляющая число с — небольшой множитель, то определяются формулой

Пусть — множество небольших простых чисел, которые могут делить выражения вида (т.е. является квадратом сто модулю ). Такое множество обычно называют мультипликативной базой В. Запомним все числа которые могут быть разложены по мультипликативной базе, т.е. записаны в виде

Такие называются - числами. С каждым В-числом а связывается вектор показателей

Если мы найдем достаточно много -чисел, чтобы множество соответствующих векторов показателей было линейно зависимо по модулю 2 (любое множество из -чисел обладает этим свойством), то можно будет представить нулевой вектор в виде суммы векторов показателей некоторого множества S, скажем, ). Определим теперь целые числа

Из сказанного выше следует, что может быть нетривиальным делителем .

Пример. Разложим на множители 1729, третье кармайклово число. В этом случае вычислим числа для небольших к. Имеем и т.д. Зафиксируем множество небольших простых чисел мы видим, что только 35, 120, 480 и 672 являются -числами, а именно Кроме 480, все числа включаются в множество S, поскольку сумма векторов показателей всех чисел, кроме 480, равна (0, 0, 0, 0, 0). Лалее вычисляются показатели и числа Квадраты чисел и и v совпадают по модулю Имеем является делителем числа 1729.

Диксоном (Dixon, 1981) доказано, что число то разлагается этим методом на множители за время

где a — некоторая константа, при Эта величина растет медленнее, чем экспонента, но быстрее, чем любая степень числа

Отметим, что числа вида которые называются соответственно числами Ферма и Мерсенна, оказали глубокое влияние на развитие техники разложения на множители и проверки простоты. Еще в 1640 г. Ферма предположил, что любое число , является простым. Однако это предположение было опровергнуто в 1729 г. Эйлером, который показал, что число делится на 641.