| 나머지 r | 몫 q | 승수 t |
|---|
모듈러 시계
9시에서 5시간 뒤는 2시입니다. 9 + 5 = 14이고 14는 12보다 2 크기 때문입니다. 이것이 모듈러 산술, 즉 n 다음에 다시 0부터 시작하는 시계 위에서 세는 것입니다. 연산을 고르고 n, a, b를 입력하면 계산기가 나눗셈의 나머지부터 반복 제곱법과 확장 유클리드 알고리즘까지 모든 단계를 적어 가며 답을 알려 주고, 시계는 그 답에 어떻게 도달하는지 보여 줍니다. 연산을 고른 다음 법 n과 수 a, b를 입력하세요. 30자리까지의 정수를 쓸 수 있고 음수도 되며, n은 10^18까지 가능합니다. 시계에는 n개의 위치가 있고 0이 맨 위에 있으며, 바늘이 답을 가리킵니다. 덧셈과 뺄셈은 b걸음의 나선으로 그려지며 한 바퀴를 돌 때마다 고리가 하나씩 생기고, 곱셈은 a씩 뛰는 점프로, 거듭제곱은 하나의 순환으로 닫히는 현 a, a², a³ …으로, 역원과 나눗셈은 1이나 a에 떨어지는 배수로 그려집니다. 단계에서는 같은 계산을 숫자로 보여 줍니다. mod 20까지는 연산표가 표시되며, 칸을 클릭하면 그 수를 사용할 수 있습니다. ‘예제’를 고르면 고전적인 문제가 입력됩니다.
작동 원리
- 연산을 고르세요: a mod n, 덧셈, 뺄셈, 곱셈, 나눗셈, 거듭제곱 또는 a의 역원.
- 법 n과 수 a, b를 입력하거나, 7^2026의 일의 자리나 작은 RSA 메시지 같은 예제를 고르세요.
- 답과 단계를 읽고 시계 위의 경로를 따라가 보세요. mod 20까지는 표의 칸을 클릭해 그 수를 시험해 볼 수 있습니다.
a mod n의 뜻
a mod n은 a를 n으로 나눈 나머지입니다: 17 = 3 × 5 + 2이므로 17 mod 5 = 2입니다. 나머지는 음수일 때도 항상 0부터 n − 1까지입니다: −7 = −3 × 3 + 2이므로 −7 mod 3 = 2입니다. 시계에서는 0에서 거꾸로 7걸음 걷는 것을 뜻합니다. 나머지가 같은 두 수는 합동이라 하고 17 ≡ 2 (mod 5)로 쓰는데, 이 표기법은 1801년 카를 프리드리히 가우스가 도입했습니다. 합, 차, 곱은 어느 단계에서든 mod n으로 줄일 수 있어 수가 작게 유지됩니다.
모듈러 산술이 쓰이는 곳
시계와 달력은 mod 12, mod 24, mod 7로 돌아갑니다: 100 mod 7 = 2이므로 수요일에서 100일 뒤는 금요일입니다. 검증 숫자는 입력 오류를 잡아내는 데 이를 사용하며, ISBN-10 번호(mod 11)부터 은행 카드 번호(mod 10), IBAN(mod 97)까지 쓰입니다. 암호는 글자를 mod 26으로 밀고, 아핀 암호를 복호화하려면 mod 26에서의 역원이 필요합니다. 인터넷의 상당 부분을 보호하는 RSA는 메시지 m을 m^e mod n으로 암호화하고 또 다른 거듭제곱으로 복호화합니다: n = 3233일 때 65^17 mod 3233 = 2790이고 2790^413 mod 3233 = 65입니다.
자주 묻는 질문
음수의 a mod n은 어떻게 계산하나요?
수가 0과 n − 1 사이에 들어올 때까지 n의 배수를 더하거나 빼세요. −7 mod 3이라면 −7 + 9 = 2이므로 답은 2입니다. 일부 프로그래밍 언어는 몫을 0 쪽으로 버리기 때문에 −7 % 3에 대해 대신 −1을 돌려주지만, 수학에서 나머지는 결코 음수가 아닙니다.
모듈러 역원이란 무엇인가요?
n을 법으로 하는 a의 역원은 a × x ≡ 1 (mod n)을 만족하는 수 x입니다. 7 × 15 = 105 = 4 × 26 + 1이므로 mod 26에서 7의 역원은 15입니다. 역원은 a와 n에 공통인수가 없을 때만 존재하며, 확장 유클리드 알고리즘으로 구할 수 있습니다. n을 법으로 a로 나눈다는 것은 그 역원을 곱한다는 뜻입니다.
7^2026 같은 거듭제곱을 mod n으로 어떻게 계산하나요?
반복 제곱법을 씁니다: 7을 계속 제곱하면서 매번 mod n으로 줄여 7^1, 7^2, 7^4, 7^8 등을 구한 다음, 2026을 이진법으로 나타낼 때 필요한 것들을 곱합니다. 이렇게 하면 2,025번의 곱셈 대신 10번의 제곱과 7번의 곱셈이면 되고, 수는 결코 n²보다 커지지 않습니다. 7^2026의 일의 자리는 9입니다.
시계에 왜 12 대신 0이 표시되나요?
모듈러 산술에서 나머지는 0부터 n − 1까지이므로, 위치가 12개인 시계에서 정오는 0입니다. 12 ≡ 0 (mod 12)이며, 보통 시계는 수학에서 0이라고 쓰는 자리에 12라고 적을 뿐입니다.
수는 얼마나 클 수 있나요?
a와 b는 최대 30자리이고 음수여도 되며, 법은 10^18까지 가능합니다. 계산기는 브라우저에서 정확한 정수로 계산하므로 RSA 규모의 예제도 정확한 답을 내며, 어떤 데이터도 어디로도 전송되지 않습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동