Возведение в степень Пожалуйста возведите в степень 43^730 mod 522 и 17^1200 mod 1033

Answer 1

вручную через ускоренное возведение

43^0 = 1
43^1 = 43
43^2 = 43^1 * 43^1
43^4 = 43^2 * 43^2
43^8 = 43^4 * 43^4
.
43^512 = 43^256 * 43^256

чтобы не ковыряться с длинными числами, на каждом шаге берем остаток от деления на 522.

дале, расписываем 730 как сумму степеней двойки 730 = 1011011010
и перемножаем степени 43, сответствующие единицам.
43^730 = 43^ (2^9+2^7+2^6+2^4 + 2^3+ 2^1) = 43^512 * 43^128 * 43^64 .
Опять-таки, чтобы не ковыряться большими числами, каждый раз берем остаток от деления на 522.

можно, конечно, и степень разложить и упростить, но лень.