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

Возведение в степень в модулярной арифметике (функция Power Mod)

Иногда приходится решать задачи такого типа:

• найти вычет а^b по модулю n;
• найти последние m цифр числа а^b в системе счисления с основанием с.

Конечно, совсем несложно написать что-нибудь вроде Mod[a^b,n] или Моd[а^b, с^m]. Однако все дело в том, что в исследовательских задачах b может быть столь велико, что для вычисления а^b не хватит памяти. Кроме того, по мере вычисления а^b часто бывает так, что требуется все больше памяти и начинает работать подкачка, что очень часто приводит к пробуксовыванию. А тогда процессор практически простаивает, и даже самая простая операция выполняется фантастически долго.

Пример 7.3.
Наибольшее число, которое можно записать тремя цифрами. Число 9⁹⁹ имеет 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 несложно вычислить, например, первую и последнюю тысячу цифр числа 9⁹⁹. Чтобы вычислить первую тысячу цифр числа 9⁹⁹, нужно просто вычислить это число с разрядностью не менее тысячи знаков. Вот как это делается.

539827016475025109538 Х 10^369693099.