모듈로 (Modulo)

모듈로(modulo, 줄여서 mod)는 정수 a를 양의 정수 n으로 나누었을 때의 나머지를 구하는 연산으로 a mod n이라고 씁니다. 예를 들어 100 = 9 × 11 + 1이므로 100 mod 9 = 1입니다. 이 n을 법(modulus)이라고 하며, 법 n에 대한 모든 계산을 모듈러 산술이라고 합니다.

자세히 알아보기

수학적 정의에서 나머지는 0 이상 n−1 이하로 잡습니다. 그런데 프로그래밍 언어마다 음수 처리가 달라 주의가 필요합니다. 수학에서는 −7 mod 3 = 2이지만, C·자바·자바스크립트의 % 연산자는 −1을 돌려줍니다. 파이썬의 %는 2를 돌려줍니다.

모듈로 연산은 덧셈·곱셈과 잘 어울립니다. (a + b) mod n과 (a × b) mod n은 a, b를 먼저 mod n으로 줄인 뒤 계산해도 결과가 같습니다. 덕분에 아주 큰 수의 거듭제곱 a^e mod n도 중간값을 매번 줄이면서 '제곱 후 곱하기' 방법으로 빠르게 계산할 수 있습니다. 반대로 '결과로부터 지수 e를 찾는' 이산 로그 문제는 큰 법에서 매우 어렵습니다. 이 비대칭성이 공개 키 암호의 핵심입니다.

블록체인·암호화폐에서는

• 타원곡선 서명: secp256k1의 모든 좌표 계산은 소수 p를 법으로, 서명값 계산은 그룹 위수 n을 법으로 이뤄집니다.
• 스마트 컨트랙트: Solidity의 % 연산과 EVM의 MOD, ADDMOD, MULMOD 명령이 모듈로 연산입니다. uint256 산술 자체도 2²⁵⁶을 법으로 합니다.
• 인코딩: 비트코인 주소의 Base58 인코딩은 큰 수를 58로 반복해 나누며 나머지를 글자로 바꾸는 과정입니다.
• 모듈로 편향 주의: 0~255 범위의 난수 바이트에 mod 10을 취하면 0~5가 6~9보다 조금 더 자주 나옵니다(256은 10의 배수가 아니므로). 키·난스 생성에서는 이런 편향을 피하기 위해 범위를 벗어난 값을 버리고 다시 뽑는 거부 표집을 씁니다.

쉽게 말하면

모듈로는 시계 계산입니다. 12시간 시계에서 10시의 5시간 뒤는 15시가 아니라 3시입니다.

예시

(10 + 5) mod 12 = 3. 일요일을 0으로 두면 수요일(3)의 10일 뒤는 (3 + 10) mod 7 = 6, 즉 토요일입니다. 2¹⁰ mod 1000 = 24입니다.

음수의 경우 수학적 정의로는 −7 mod 3 = 2입니다(−7 = 3 × (−3) + 2). 프로그램에서 항상 0 이상의 나머지를 얻으려면 ((a % n) + n) % n처럼 보정합니다.