Функция FactorIntegerECM попытка
Функция 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[10Am] Prime[10Лт+1]
Вот что получилось:
12 899773470806612917304808883
Теперь давайте разложим п (оно составное, так как является произведением двух последовательных достаточно больших простых чисел).
FactorIntegerECM[n]
И вот один из сомножителей: 29996224275851
Вот еще один пример применения функции FactorIntegerECM.
n=(2^58 - 27) * (2^127 - 1) 4903985730770843887365 5151436140637119954221204852703259
Теперь ищем какой-нибудь делитель этого числа.
288230376151711717
Наконец, освоившись с функцией FactorIntegerECM на этих более или менее простых примерах, можем попытаться применить ее к факторизации числа Мерсенна Мт. Как мы помним, оно имеет делитель 9511. Сначала убедимся, что он простой.
PrimeQ[9511] True
Теперь можем разделить на него число Мерсенна М317.
n=(2Л317-1)/9511 28072587476617996036103218722657345 63403827834029876945046579760043922 4658035965592773657961
После этого нужно убедиться, что это число составное.
PrimeQ[n] False
Значит, можно применить функцию FactorIntegerECM.
m=Factor!ntegerECM[n]
Через 205,375 с (процессор Pentium 2,4 ГГц) получаем один из его делителей:
587492521482839879 Он простой.
PrimeQ[m] True
Поэтому можем заниматься только частным n = n/m.
n=n/m
477837358776284792683873587315
9342707436119775645430680034874628800586
6959
Опять нужно проверить, простое ли оно.
PrimeQ[n]
Эта проверка занимает всего лишь 0,016 с, и оказывается, что оно составное.
False
Значит, можем снова применить функцию FactorIntegerECM.
m=Factor!ntegerECM[n]
На этот раз понадобится 727,047 с, чтобы найти очередной делитель. 4868122671322098041565641
Снова нужно проверить, прост ли найденный делитель. PrimeQ[m]
Эта проверка выполняется пoчти мгновенно, и оказывается, что делитель действительно прост.
True
Значит, снова можем заниматься только частным n= n/m.
n=n/m 9815639231755686605031317440031161584572466128599
Опять нужно проверить, простое ли оно.
PrimeQn]
Эта проверка занимает всего лишь 0,015 с, и оказывается, что найденное частное является простым числом.
PrimeQ[ n] True
Таким образом, мы нашли все простые множители 317-го числа Мерсенна М317 и тем самым разложили этого числового великана на простые множители.
М317 = 9511X587492521482839879X486812267 1322098041565641X981563923175568 6605031317440031161584572466128599
Факторизация 337-го числа Мерсенна М337
Чтобы освоить методику применения функций Factorlnteger и FactorIntegerECM, попробуем разложить на простые множители 337-е число Мерсенна M337. Сначала можно попытаться применить функцию Factorlnteger. Но как и в случае 317-го числа Мерсенна M317, это не даст результата за приемлемое время. Тогда применим функцию Factorlnteger с опцией FactorComplete->False, чтобы найти хоть какие-нибудь делители 337-го числа Мерсенна М337.
Factorlnteger[2^337-1,FactorComplete->False]
Результат будет таким.
Factorlnteger::facfn: Unable to factor 57238939242563 «51» 465444456568561. More...
Зато чуть ниже будут найдены делители.
{{18199, 1}, (2806537,1), (95763203297, 1}, {572389392425637497118853974356 80799950268490508661316904465621201465444456568561, 1}}
Иными словами,
М337=18199X2806537X95763203297X572389392425637 497118853974356807999502 68490508661316904465621201465444456568561
Теперь нужно проверить, просты ли найденные делители.
PrimeQ[18199] True PrimeQ[2806537] True PrimeQ[95763203297] True PrimeQ[5723893924256374971188539743568079 99502684905086613169044656212 01465444456565-61] False
Как видите, все они, за исключением последнего (обозначим его временно через n), самого большого, простые. (Все это заняло менее двух секунд.)
Поскольку 337 — простое число (я опять специально подобрал индекс числа Мерсенна), формулы сокращенного умножения "в лоб" применить не удастся. Но ведь мы можем загрузить пакет теории чисел.
<<NumberTheory"FactorIntegerECM`
Теперь, когда пакет загружен, можно вызвать функцию FactorIntegerECM.
FactorIntegerECM[572389392425637497118
85397435680799950268490508661316 90446562120146544445656561]
Мгновенно находится множитель.
726584894969
Давайте проверим, прост ли он.
PrimeQ[726584894969]
True
Оказывается, прост. Поэтому разделим на найденный множитель полученное на предыдущем шаге число, присвоим частное переменной п и проверим, является ли частное простым числом.
n=57238939242563749711885397435680799950268490 508661316904465621201465 44445656561/726584894969 787780473264667429936124208424161983 11394008068822475527239136925369 PrimeQ[n] True
Поскольку полученное частное является простым числом, мы нашли все простые множители 337-го числа Мерсенна М337 и тем самым разложили и этого числового великана на простые множители.
М337=18199x2806537x95763203297x 726584894969x787780473264667429 93612420 842416198311394008068822475527239136925369
Функция FactorIntegerECM: поиск делителей 5011 -го числа Мерсенна М5011
Функция FactorlntegerECM иногда может находить делители таких чисел, которые можно смело отнести к разряду супервеликанов. Еще в середине прошлого столетия было известно, что 5011-е число Мерсенна Мхи — составное. Вот этот супервеликан.
