อัลกอริทึม Miller-Rabin สำหรับทดสอบจำนวนเฉพาะ

Miller-Rabin Primality Test

อัลกอริทึมทดสอบจำนวนเฉพาะแบบ Probabilistic เร็ว กำหนดได้ว่า Composite (ไม่ใช่เฉพาะ) แน่นอน หรือ Probably Prime (อาจเป็นเฉพาะ)

พื้นฐานทฤษฎี

ขยายจาก Fermat's Little Theorem: ถ้า n เป็นเฉพาะ, aⁿ⁻¹ ≡ 1 (mod n) สำหรับทุก a ที่ gcd(a,n)=1

เขียน n-1 = m × 2ᵏ (m คี่) → ตรวจสอบลำดับ:

aᵐ, a²ᵐ, a⁴ᵐ, ..., a²ᵏ⁻¹ᵐ, a²ᵏᵐ = aⁿ⁻¹ (mod n)

ขั้นตอนอัลกอริทึม (Pseudocode)

MillerRabin(n, a):
    // n: จำนวนที่ต้องการทดสอบ, a: base (witness)
    หา m, k: n-1 = m × 2ᵏ (m คี่)
    T = aᵐ mod n
    ถ้า T ≡ ±1 (mod n): return "Probably Prime"
    สำหรับ i = 1 ถึง k-1:
        T = T² mod n
        ถ้า T ≡ 1: return "Composite"  // Non-trivial square root of 1
        ถ้า T ≡ -1: return "Probably Prime"
    return "Composite"

ความน่าจะเป็นความผิดพลาด

• 1 รอบ: ≤ 1/4 (25%) โอกาสที่ Composite ผ่าน (Strong Liar)
• m รอบ (Base ต่างกัน): ≤ (1/4)ᵐ
• เช่น 40 รอบ → (1/4)⁴⁰ ≈ 2⁻⁸⁰ (ปลอดภัยทางปฏิบัติ)

ตัวอย่าง: ทดสอบ n=341, base a=2

1. 341-1 = 340 = 85 × 2² → m=85, k=2
2. T = 2⁸⁵ mod 341 = 8
3. T ≠ ±1 → Loop
4. i=1: T = 8² mod 341 = 64 mod 341 = 64
5. 64 ≠ ±1 → Loop จบ (k-1=1)
6. Return "Composite" → 341 = 11 × 31 ✓

Deterministic Variants

• สำหรับ n < 2⁶⁴: ทดสอบ Base = {2, 3, 5, 7, 11, 13, 17} → Deterministic 100%
• ใช้ใน OpenSSL, GnuTLS, Java, .NET, Go, Python (secrets, cryptography)

ข้อดี

• เร็วมาก (O(k log³ n) ด้วย Fast Multiplication)
• ไม่มี Carmichael Number ปัญหา (ต่างจาก Fermat Test)
• มาตรฐานอุตสาหกรรมสำหรับ RSA Key Generation