modular exponentiation

a^b mod c 를 구하는 알고리즘이다.
단순하게 a^b를 하고 c로 나머지를 하면 프로그래밍에서 오버플로우가 발생하기 때문에,
중간과정에 modular 연산을 해줌으로써 오버플로우를 방지한다.
물론 이렇게 해도 결과가 달라지는 일은 없다고 한다.

b승을 단순히 a를 b번 곱하는 식으로 하게 되면 O(b)의 시간복잡도가 생기는데,
이것은 빠른 방법이 아니다.
이에 관련된 알고리즘엔 여러가지가 있는데,
이 중 하나의 방법으로 2씩 나눠가는 방법이 있다.
a^b = (a^2)^(b/2) 라는것을 이용하여 O(log2(b)) 의 시간복잡도 안에 해결 가능하다.

소스