거듭제곱 썸네일형 리스트형 거듭제곱 계산하기 RSA 암호화를 하는 과정에 있어서 거듭 제곱을 계산할 필요가 있습니다. $a^n$을 계산할 때 for이나 while 문과 같이 반복문을 이용해서 $n$번을 곱하는 방법이 가장 쉽게 생각할 수 있는 방법입니다. def easy_mod_pow(base, exp, mod): base %= mod result = 1 while exp > 0: result = (result * base) % mod; exp -= 1 return result 이 알고리즘의 경우에는 시간 복잡도를 생각하면 $O(n)$이라는 것을 알 수 있습니다. (반복문이 n번 돌기 때문) 즉 $n$의 값이 크면 그 만큼 속도가 느려진다는 것을 의미하고, RSA 암호화 과정에서는 $n$의 값을 큰 것으로 사용하기 때문에 이러한 방법으로는 어렵다는.. 이전 1 다음