power tower 를 오일러 정리 적용하여 계산하기.

오일러 정리는 a^phi(m) === 1 (mod m) // (gcd(a,m) = 1일때) ..  을 사용하여, a^(T mod phi(m)) mod m = a^T mod m 으로 나타낼 수 있는거에요. 그런데 오일러 정리는 (gcd(a,m) = 1일때)만 성립하기 때문에, 일반적인 상황에 적용시키기 어려워 보입니다.

 

https://stackoverflow.com/questions/21367824/how-to-evalute-an-exponential-tower-modulo-a-prime

How to evalute an exponential tower modulo a prime

이 글을 보면 사이클 찾아서 뭐 일반화 시키는데 결과적으로는

 

a^(ϕ(m)+(Tmodϕ(m))) modm 이걸로 쓰면 된다는거임.. 지수에다가 피함수 한번 더 얹어주면 됩니다.

 

증명은 나중에 보자~