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

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

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

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

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

FactorInteger[M317-1,FactorComplete › False]

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

FactorInteger::facfn: Unable to factor 28072587476617 "64" 65592773657961.
More...

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

{{9511, 1), {280725874766179960361032187226573
45634038278340298769450465
797600439224658035965592773657961.1}}

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

Factorlnteger::facfn:
Unable to factor 28072587476617
"64" 65592773657961. More...
{{2807258747661799603610
321872265734563403827834
0298769450465797600439
224658035965592773657961.1}}

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

<<NumberTheory`FactorlntegerECM`

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

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

FactorIntegerECM[91]

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

13

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

m = 12
n = Prime[10 ^ m] Prime[10 ^ m + 1]

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

12 899773470806612917304808883
Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.