Primality Testing ใน Cryptography
จำเป็นสำหรับสร้างกุญแจ RSA (ต้องการ p, q เฉพาะ 1024-4096 บิต) และระบบ Public-Key อื่นๆ
ประเภทของ Primality Tests
1. Deterministic Algorithms (แน่นอน)
- ให้คำตอบถูกต้องเสมอ (Prime/Composite)
- AKS (2002): Agrawal-Kayal-Saxena, O(log⁶ n) Polynomial Time → ทฤษฎีสำคัญ แต่ช้าจริง
- Trial Division: หาร 2..√n → ใช้ได้เฉพาะ n เล็ก
2. Probabilistic Algorithms (โอกาสผิดพลาดต่ำ)
- ใช้ในปฏิบัติจริง (RSA, DH, ECC Key Gen)
- กฎ: ถ้า n เป็น Prime → ตอบ Prime เสมอ (No False Negative)
- ถ้า n เป็น Composite → ตอบ Composite ด้วยโอกาส ≥ 1-ε, ตอบ Prime ด้วยโอกาส ≤ ε
- รัน m รอบ → Error ≤ εᵐ
3. Fermat Primality Test
- จาก Fermat's Little Theorem: aⁿ⁻¹ ≡ 1 (mod n)
- เลือก a แล้วตรวจสอบ → ผ่าน = Probably Prime
- ❌ Carmichael Numbers (เช่น 561, 1729, 6601) ผ่านทุก a ที่ gcd(a,n)=1 → False Positive มาก
4. Miller-Rabin Test (มาตรฐานอุตสาหกรรม)
- ขยาย Fermat ด้วย Square Root Test
- ไม่มี Carmichael Problem
- Error ≤ 1/4 ต่อรอบ → 40 รอบ = 2⁻⁸⁰
- Deterministic สำหรับ n < 2⁶⁴ ด้วย Bases เฉพาะ
5. Solovay-Strassen Test
- ใช้ Euler Criterion + Jacobi Symbol
- Error ≤ 1/2 ต่อรอบ (แย่กว่า Miller-Rabin)
- ใช้น้อยกว่าในปัจจุบัน
การใช้งานจริง (RSA Key Generation)
- สุ่ม Odd Number n ขนาดที่ต้องการ (เช่น 2048 บิต)
- Trial Division ด้วย Prime เล็กๆ (Primes < 10000) → กรอง Composite เร็ว
- Miller-Rabin 40 รอบ (Random Bases) → Probably Prime
- (Optional) Lucas Test เพิ่มความมั่นใจ
- ทำซ้ำจนได้ p, q ทั้งคู่
Post-Quantum Note
RSA ต้องการ Primality Testing แต่ PQC (Kyber, Dilithium, SPHINCS+) ใช้ Structured Lattices/Hash-based → ไม่ต้องหา Prime ใหญ่
