Вычислить a^n mod m

[spyphy]

Исходная задача $5^{614} \pmod {1135}$ с помощью теоремы Ферма свелась к $5^{161} \pmod {227}$. Можно ли последнее посчитать вручную?

[nnosipov]

Легко. Используйте бинарный алгоритм.

Можно также заменить показатель $161$ на $-65$, но сначала нужно будет алгоритмом Евклида найти $5^{-1} \bmod{227}$.

[spyphy]

nnosipov в сообщении #919264 писал(а):

Легко. Используйте бинарный алгоритм.

а где его взять?
где почитать?
Нужны примеры решения таких задач. наверняка они здесь не раз появлялись, но сейчас ничего не могу найти.

[nnosipov]

Гуглите "Алгоритмы быстрого возведения в степень по модулю". Примеры сами сочините, проверку можно проделать в какой-нибудь системе компьютерной алгебры.

[spyphy]

nnosipov в сообщении #919274 писал(а):

Гуглите "Алгоритмы быстрого возведения в степень по модулю".

Дело в том, что подавляющее большинство того, что попадается в сети на эту тему, предназначенно для реализации на ПК, но не адаптировано под ручной счет

[nnosipov]

Бинарный алгоритм (последовательное возведение в квадрат) довольно прост. Разберите его прямо на Вашем примере.

[spyphy]

да, я понял как работает этот алгоритм. но правда без калькулятора здесь всё равно не обойдешься )