ขั้นตอนการทดสอบจำนวนเฉพาะแบบ Miller-Rabin

ขั้นตอน Miller-Rabin Primality Testing

รวม Fermat Test และ Square Root Test เพื่อหา Strong Pseudoprime

การเตรียม (Initialization)

1. เลือก Base a (1 < a < n-1)
2. เขียน n-1 = m × 2ᵏ (m คี่)
3. คำนวณ T = aᵐ mod n

การตัดสินใจเริ่มต้น

• ถ้า T ≡ +1 หรือ -1 (mod n) → Probably Prime (หยุด)
• เหตุผล: T=±1 → T²=1 → ผ่าน Fermat และ Square Root Test ทุกขั้นต่อไป
• ถ้า T ไม่ใช่ ±1 → ดำเนินต่อ (Inconclusive)

ขั้นตอนที่ 1 ถึง k-1 (Iterative Steps)

สำหรับ i = 1, 2, ..., k-1:

1. T = T² mod n (Square)
2. ถ้า T ≡ +1: → Composite (หยุด)
   เหตุผล: T กลายเป็น 1 แต่ขั้นก่อนหน้าไม่ใช่ ±1 → Non-trivial Square Root of 1 → n Composite
3. ถ้า T ≡ -1: → Probably Prime (หยุด)
   เหตุผล: T=-1 → ขั้นต่อไป T=1 → ผ่าน Fermat และ Square Root Test
4. อื่นๆ: → ดำเนินขั้นต่อไป (Inconclusive)

ขั้นตอนที่ k (Final Step)

• ไม่จำเป็นต้องคำนวณ (เพราะ T² = aⁿ⁻¹ mod n)
• ถ้าถึงขั้นนี้ยังไม่ตัดสินใจ → Composite
• เหตุผล: Fermat Test อาจผ่าน (T=1) แต่ Square Root Test ล้มเหลว (ขั้นก่อนไม่ใช่ ±1)

สรุปโฟลูว์

ตัวอย่าง n=341, a=2

1. 340 = 85 × 2² (m=85, k=2)
2. T₀ = 2⁸⁵ mod 341 = 8 (≠ ±1)
3. i=1: T₁ = 8² mod 341 = 64 (≠ ±1)
4. จบ Loop (k-1=1) → Composite