Modular Arithmetic
合同算術（モジュラ演算）は整数演算の剰余を取り、結果を[0, n)の範囲に保つ。数論と暗号理論の基礎である。
目的
演算を有限範囲内で閉じさせ、RSAやDiffie-Hellmanなどの暗号技術の基礎を提供する。
メカニズム
法nの下で(a + b) mod nと(a × b) mod nが定義される。モジュラ逆元a^(-1)はa·a^(-1) ≡ 1 (mod n)を満たし、gcd(a,n)=1のとき存在し、拡張ユークリッドの互除法で求められる。フェルマーの小定理により、素数pに対してa^(p-1) ≡ 1 (mod p)が成り立つ。
ユースケース
- RSAの暗号化と復号
- ディフィー・ヘルマン鍵交換
- ハッシュによるシャーディング
- チェックサムの計算
例
- 入力
(7 + 8) mod 5Output015 mod 5 = 0
よくあるエラー
- Negative modulo behaves differently across languages
- Know your language's behavior or normalize with ((a%n)+n)%n