2010년부터 · 매월 200만 회 이상의 도구 사용을 지원합니다
2010년부터
Chrome에 추가

내 도구함

자동 모드

저장된 도구가 없습니다.

프리미엄 버전으로 업그레이드하기
관련 도구
모듈러 곱셈 역원 계산기중국인의 나머지 정리 계산기확장 유클리드 알고리즘 계산기복소수 계산기부분 분수 분해 계산기메르센 소수 체커
홈페이지 > 수학 관련 도구 > 고급 수학 연산 도구
 

모듈러 거듭제곱 계산기

이진 거듭제곱 알고리즘으로 a^b mod n을 효율적으로 계산합니다. 밑, 지수, 법을 입력하면 결과와 함께 제곱-곱 단계별 풀이, 이진 분해 시각화, 암호학적 맥락을 확인합니다.

무료로 사용가입 필요 없음즉시 결과 확인
모듈러 거듭제곱 계산기지금 무료로 사용하기 ▼
예시:
계산 중
ab mod n
^
mod

모듈러 거듭제곱 계산기 위젯 삽입

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

모듈러 거듭제곱 계산기는 \(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 복호화

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

  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)

모듈러 거듭제곱이란 무엇인가요?
모듈러 거듭제곱은 (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

개발자 API 사용 가능: 이 도구를 앱, 자동화, 에이전트에서 한 번의 JSON HTTP 요청으로 실행할 수 있습니다. API 문서 보기

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

고급 수학 연산 도구:

인기·최신 도구:

연분수 계산기원시근 계산기지수 계산기모두 보기 →
홈페이지 > 수학 관련 도구 > 고급 수학 연산 도구 > 모듈러 거듭제곱 계산기