расчет по модулю для большого числа

Question

Все,

Как рассчитать 2 ^ 301 мод 77?Я проверил ссылку StackOverflow .Но так и не понял шаг, на котором 625 мод 221 = 183 мод 221. Как происходило преобразование?

Answer 1

Посмотрите на вопрос здесь для ответа на ваш вопрос.

В основном (X * Y) % Z == ((X % Z) * (Y % Z)) % Z.

Итак, в качестве отправной точки, 2^301 % 77 == ((2^150 % 77) * (2^151 % 77)) % 77. Продолжайте разбивать, пока не получите разумные числа, затем рекомбинируйте. Вы сможете сохранять свои номера в разумных пределах на протяжении всего пути.

Answer 2

Я не понимаю вторую часть вашего поста, возможно, потому, что вы не указали ссылку, по которой действительно следовали.Но ваша проблема может быть решена чтением этой страницы и реализацией правильного алгоритма модульного возведения в степень