การทดสอบ Permality ของ Miller-Rabin รวมการทดสอบ Fermat และการทดสอบรากของ Fermat ในวิธีคลาสสิกเพื่อค้นหา pseudoprime ที่แข็งแกร่ง ในการทดสอบนี้ สามารถเขียน n – 1 เป็นผลคูณของจำนวนคี่ m และยกกำลัง 2:
$$\mathrm{n-1=m\, x\, 2^{k}}$$
การทดสอบแฟร์มาต์ในเบส a สามารถเขียนได้ดังนี้:
$$\mathrm{a^{n-1}\, =\, a^{m\, x\, 2k}=\left [ a^{m} \right ]^{2k}=\left [ a^ {m} \right ]\frac{2^{2}\cdot \cdot \cdot 2}{K\, times}}$$
กล่าวอีกนัยหนึ่ง แทนที่จะคำนวณ a n-1 (mod n) ในขั้นตอนเดียวสามารถทำได้ใน k+1steps ข้อดีของการใช้ k + 1 คือแต่ละขั้นตอนในขั้นตอนรากที่สองสามารถนำไปใช้ได้ หากการทดสอบรากที่สองล้มเหลว ก็สามารถหยุดและประกาศ n เป็นจำนวนประกอบได้
ในแต่ละขั้นตอน สามารถระบุให้ผ่านการทดสอบ Fermat และการทดสอบรากที่สองเป็นไปตามกลุ่มของขั้นตอนที่อยู่ติดกันทั้งหมด หากสามารถเข้าถึงได้ (หากผลลัพธ์คือ 1)
การเริ่มต้น
-
สามารถเลือกฐาน a และคำนวณได้ $\mathrm{T\, =\, a^{m}}$ ซึ่ง $\mathrm{m\, =\, \frac{n-1}{2^{k }}}$
-
ถ้า T เป็น + 1 หรือ -1 ประกาศว่า n เป็น pseudoprime ที่แข็งแกร่งและหยุด เพราะถ้า T เป็น+-1, T จะกลายเป็น 1 ในขั้นตอนต่อไปและยังคงเป็น 1 จนกว่าจะผ่าน Fermattest นอกจากนี้ T ได้ผ่านการทดสอบรากที่สองเนื่องจาก T สามารถเป็น 1 ได้ในขั้นตอนถัดไป และรากที่สองของ 1 (ในขั้นตอนถัดไป) คือ +-1
-
ถ้า T เป็นอย่างอื่น จะไม่แน่ใจว่า n เป็นจำนวนเฉพาะหรือคอมโพสิต ดังนั้นจึงไม่สามารถไปยังขั้นตอนถัดไปได้
ขั้นที่ 1 :พวกเรากำลังสอง T
-
หากผลลัพธ์เป็น +1 เป็นที่ทราบแน่ชัดว่าการทดสอบแฟร์มาต์จะผ่านเพราะ T ยังคงเป็น 1 สำหรับการทดสอบที่ประสบความสำเร็จ ไม่ผ่านการทดสอบรากที่สอง เนื่องจาก T เป็น 1 ในขั้นตอนนี้และเป็นอย่างอื่นที่ไม่ใช่ +-1 ในขั้นตอนก่อนหน้า จึงประกาศ n เป็นส่วนประกอบและหยุดได้
-
ถ้าผลลัพธ์เป็น -1 ก็จะเข้าใจได้ว่า n จะผ่านการทดสอบแฟร์มาต์ในที่สุด นอกจากนี้ยังสามารถเข้าใจได้ว่ามันจะผ่านการทดสอบรากที่สองเนื่องจาก T คือ -1 ในขั้นตอนนี้และกลายเป็น 1 ในขั้นตอนถัดไป สามารถประกาศ n เป็น strongpseudoprime และหยุดได้
-
ถ้า T เป็นอย่างอื่น ไม่แน่ใจว่าจะทำได้หรือไม่มีเฉพาะ ดำเนินการในขั้นตอนต่อไป
ขั้นตอนที่ 2 สู่ขั้นตอน K – 1:
ขั้นตอนนี้และขั้นตอนต่อไปนี้ทั้งหมดดำเนินต่อไปจนถึงขั้นตอนที่ 2 และจนถึงขั้นตอน K -1 เท่ากับขั้นตอนที่ 1
ขั้นตอน K:
ขั้นตอนนี้ไม่จำเป็น หากสามารถมาถึงขั้นตอนนี้ได้และยังไม่ได้ตัดสินใจ ขั้นตอนนี้จะไม่ช่วยให้เราดำเนินการได้ หากผลลัพธ์ของขั้นตอนนี้เท่ากับ 1 แสดงว่าการทดสอบ Fermat เป็นที่ยอมรับ แต่เนื่องจากผลลัพธ์ของขั้นตอนก่อนหน้าไม่ใช่ +-1 จึงไม่ยอมรับการทดสอบรากที่สอง หลังจากขั้นตอนที่ k -1 ถ้ายังไม่หยุด สามารถประกาศได้ว่า n เป็นส่วนประกอบ จำเป็นต้องทำการทดสอบ Miller-Rabin ตั้งแต่ขั้นตอนที่ 0 ถึงขั้นตอน K-1
