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

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

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

Чтобы освоить методику применения функций Factorlnteger и FactorIntegerECM, попробуем разложить на простые множители 337-е число Мерсенна M₃₃₇. Сначала можно попытаться применить функцию Factorlnteger. Но как и в случае 317-го числа Мерсенна M₃₁₇, это не даст результата за приемлемое время. Тогда применим функцию Factorlnteger с опцией FactorComplete ->False, чтобы найти хоть какие-нибудь делители 337-го числа Мерсенна М₃₃₇.

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

Зато чуть ниже будут найдены делители.

Иными словами:

Теперь нужно проверить, просты ли найденные делители.

Как видите, все они, за исключением последнего (обозначим его временно через n), самого большого, простые. (Все это заняло менее двух секунд.)

Поскольку 337 – простое число (я опять специально подобрал индекс числа Мерсенна), формулы сокращенного умножения "в лоб" применить не удастся. Но ведь мы можем загрузить пакет теории чисел.

Теперь, когда пакет загружен, можно вызвать функцию FactorIntegerECM.

Мгновенно находится множитель.

Давайте проверим, прост ли он.

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

Поскольку полученное частное является простым числом, мы нашли все простые множители 337-го числа Мерсенна М₃₃₇ и тем самым разложили и этого числового великана на простые множители.