合同算術
17 = 5 (mod 12)
17 と 5 は 12 で割った余りが同じ
合同算術は円の上の算術である。2 つの数が 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ℤ（5 を法とする整数）の加法表
各行と各列には {0,1,2,3,4} がちょうど一度ずつ現れる。5 個の元は 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 |
合同算術の要点
合同算術は合同関係を定義する。a と b が mod n で合同であるとは、n が a-b を割り切ることである。ガウスは 1801 年にこれを体系化した。現代の公開鍵暗号の基盤であり、RSA 暗号はフェルマーの小定理、すなわち a を割らない素数 p に対して 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
