정의

빠른 거듭제곱(Exponentiation by Squaring)은 a^n을 O(log n)에 계산하는 알고리즘입니다. 지수를 반으로 줄이며 제곱하는 방식으로, 단순 곱셈보다 훨씬 빠릅니다. 모듈러 연산과 결합해 암호화에서도 사용됩니다.

핵심 특성

• ✓n이 짝수면: a^n = (a^(n/2))^2
• ✓n이 홀수면: a^n = a × a^(n-1)
• ✓O(log n) 시간복잡도로 매우 빠름
• ✓모듈러 연산과 결합 가능 (오버플로우 방지)

시간 복잡도