모듈러 산술 계산기
입력
| 연산 | a mod n |
|---|---|
| a | 17 |
| 법 n | 5 |
| 지수 b | 3 |
모듈러 산술 계산기
a mod n, 모듈러 거듭제곱(a^b mod n), 모듈러 역원을 계산합니다. 정수론의 나머지 연산 원리와 빠른 거듭제곱 알고리즘을 다룹니다.
입력
결과
값을 입력하면 계산 결과가 표시됩니다.
세부 정보
모듈러 산술은 정수를 고정된 정수로 나눈 나머지를 기준으로 분류하는 정수론의 한 분야입니다. 두 정수 a와 b의 차가 n의 배수일 때 이 둘은 n을 법으로 합동이라 하며, a ≡ b (mod n)으로 표기합니다. 이 계산기는 나머지 연산, 모듈러 거듭제곱, 모듈러 역원의 세 가지 연산을 지원합니다.
나머지 연산 (a mod n)
양의 정수 n에 대해 a mod n은 다음 조건을 만족하는 유일한 정수 r로 정의됩니다.
a=q×n+r,0≤r<n여기서 q = ⌊a / n⌋은 바닥 몫이고, r은 나머지입니다. 이 정의는 항상 음이 아닌 결과를 보장합니다.
계산 예시. a = 17, n = 5인 경우:
q=⌊517⌋=3,r=17−3×5=2따라서 17 mod 5 = 2입니다. 시계 바늘로 비유하면, 5칸짜리 시계에서 17칸을 이동했을 때 멈추는 위치가 2칸입니다.
음수 처리. a = −7, n = 5인 경우:
q=⌊5−7⌋=−2,r=−7−(−2)×5=3따라서 −7 mod 5 = 3입니다. C, JavaScript 같은 언어의 % 연산자는 절삭 나머지를 사용하여 −2를 반환하지만, 이 계산기는 항상 [0, n − 1] 범위의 수학적 나머지를 계산합니다.
모듈러 거듭제곱 (a^b mod n)
a^b를 먼저 계산한 뒤 n으로 나누는 직접 방법은 지수가 커질수록 비현실적입니다. 예를 들어 17^1000은 자릿수가 1,000을 훨씬 넘어 메모리에 저장조차 어렵습니다.
**제곱-곱셈법(빠른 모듈러 거듭제곱)**은 지수를 이진수로 분해하여 이 문제를 해결합니다. 각 단계에서 현재 값을 제곱하고 n으로 나눈 나머지를 취하므로, 중간 값이 항상 [0, n − 1] 범위 안에 유지됩니다. 곱셈 횟수는 b − 1회 대신 최대 2 log₂(b)회로 줄어듭니다.
계산 예시. a = 17, b = 3, n = 5인 경우:
17≡2(mod5) 172≡4(mod5) 173=172×17≡4×2=8≡3(mod5)따라서 17^3 mod 5 = 3입니다. 직접 확인: 17^3 = 4,913 = 982 × 5 + 3.
모듈러 역원 (a⁻¹ mod n)
a의 모듈러 역원은 다음을 만족하는 정수 x입니다.
a×x≡1(modn)이 역원은 gcd(a, n) = 1, 즉 a와 n이 서로소일 때만 존재합니다. n이 소수이면 1부터 n − 1까지의 모든 정수에 역원이 존재하고, n이 합성수이면 n과 공약수를 가지는 값은 역원이 없습니다.
확장 유클리드 알고리즘은 역원을 구하는 표준적인 방법입니다. 이 알고리즘은 유클리드 호제법을 확장하여, gcd(a, n) = 1인 경우 다음을 만족하는 정수 s, t를 구합니다.
a×s+n×t=1이때 s를 n으로 나눈 나머지가 a의 모듈러 역원입니다.
계산 예시. a = 3, n = 5인 경우, 확장 유클리드 알고리즘을 적용하면:
- 5 = 1 × 3 + 2
- 3 = 1 × 2 + 1
역대입으로 정리하면: 1 = 3 − 1 × 2 = 3 − 1 × (5 − 1 × 3) = 2 × 3 − 1 × 5
따라서 3 × 2 ≡ 1 (mod 5)이므로 3⁻¹ ≡ 2 (mod 5)입니다.
검증: 3 × 2 = 6 = 1 × 5 + 1.
바닥 몫과 유클리드 등식
n ≥ 1인 모든 정수 쌍 (a, n)에 대해 바닥 몫 q = ⌊a / n⌋과 나머지 r = a mod n은 다음 유클리드 등식을 만족합니다.
a=q×n+r,0≤r<n이 계산기는 r과 q를 함께 표시하여 임의의 입력에 대해 이 등식을 직접 확인할 수 있게 합니다.
활용 분야
모듈러 산술은 수학과 컴퓨팅 전반에 걸쳐 사용됩니다.
- 공개키 암호화. RSA 암호화는 큰 소수 두 개의 곱을 법으로 하는 모듈러 거듭제곱에 기반하며, 복호화에는 모듈러 역원을 사용합니다.
- 체크섬. ISBN-13, IBAN, 신용카드의 루한 알고리즘은 모두 모듈러 산술로 입력 오류를 검출합니다.
- 요일 계산. d일 후의 요일은 현재 요일에 d를 더한 뒤 7로 나눈 나머지로 결정됩니다.
- 해시 테이블. 키를 버킷 인덱스에 매핑할 때 key mod table_size 연산을 사용합니다.
- 순환 자료구조. 링 버퍼와 원형 배열에서 읽기·쓰기 포인터를 index mod capacity로 갱신합니다.
자주 묻는 질문 (FAQ)
음수에서 나머지 연산과 mod의 결과가 다른 이유는 무엇입니까?
수학적 정의의 mod 연산은 결과가 항상 [0, n − 1] 범위에 속합니다. 예를 들어 −7 mod 5 = 3인데, 이는 −7 = (−2) × 5 + 3이기 때문입니다. 반면 C, JavaScript 등 많은 프로그래밍 언어의 % 연산자는 절삭 나머지를 사용하여 −7 % 5 = −2를 반환합니다. 이 계산기는 수학적 정의를 따릅니다.
17^1000 mod 5처럼 큰 거듭제곱은 어떻게 효율적으로 계산합니까?
빠른 모듈러 거듭제곱(제곱-곱셈법)은 지수를 이진수로 분해하여 곱셈 횟수를 O(log b)로 줄입니다. 각 단계에서 현재 거듭제곱값을 제곱하고 필요한 경우 밑수를 곱한 뒤, 매 단계마다 n으로 나눈 나머지를 취해 중간 값이 커지는 것을 방지합니다.
모듈러 역원은 언제 존재합니까?
a⁻¹ mod n의 역원이 존재하려면 gcd(a, n) = 1, 즉 a와 n이 서로소여야 합니다. n이 소수이면 1부터 n − 1까지의 모든 정수는 역원을 가집니다. n이 합성수이면 n과 공약수를 가지는 값은 역원이 존재하지 않습니다.
모듈러 산술은 실제로 어디에 사용됩니까?
모듈러 산술은 공개키 암호화(RSA는 모듈러 거듭제곱과 역원에 기반합니다), 해시 함수, 체크섬(ISBN, IBAN, 신용카드 루한 알고리즘), 요일 계산(7을 법으로 하는 주기), 해시 테이블의 버킷 인덱싱, 링 버퍼 등 순환 자료구조에 폭넓게 활용됩니다.