모듈러 산술
17 = 5 (mod 12)
17과 5는 12로 나눌 때 같은 나머지를 갖는다
모듈러 산술은 원 위의 산술이다. 두 수가 n의 배수만큼 차이나면 n으로 합동이다. 시계는 mod 12 산술을 한다: 5시에서 10시간 후는 15시가 아니라 3시이다. 이 간단한 아이디어가 모든 현대 암호학, 해시 함수, 오류 정정 코드, 그리고 정수론의 상당 부분의 기초가 된다.
mod 12 시계: 덧셈이 순환한다
페르마의 소정리 검증
a^(p−1) ≡ 1 (mod p) when p is prime, p∤a
Example p=5, a=2: 2⁴ = 16 = 3×5 + 1 ≡ 1 (mod 5) ✓
Example p=7, a=3: 3⁶ = 729 = 104×7 + 1 ≡ 1 (mod 7) ✓
Used in RSA encryption to prove decryption recovers the original message.
ℤ/5ℤ (정수 mod 5)의 덧셈표
모든 행과 열에 {0,1,2,3,4}가 정확히 한 번씩 나타난다. 다섯 원소는 mod 5 덧셈 아래 닫힌 군을 형성한다. 빨간색: 순환하는 합(≥5).
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
모듈러 산술의 주요 사실
모듈러 산술은 합동을 정의한다: n이 a-b를 나누면 a는 b와 mod n으로 합동이다. 가우스가 1801년에 체계화했다. 모든 현대 공개키 암호학의 기반이 된다: RSA 암호화는 페르마의 소정리에 의존하며, 이는 p가 a를 나누지 않는 소수일 때 a^(p-1)이 1과 mod p로 합동이라는 것이다. 해시 함수는 큰 입력을 고정 크기 출력으로 매핑하는 데 모듈러 연산을 사용한다. mod n의 정수는 완전한 환을 형성하며, n이 소수일 때 유한체를 형성한다.
사용 분야
수학
✓
물리학
–
공학
–
생물학
–
컴퓨터 과학
✓
통계학
–
금융
–
예술
–
건축
–
음악
✓
암호학
✓
천문학
–
화학
–
철학
–
지리학
–
생태학
–
지식을 테스트해 보시겠습니까?
질문
윌슨의 정리란 무엇인가요?
탭 · 스페이스
1 / 10
플레이할 준비가 되셨나요?
Pi
Memorize pi, e, and 40+ mathematical constants using the numpad path method
지금 플레이 - 무료계정 불필요. 모든 기기에서 작동.
Topic roundups
