Алгебра и пакет 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[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-е число Мерсенна Мхи — составное. Вот этот супервеликан.
С помощью системы Mathematica можно почти мгновенно убедиться, что это число составное.
PrimeQ[M5011] False Однако неплохо было бы найти хотя бы какой-нибудь его делитель.
m=FactorIntegerECM[M5011]
Системе Mathematica потребуется менее 36 секунд, чтобы найти делитель m = 80177. Теперь проверим, прост ли найденный делитель.
PrimeQ[m] True
Оказывается, да! Есть шансы разложить 5011-е число Мерсенна M5011 на простые множители? Давайте попытаемся. Для этого разделим 5011-е число Мерсенна Мт] на найденный делитель.
Но простое ли число nl Давайте проверим.
PrimeQ[n] False
Нет. В таком случае к нему можно применить функцию FactorIntegerECM. Но на этот раз результата не дождаться даже за несколько часов... Конечно же, функция FactorIntegerECM чрезвычайно эффективна, но всех проблем теории чисел она решить не может...
Функция FactorIntegerECM: поиск делителей М13 -го числа Мерсенна М8191= М13
Но все же ситуация не столь безнадежна. Некоторые специалисты по теории чисел, например, долгое время считали, что если число Мерсенна Mn, является простым, то и число МMn тоже простое. Это действительно так для четырех наименьших простых чисел Мерсенна. Но лишь в 1953 году Д. Ю. Уиллер показал, что для пятого простого числа Мерсенна это не так. Пятое простое число Мерсенна М13 = 8191, однако число A/W], имеющее 2466 цифр, является составным. Тем не менее в течение более чем десятилетия после .открытия Уиллера не удалось найти ни одного его простого делителя. С помощью функции FactorIntegerECM это можно сделать за считанные минуты (само число Мм в распечатке опущено).
ММ13=2^8191-1
m=FactorIntegerECM[MM13]
338193759479
С другой стороны, давно было известно, что М17и M19 — простые числа. Кроме того, еще в 1957 году было доказано, что MM17 делится на n1 = 1768(2'7-1)+1 = 231733529, а ММn — на n2= 120(2|9-1)+1 =62914441. Тем не менее функция FactorIntegerECM, не говоря уже о функции FactorInteger, не может обнаружить ни одного нетривиального делителя МM17 или MM19 . Интеллект человека сильнее. Мораль: Хотя всех проблем теории чисел решить не может даже функция FactorlntegerECM, воспринимать это следует без излишнего пессимизма...
