เลขคณิตแบบโมดูลาร์ (Modular Arithmetic)
ระบบเลขคณิตสำหรับจำนวนเต็ม ที่ตัวเลข "วนกลับ" (Wrap around) เมื่อถึงค่าที่กำหนด (Modulus n) พื้นฐานของ Public-Key Cryptography ทุกประเภท
แนวคิดพื้นฐาน
- a ≡ b (mod n) ⟺ n หาร (a - b) ลงตัว
- ชั้นเหมือน (Equivalence Classes): [0], [1], ..., [n-1]
- ชุด Zn = {0, 1, ..., n-1} ด้วยการบวก/คูณ modulo n
คุณสมบัติพื้นฐาน
| คุณสมบัติ | สมการ |
|---|---|
| Reflexive | a ≡ a (mod n) |
| Symmetric | a ≡ b → b ≡ a (mod n) |
| Transitive | a ≡ b, b ≡ c → a ≡ c (mod n) |
| Addition | [(a mod n) + (b mod n)] mod n = (a + b) mod n |
| Subtraction | [(a mod n) - (b mod n)] mod n = (a - b) mod n |
| Multiplication | [(a mod n) × (b mod n)] mod n = (a × b) mod n |
โครงสร้างทางพีชคณิต
- Group (Zn, +): Abelian Group
- Ring (Zn, +, ×): Commutative Ring with Identity
- Field (Zp, +, ×): ถ้า p เป็นเฉพาะ → ทุกสมาชิกยกเว้น 0 มี Multiplicative Inverse
- Multiplicative Group (Zn*, ×): สมาชิกที่ gcd(a,n)=1 ขนาด = φ(n) (Euler's Totient)
การประยุกต์ใน Cryptography
- RSA: โมดูลัส n = p×q, φ(n) = (p-1)(q-1), e·d ≡ 1 (mod φ(n))
- Diffie-Hellman: gab mod p ใน Zp*
- ECC: Elliptic Curve over Finite Field Fp หรือ F2ᵐ
- AES: Arithmetic ใน GF(2⁸) = Polynomials mod x⁸+x⁴+x³+x+1
- Hash Functions: Modular Addition (SHA-2), Modular Multiplication
ทฤษฎีบทสำคัญ
- Fermat's Little Theorem: ap-1 ≡ 1 (mod p), p prime, gcd(a,p)=1
- Euler's Theorem: aφ(n) ≡ 1 (mod n), gcd(a,n)=1
- Chinese Remainder Theorem (CRT): ระบบสมการมอดุลัส → เร่ง RSA Decryption 4x
- Lagrange's Theorem: Order of subgroup divides order of group
การคำนวณที่สำคัญ
- Modular Exponentiation: Square-and-Multiply (Binary Exponentiation) O(log e)
- Modular Inverse: Extended Euclidean Algorithm
- Modular Square Root: Tonelli-Shanks (p ≡ 1 mod 4)
