возведение в степень по модулю

Ответ от Spin722[гуру]
Воспользуйся свойством ( a * b ) mod c = ( ( a mod c ) * ( b mod c ) ) mod c Твой пример расписывать не буду - много писанины. Возьму более простой пример. 2^9 mod 5 = 512 mod 5 = 2 (легко проверить на калькуляторе или на листике) Теперь, если пользоваться указанным свойством 2^9 mod 5 = ((2^3 mod 5)(2^3 mod 5)(2^3 mod 5)) mod 5 = (3*3*3) mod 5 = 27 mod 5= 2 Есть еще такая запись указанного свойства ( a ^ b ) mod c = ( ( a mod c ) ^ b ) mod c(оно равносильно предыдущему, только запись через степень) . Можешь понижать степень до тех пор, пока не найдешь результат. Есть еще такой метод - больше подходит для написания программ для вычислительных машин. a^25 mod m. Переводим 25 (показатель степени в двоичную систему) 25 (дес) = 11001 (двоич) =2^4 + 2^3 + 2^0 таким образом a^25 mod n = (a * a^24) mod n = (a * a^8 * a^16) mod n = = (a * (( a^2) ^2) ^2 * ((( a^2 ) ^2 ) ^2 ) ^2 mod n = = (((( a^2 * a ) ^2 ) ^2 ) ^2 * a) mod n таким образом a^25 можно вычислить по формуле: ((((((( a^2 mod n ) * a ) mod n ) ^2 mod n ) ^2 mod n ) ^2 mod n ) ^2 mod n) * a * mod n Удачи.