ทฤษฎีบทเล็กของเฟอร์มา (Fermat's Little Theorem) ในความปลอดภัยข้อมูล

ทฤษฎีบทเล็กของเฟอร์มา (Fermat's Little Theorem)

ทฤษฎีบทพื้นฐานในทฤษฎีจำนวน (Number Theory) ใช้ใน Primality Testing และ Public-Key Cryptography (RSA)

ข้อความทฤษฎีบท

ถ้า p เป็นจำนวนเฉพาะ (Prime) และ a เป็นจำนวนเต็มบวก ที่ ไม่หาร p ลงตัว (gcd(a,p)=1) แล้ว:

a^p-1 ≡ 1 (mod p)

รูปแบบอื่น: ถ้า p เป็นเฉพาะ และ a เป็นจำนวนเต็มใดๆ แล้ว:

a^p ≡ a (mod p)

การพิสูจน์ (Proof Sketch)

1. พิจารณาชุด Z_p = {1, 2, ..., p-1}
2. คูณทุกสมาชิกด้วย a (mod p): {a·1, a·2, ..., a·(p-1)} mod p
3. เพราะ gcd(a,p)=1 ชุดใหม่นี้เป็นการเรียงสับเปลี่ยน (Permutation) ของชุดเดิม
4. คูณทุกตัวพร้อมกัน: a·2a·...·(p-1)a ≡ 1·2·...·(p-1) (mod p)
5. a^p-1 · (p-1)! ≡ (p-1)! (mod p)
6. ตัด (p-1)! ออกได้ (เพราะ gcd((p-1)!, p) = 1) → a^p-1 ≡ 1 (mod p)

ตัวอย่างตัวเลข

• 3¹⁰ mod 11 = 1 (เพราะ 11 เป็นเฉพาะ, gcd(3,11)=1)
• 3²⁰¹ = (3¹⁰)²⁰ × 3 ≡ 1²⁰ × 3 ≡ 3 (mod 11)
• 6¹⁰ mod 11 = 1
• 3¹² mod 11 = (3¹¹ × 3) mod 11 = (3 × 3) mod 11 = 9

การประยุกต์ใน Cryptography

• Primality Testing: Fermat Test (แต่มี Carmichael Numbers ให้ False Positive)
• RSA Key Generation: หา Modular Inverse: d ≡ e⁻¹ mod φ(n) ใช้ Euler's Theorem (การขยายของ Fermat)
• Modular Exponentiation: ลดเลขยกกำลังใหญ่ modulo p
• Diffie-Hellman: g^ab mod p

ข้อจำกัด

• เงื่อนไข: p ต้องเป็นเฉพาะจริง (Carmichael numbers ผ่าน Fermat test แต่ไม่ใช่เฉพาะ)
• ต้องใช้ Miller-Rabin หรือ AKS สำหรับ Primality Testing จริง