Miller Rabin เป็นวิธีที่รวดเร็วในการทดสอบความเป็นอันดับหนึ่งของตัวเลขจำนวนมาก อัลกอริธึมนี้เรียกว่าการทดสอบเบื้องต้นของ Rabin-miller และอัลกอริธึมนี้จะตัดสินว่าจำนวนเฉพาะซึ่งเหมือนกับการทดสอบอื่นๆ รวมถึง Fermat primality Test และ Solovay- Strassen primality test
การทดสอบนี้อิงจากความเท่าเทียมกันหรือกลุ่มของความเท่าเทียมกันที่เป็นจริงสำหรับค่าเฉพาะ ดังนั้นตรวจสอบว่ามีค่าเท่ากับจำนวนนั้นหรือไม่ว่าจำเป็นต้องทดสอบหาความเป็นอันดับหนึ่ง
อัลกอริธึมนี้เป็นอัลกอริธึมการทดสอบพื้นฐานที่รู้จักและมีประโยชน์มากที่สุด และสามารถใช้ในไลบรารีซอฟต์แวร์ต่างๆ ที่อิงตามการเข้ารหัส RSA และอินสแตนซ์ที่ดีที่สุดคือ OpenSSL
มิลเลอร์ ราบินตรวจสอบว่าตัวเลขนั้นประกอบกัน นี่จึงเรียกว่าการทดสอบคอมโพสิตมากกว่าการทดสอบเบื้องต้น การทดสอบมิลเลอร์ Rabin ระบุส่วนผสมทั้งหมด สำหรับแต่ละหมายเลขประกอบ n อาจมีอย่างน้อย 3/4 (มิลเลอร์ ราบิน) ของตัวเลข a เป็นพยานถึงการรวมกันของ n
Miller Rabin เป็นส่วนขยายที่เชื่อมโยงอย่างง่ายของทฤษฎีบทเล็กๆ ของ Fermats ที่ช่วยให้เราสามารถทดสอบความเป็นปฐมภูมิโดยมีความน่าจะเป็นมากกว่าทฤษฎีบทเล็กๆ ของ Fermats
อัลกอริทึม :Pseudocode สำหรับการทดสอบ Miller-Rabin -
Miller-Rabin-Test (n, a) // n is the number; a is the base
{
Find m and k such that n − 1 = m x 2k
T ← am mod n
If (T = ±1)return "a prime"
for (i ← 1 to k − 1) // k – 1 is the maximum number of steps
{
T ← T2 mod n
if (T = ±1) return "a composite"
if (T = −1) return "a prime"
}
return "a composite"
} มีอดีตฉัน เป็นข้อพิสูจน์ว่าทุกครั้งที่ตัวเลขผ่านการทดสอบ Miller-Rabin ความน่าจะเป็นที่ไม่ใช่จำนวนเฉพาะคือ ¼ หากตัวเลขผ่าน m การทดสอบ (โดยมีค่า m ต่างกัน) ความน่าจะเป็นที่ไม่ใช่จำนวนเฉพาะคือ (1/4) m .
ตัวอย่าง :ใช้ Miller-Rabin Algorithm โดยใช้ฐาน 2 เพื่อทดสอบว่าตัวเลข 341 นั้นประกอบกันหรือไม่
วิธีแก้ปัญหา :โดยใช้ Miller-Rabin Algorithm เราสามารถทดสอบเลข 341 ได้ดังนี้:
ขั้นที่ 1:341 − 1 =2 2 x 85 ดังนั้น p =341, k =2 และ q =85
ขั้นที่ 2:x =2 (ระบุ)
ขั้นที่ 3:S =x q mod p
=2 85 mod 341 =(2 10 ) x 2 5 mod 341 8
=2 10 mod 341 x 2 13 mod 341
=1 x 8192 mod 341 =8192 mod 341
=8
ขั้นที่ 4:เมื่อ 8 ≠ 1 เราย้ายไปยังขั้นตอนถัดไป
ขั้นที่ 5:สำหรับ j =1, S =x 2q mod p
=2 170 mod 341 =(2 20 ) 8 x 2 10 mod 341
=2 20 mod 341 x 2 8 mod 341 x 2 10 mod 341
=1 x 256 x 1 =256
ตอนนี้ =256 ≠ 1
และผลลัพธ์ยังสรุปไม่ได้
ดังนั้น 341 ไม่ใช่จำนวนเชิงประกอบ
ข้อดี
-
อัลกอริธึมนี้สามารถใช้ในการทดสอบตัวเลขสูงสำหรับความเป็นปฐมวัยได้
-
เนื่องจากมีความได้เปรียบในด้านความเร็วเมื่อเทียบกับการทดสอบในขั้นต้น การทดสอบ Miller Rabin จะเป็นการทดสอบทางเลือกสำหรับแอพพลิเคชั่นการเข้ารหัสหลายตัว
-
เมื่อเปรียบเทียบกับการทดสอบออยเลอร์และโซโลเวย์-สตราสเซน มิลเลอร์ ราบินมีพลวัตมากกว่าและสิ่งสำคัญคือความน่าจะเป็นของความล้มเหลวจะลดลง
-
จากการทดสอบ Fermat มีผู้โกหกมากเกินไปสำหรับ Carmichaelnumbers n ทั้งหมด ความน่าจะเป็นของข้อผิดพลาดนั้นใกล้จะถึง 1 ข้อเสียนี้สามารถป้องกันได้ในMiller Rabin
