이진 거듭제곱은 어떻게 작동하나요?

이진 거듭제곱(거듭제곱법에 의한 거듭제곱이라고도 함)은 지수를 이진수로 변환한 다음 각 비트를 왼쪽에서 오른쪽으로 처리합니다. 각 비트에 대해 현재 결과를 제곱(모듈러 연산 포함)합니다. 비트가 1이면 밑을 한 번 더 곱합니다(모듈러 연산 포함). 이를 통해 곱셈 횟수를 b-1번에서 최대 2*log2(b)번으로 줄일 수 있습니다.

모듈러 거듭제곱 계산기

이진 거듭제곱(빠른 거듭제곱) 알고리즘을 사용하여 모듈러 거듭제곱 a^b mod n을 효율적으로 계산하세요. 밑, 지수, 모듈러를 입력하면 제곱 후 곱셈 방식의 단계별 분석, 이진 분해 시각화 및 암호학적 맥락과 함께 즉각적인 결과를 얻을 수 있습니다.

모듈러 거듭제곱 계산기

Embed 모듈러 거듭제곱 계산기 Widget

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

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

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

🔐

RSA 암호화

거대한 소수의 곱을 모듈러스로 사용하는 모듈러 거듭제곱을 통해 메시지를 암호화 및 복호화합니다.

🤝

Diffie-Hellman

안전한 공유 비밀키를 생성하기 위해 g^a mod p를 계산하는 키 교환 프로토콜입니다.

✍

디지털 서명

DSA, ECDSA, EdDSA는 모두 모듈러 거듭제곱 연산에 의존합니다.

🧪

소수 판별법

페르마 및 밀러-라빈 검사는 a^(n-1) mod n을 사용하여 소수 여부를 확인합니다.

🏆

프로그래밍 대회

빠른 거듭제곱을 활용한 모듈러 산술은 알고리즘 문제 해결의 필수 요소입니다.

🔗

블록체인

작업 증명과 암호화 해싱은 모듈러 산술에 크게 의존합니다.

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

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

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

단계 1: 지수 \(b\)를 이진수로 변환합니다.

단계 2: 결과값을 1로 초기화합니다(또는 첫 번째 비트가 1이면 밑으로 초기화).

단계 3: 후속 각 비트에 대해: 결과값을 제곱합니다(mod n). 비트가 1이면 밑을 추가로 곱합니다(mod n).

단계 4: 모든 비트를 처리한 후의 결과가 \(a^b \bmod n\)입니다.

의사 코드 (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

주요 공식

속성	공식	설명
모듈러 거듭제곱	\(a^b \bmod n\)	a^b를 n으로 나눈 나머지
페르마의 소정리	\(a^{p-1} \equiv 1 \pmod{p}\)	소수 p와 gcd(a,p)=1인 경우
오일러의 정리	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	gcd(a,n)=1인 경우 (φ는 오일러 피 함수)
이진법 복잡도	\(O(\log b)\)번 곱셈	최대 2·log₂(b)번의 모듈러 곱셈
RSA 암호화	\(c = m^e \bmod n\)	공개키 (e, n)으로 메시지 m 암호화
RSA 복호화	\(m = c^d \bmod n\)	개인키 d로 암호문 c 복호화

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

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

이진 거듭제곱이 빠른 이유

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

자주 묻는 질문 (FAQ)

모듈러 거듭제곱이란 무엇인가요?

모듈러 거듭제곱은 (a^b) mod n을 계산하는 것입니다. 밑을 지수만큼 거듭제곱한 다음 모듈러스로 나눈 나머지를 취합니다. 이는 공개키 암호화(RSA, Diffie-Hellman, ElGamal)의 핵심 연산이며 정수론, 알고리즘 대회, 컴퓨터 과학에서 광범위하게 사용됩니다. 이진 거듭제곱법을 통해 O(log b)번의 곱셈으로 효율적으로 계산할 수 있습니다.

이진 거듭제곱(거듭제곱법에 의한 거듭제곱)은 어떻게 작동하나요?

이진 거듭제곱은 지수를 이진 표현으로 변환한 후 각 비트를 왼쪽에서 오른쪽으로(또는 오른쪽에서 왼쪽으로) 처리합니다. 각 비트마다 현재 결과를 모듈러스 n에 대해 제곱합니다. 비트가 1이면 추가로 결과에 밑을 곱하고 모듈러 연산을 수행합니다. 이를 통해 곱셈 횟수를 b-1번(단순 계산)에서 최대 2×log₂(b)번으로 줄여 거대한 지수도 계산 가능하게 만듭니다.

암호학에서 모듈러 거듭제곱이 왜 중요한가요?

RSA 암호화는 암호화 시 c = m^e mod n, 복호화 시 m = c^d mod n을 계산하며, 여기서 n은 두 거대 소수의 곱이고 지수는 수백 자리에 달할 수 있습니다. 빠른 모듈러 거듭제곱 없이는 이러한 연산이 실시간으로 이루어질 수 없습니다. 보안의 핵심은 역연산(이산 로그 계산)이 사실상 불가능하다는 점에 있습니다.

밑이 음수일 수 있나요?

네, 음수 밑도 완벽하게 지원됩니다. 계산기는 먼저 밑을 모듈러스 n으로 나눈 나머지로 변환합니다(양의 n에 대해 항상 0 이상의 결과를 반환하는 Python의 모듈러 산술 방식 사용). 예를 들어, (−3)^2 mod 7 = 9 mod 7 = 2입니다. 모듈러 축소는 항상 [0, n−1] 범위의 값을 생성하므로 음수 결과는 발생하지 않습니다.

모듈러스가 1이면 어떻게 되나요?

모든 정수를 1로 나눈 나머지는 0입니다. 어떤 정수를 1로 나누면 나머지가 0인 정수 자체가 나오기 때문입니다. 따라서 a와 b 값에 관계없이 a^b mod 1 = 0이 됩니다. 계산기는 이를 특수 사례로 처리합니다.

이 콘텐츠, 페이지 또는 도구를 다음과 같이 인용하세요:

"모듈러 거듭제곱 계산기" - https://MiniWebtool.com/ko/모듈러-거듭제곱-계산기/에서 MiniWebtool 인용, https://MiniWebtool.com/

MiniWebtool 팀 제작. 업데이트: 2026-04-16

또한 저희의 AI 수학 해결사 GPT를 사용하여 자연어 질문과 답변으로 수학 문제를 해결할 수 있습니다.