네 개의 정수 p, q, r, k가 주어졌을 때, 러시아 농민 곱셈(Russian Peasant Multiplication) 기법을 활용하여 복소수 거듭제곱 (p + qi)r = r + si를 계산하고, 그 결과인 r mod k와 s mod k를 구하는 프로그램을 만들어 보겠습니다.
예를 들어 입력값이 p = 3, q = 0, r = 8, k = 10000이라면 출력은 (6561, 0)이 됩니다. 38 = 6561이고, q = 0이므로 허수 부분이 0이기 때문입니다.
해결 접근 방법
이 문제는 거듭제곱을 반복적으로 제곱 형태로 분해하여 계산 횟수를 줄이는 것이 핵심입니다. 복소수의 성질을 이용하면 (p + qi)2 = (p² − q²) + 2pq·i가 되므로, 지수를 절반씩 줄여가며 재귀적으로 처리할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- r이 0인 경우: 1을 반환합니다.
- r이 1인 경우: (p mod k, q mod k) 쌍을 반환합니다.
- r이 짝수인 경우: 실수부와 허수부를 각각 (p*p − q*q) mod k와 2*p*q mod k로 갱신한 뒤, solve((p*p − q*q) mod k, 2*p*q mod k, r/2, k)를 재귀 호출합니다.
- r이 홀수인 경우: 먼저 (pr, qr) = solve(p, q, r−1, k)를 구한 후, ((p * pr − q * qr) mod k, (p * qr + q * pr) mod k)를 반환합니다.
예제 코드
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다. 정확한 정수 연산을 위해 지수를 절반으로 나눌 때 정수 나눗셈 연산자(//)를 사용했습니다.
def solve(p, q, r, k):
if r == 0:
return 1
elif r == 1:
return (p % k, q % k)
elif r % 2 == 0:
return solve((p*p - q*q) % k, 2*p*q % k, r//2, k)
else:
(pr, qr) = solve(p, q, r-1, k)
return ((p * pr - q * qr) % k, (p * qr + q * pr) % k)
print(solve(3, 0, 8, 10000))입력
3, 0, 8, 10000
출력
(6561, 0)
정리
이 알고리즘은 일반적인 거듭제곱 계산에 필요한 O(r)번의 곱셈 대신, 지수를 절반씩 줄여나가는 방식으로 약 O(log r)번의 곱셈만 수행하면 됩니다. 덕분에 r이 매우 큰 경우에도 모듈로 연산과 결합하면 오버플로우 없이 빠르게 결과를 얻을 수 있으며, 이것이 러시아 농민 곱셈 기법이 암호학 등 대규모 정수 연산 분야에서 널리 활용되는 이유입니다.