모듈로 계산기

모듈로 연산 기초

모듈로 연산(a mod m)은 a를 m으로 나눈 나머지입니다. 예: 17 mod 5 = 2. 시계 계산(24시간제), 요일 계산 등 일상에서 자주 사용됩니다. 프로그래밍에서는 배열 인덱스 순환, 해시 함수 등에 필수적입니다.

모듈러 덧셈과 곱셈

모듈러 덧셈: (a + b) mod m. 모듈러 곱셈: (a × b) mod m. 큰 수 계산 시 오버플로우를 방지하려면 각 단계마다 모듈로를 취합니다. 예: (12 + 8) mod 5 = 20 mod 5 = 0.

모듈러 거듭제곱 - 빠른 계산

a^b mod m을 계산할 때 직접 거듭제곱하면 수가 너무 커집니다. 분할정복 방식의 빠른 거듭제곱 알고리즘을 사용하면 O(log b) 시간에 계산 가능합니다. RSA 암호화의 핵심 연산입니다.

모듈러 역원 - 확장 유클리드 알고리즘

모듈러 역원은 (a × x) mod m = 1이 되는 x입니다. a와 m이 서로소일 때만 존재합니다. 확장 유클리드 알고리즘으로 O(log m) 시간에 계산합니다. 암호 해독, 분수 계산에 사용됩니다.

RSA 암호화와 모듈러 연산

RSA는 모듈러 거듭제곱과 역원을 핵심으로 하는 공개키 암호 시스템입니다. 암호화: c = m^e mod n, 복호화: m = c^d mod n. 큰 소수 두 개의 곱 n을 인수분해하기 어렵다는 점을 이용합니다.