모듈러 거듭제곱 계산기

모듈러 거듭제곱 계산기 정보

모듈러 거듭제곱 계산기는 \(a^b \bmod n\)을 계산합니다. 즉, 밑 \(a\)를 지수 \(b\)만큼 거듭제곱하고 모듈러스 \(n\)으로 나눈 나머지를 구합니다. 이 계산기는 이진 거듭제곱 알고리즘(빠른 거듭제곱 또는 거듭제곱법에 의한 거듭제곱이라고도 함)을 사용하며, 이는 연산을 \(O(b)\)번의 곱셈에서 단 \(O(\log b)\)번으로 줄여줍니다. 이 알고리즘은 RSA, Diffie-Hellman, ElGamal과 같은 실제 암호화 구현에 사용되는 것과 동일합니다.

모듈러 거듭제곱의 응용 분야

이진 거듭제곱 알고리즘의 작동 원리

핵심 아이디어는 이진 표현을 사용하여 모든 지수를 2의 거듭제곱의 합으로 분해할 수 있다는 것입니다. 예를 들어, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\)이므로, \(a^{13} = a^{8} \times a^{4} \times a^{1}\)이 됩니다.

알고리즘은 지수의 이진 숫자를 왼쪽에서 오른쪽으로 처리합니다:

의사 코드 (Pseudocode)

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // 비트가 1인 경우
            result = (result × base) mod mod
        exp = exp >> 1        // 오른쪽으로 시프트 (2로 나누기)
        base = (base × base) mod mod
    return result

주요 공식

모듈러 거듭제곱 계산기 사용 방법

1. 밑 (a) 입력: 거듭제곱할 숫자를 입력합니다. 양수와 음수 모두 가능합니다. 예를 들어 7^256 mod 13을 계산하려면 7을 입력합니다.
2. 지수 (b) 입력: 음이 아닌 정수여야 합니다. 거듭제곱 횟수를 나타냅니다. 암호학적 응용을 위해 매우 큰 숫자도 지원합니다(최대 10^18).
3. 모듈러스 (n) 입력: 양의 정수여야 합니다. 나머지를 구하기 위해 나눌 숫자입니다. RSA에서는 보통 두 거대 소수의 곱이 사용됩니다.
4. 계산하기 클릭: 계산기가 이진 거듭제곱을 사용하여 a^b mod n을 계산하고 즉시 결과를 보여줍니다.
5. 애니메이션 시청: 재생 버튼을 눌러 이진 거듭제곱 알고리즘이 단계별로 실행되는 것을 확인하세요. 지수의 각 비트가 순서대로 처리되며 제곱 또는 제곱 후 곱셈 과정이 표시됩니다.
6. 추적 결과 검토: 단계별 표에는 모든 중간 계산 과정이 표시되며, 효율성 비교를 통해 단순 반복 곱셈보다 이진 거듭제곱이 얼마나 빠른지 확인할 수 있습니다.

이진 거듭제곱이 빠른 이유

\(2^{1000} \bmod 13\)을 계산한다고 가정해 봅시다. 단순한 접근 방식은 999번의 곱셈이 필요합니다. 이진 거듭제곱은 1000을 이진수(1111101000, 10비트)로 변환합니다. 이 경우 최대 9번의 제곱과 '1'인 비트에 대한 몇 번의 곱셈, 즉 총 약 15번의 연산만 필요합니다. 이는 약 98.5% 더 적은 연산입니다. 수백 자리 숫자의 지수를 사용하는 암호학적 규모에서는 그 차이가 천문학적입니다. 이진법은 수천 번의 연산으로 끝나지만, 단순 계산법은 우주의 원자 수보다 더 많은 연산이 필요할 수도 있습니다.

자주 묻는 질문 (FAQ)