Возведение в степень в модулярной
Возведение в степень в модулярной арифметике — функция Power Mod
Иногда приходится решать задачи такого типа:
- найти вычет аb по модулю n;
- найти последние m цифр числа аb в системе счисления с основанием с.
Конечно, совсем несложно написать что-нибудь вроде Mod[a^b,n] или Моd[а^b, с^m]. Однако все дело в том, что в исследовательских задачах b может быть столь велико, что для вычисления аb не хватит памяти. Кроме того, по мере вычисления аb часто бывает так, что требуется все больше памяти и начинает работать подкачка, что очень часто приводит к пробуксовыванию. А тогда процессор практически простаивает, и даже самая простая операция выполняется фантастически долго.
Пример 7.3. Наибольшее число, которое можно записать тремя цифрами. Число 999 имеет 369 693 100 цифр, т.е. более трети миллиарда! Еще в 1953 году было известно, что это число начинается цифрами 428 124 773 175 747 048 036 987 115 930 563 521 339 055 482 241 443 514 174 753, а заканчивается цифрами 24178799359681422627177289. Какие цифры между ними, не было известно и в 1959 году. Ведь если это число напечатать более или менее четко на полоске бумаги, то эта полоска оказалась бы длиной 1200, а может и 1800 км. Если же напечатать это число в книге так, чтобы на каждой странице помещалось 14 000 цифр (на странице обычно помещается 2,5—3 тысячи знаков), то такая книга состояла бы из 33 томов по 800 страниц в каждом. Но с помощью системы Mathematica несложно вычислить, например, первую и последнюю тысячу цифр числа 999. Чтобы вычислить первую тысячу цифр числа 999, нужно просто вычислить это число с разрядностью не менее тысячи знаков. Вот как это делается.
М[9^(9^9),1000] 4.281247731757470480369871159
30563521339055482241443514174753723053523
887471735048353193665299432033375060417533
64763100078032613904733860832080206037470612
809165574132086446019861999614520310524428581489598115
1471949351767796559302159393385015023969426231
0529675816569433334631474925538494859337781208762
495721650419522060180457130151786405101459407
904194866332733667183065441076023482363342793388473
449171490713928387636703470733221615842638847026446
505858035582482311577827786618011472099436290690473438
366488664695023381735331493288811517612485971201533575
64439876059956217339548503950536965544532955477621833381
799037537429866036175410766960904718339923933145342547022
698333065128258703520736236 343330809161939992399143539
9517426262619225044491488935534629633876424,
710803619094832833935338326811681684096752173716022
71240386424109448631241673361631602584738577273169933875
567294188775379238762791518151971 69574861839692092170993
60780264476440839592643445485180078094839593328
539827016475025109538Х10369693099
Почти так же можно вычислить и последнюю тысячу знаков.
Mod[9^(9^9),10^1000]//Timing{260.64 Second, 164378947574778447311427807670372670 0326359025082234292387746462391127 9751529028988405927046285969119001418 842032015433264756391857718597649 204912230323811027210136918 3684943285741373762637969125845614123744406 01020026085922354 10622770718702230402359356419151296996286668460066302 9835137 9027215796574565344432784903341994543575575416975966278964106 12 7038799025612835366795058993611717249028581457173391518760 2283281383558665788995350272253954345165983917336427507154331 749386377957650223307 168958637197192110578737857336943212457 7155212755139983177854767167859 12996450672962748373653022152 34320507478340927905653712738326405359097 6996351343597753799 283680752817548382724478144536940979972304718417625 894479515 4018072624283659761429188348967918815377285476781074966161266 1854762666853235529005571888491679885547006847358268508973918 700851075402818853925349052912288203971972 4032235787006073283877358282 617004315060225040660196165699439754361026855266374036682906 1901749234943241787 99359681422627177289}
Вычисление, как видите, заняло более четырех минут (260,64 секунды). Но гораздо быстрее результат можно получить вот так.
PowerMod[9,9^9,10^1000]//Timing {0.015 Second, 1643789475747784473114278076703726700...2627177289}
(Здесь середина пропущена.) Это вычисление заняло лишь 0,015 секунды. Это более чем в тысячу (точнее, в 17376) раз быстрее!
Пример 7.4. Графики функции Power Mod.
Давайте теперь построим несколько графиков функции PowerMod. Поскольку это функция двух аргументов, построим изображения поверхности z = PowerMod[x, у]. Для этого используем функцию Plot3D.
