Иллюстрированный самоучитель по Mathematica 5

Функция FactorIntegerECM (попытка факторизации больших чисел Мерсенна)

Давайте на примере попытки разложения больших чисел Мерсенна рассмотрим, к ак Mathematica позволяет приблизиться к решению задачи факторизации очень больших чисел.

Факторизация 317-го числа Мерсенна М317

Конечно, можно попытаться применить функцию Factorlnteger. Но это не даст результата (за приемлемое время). Можно, правда, "попросить" функцию Factorlnteger найти хоть какие-нибудь делители числа Мерсенна М₃₁₇. Для этого нужно воспользоваться опцией FactorComplete › False.

FactorInteger[M₃₁₇-1,FactorComplete › False]

Результат будет таким.

Чуть ниже будут и найденные множители.

Хорошо, конечно, что нашли множитель 9511, но вот второй множитель… Неизвестно, даже простой ли он. Можно, конечно, попытаться повторить процедуру для него, но это ни к чему новому не приведет.

В этом случае все придется сделать вручную:.. Возможно, вы подумали о формулах сокращенного умножения. Да, действительно, часто они помогают. (Мы в этом уже не раз убеждались.) Но в данном случае 317 – простое число (я специально так подобрал индекс числа Мерсенна), и применить формулы сокращенного умножения просто так, "в лоб", не удастся. Придется использовать другую функцию. Она есть в пакете теории чисел, который загружается так:

Сама функция называется FactorIntegerECM. Ее первоначальный алгоритм придумал X. Ленстра (Н. W. Lenstra) в 1985 году. В нем используется теория эллиптических кривых. Функция FactorIntegerECM очень эффективна там, где FactorInteger не справляется. Правда, с другой стороны, она не столь услужлива, как FactorInteger. Она находит только один множитель, притом не обязательно простой. К тому же она привередлива: ее поведение не предсказуемо, если в качестве аргумента передать ей простое число. Поэтому предварительно нужно проверить, что аргумент не является простым числом. Это делается с помощью функции PrimeQ.

Давайте теперь попытаемся применить функцию FactorIntegerECM для какого-нибудь небольшого числа, например 91. (Это число, как мы знаем, не простое.)

А вот и результат.

Да, найден только один множитель… Остальное приходится делать вручную. Рассмотрим теперь более сложный пример.

Вот что получилось: