การทดสอบความเป็นจำนวนเฉพาะของมิลเลอร์-ราบินหรือการทดสอบความเป็นจำนวนเฉพาะของราบิน-มิลเลอร์เป็นการทดสอบความเป็นจำนวนเฉพาะ เชิงความน่าจะเป็น : อัลกอริทึม ที่ใช้ตรวจสอบ ว่า จำนวนที่กำหนดมีแนวโน้มที่จะเป็นจำนวนเฉพาะ หรือ ไม่ คล้ายกับการทดสอบความเป็นจำนวนเฉพาะของแฟร์มาต์และการทดสอบความเป็นจำนวนเฉพาะของโซโลเวย์-สตราสเซน

วิธีการนี้มีความสำคัญทางประวัติศาสตร์ในการค้นหา การทดสอบความเป็นจำนวนเฉพาะแบบกำหนดได้ ในเวลาพหุนามส่วนวิธีการแบบความน่าจะเป็นยังคงถูกนำมาใช้กันอย่างแพร่หลายในทางปฏิบัติ เนื่องจากเป็นหนึ่งในวิธีการทดสอบที่ง่ายและเร็วที่สุดเท่าที่รู้จัก

แกรี่ แอล. มิลเลอร์ค้นพบการทดสอบนี้ในปี 1976 เวอร์ชันของการทดสอบของมิลเลอร์เป็นแบบกำหนดได้แต่ความถูกต้องขึ้นอยู่กับสมมติฐานรีมันน์แบบขยาย ที่ยังไม่ได้รับ การ พิสูจน์ ^{[ 1 ]}ไมเคิล โอ. ราบินปรับเปลี่ยนเพื่อให้ได้อัลกอริทึมความน่าจะเป็น แบบไม่มีเงื่อนไข ในปี 1980 ^{[ 2 ] [ a ]}

เช่นเดียวกับการทดสอบของแฟร์มาต์และโซโลเวย์-สตรัสเซน การทดสอบความเป็นจำนวนเฉพาะของมิลเลอร์-ราบินจะตรวจสอบว่าคุณสมบัติเฉพาะอย่างหนึ่ง ซึ่งเป็นที่ทราบกันดีว่าใช้ได้กับจำนวนเฉพาะนั้น ใช้ได้กับจำนวนที่กำลังทดสอบหรือไม่

คุณสมบัติดังกล่าวมีดังนี้ สำหรับจำนวนเต็มคี่ที่กำหนดให้ ให้เขียน ในรูปโดยที่เป็นจำนวนเต็มบวก และเป็นจำนวนเต็มบวกคี่ ให้พิจารณาจำนวนเต็ม  เรียกว่าฐานซึ่งเป็นจำนวนเฉพาะสัมพัทธ์กับแล้วกล่าวได้ว่า เป็น จำนวนเฉพาะที่น่าจะเป็น ไปได้มาก (strong probable prime) ของฐานถ้าความสัมพันธ์สมภาคข้อ ใดข้อหนึ่งต่อไปนี้ เป็นจริง: ${\displaystyle n>2}$${\displaystyle n-1}$${\displaystyle 2^{s}d}$${\displaystyle s}$${\displaystyle d}$${\displaystyle a}$${\displaystyle n}$${\displaystyle n}$

• ${\displaystyle a^{d}\equiv 1\!\!\!{\pmod {n}}}$, หรือ
• ${\displaystyle a^{2^{r}d}\equiv -1\!\!\!{\pmod {n}}}$สำหรับบางคน${\displaystyle 0\leq r<s}$

วิธีนี้ทำให้ง่ายขึ้นโดยการตรวจสอบค่า ก่อนแล้วจึงตรวจสอบค่า ต่อไปสำหรับแต่ละค่าค่าของนิพจน์สามารถคำนวณได้โดยใช้ค่าที่ได้จากค่า ก่อนหน้าโดยการยกกำลังสองภายใต้ค่าสัมบูรณ์ของ ${\displaystyle a^{d}\equiv 1{\pmod {n}}}$${\displaystyle a^{2^{r}d}\equiv n-1{\pmod {n}}}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$${\displaystyle n}$

แนวคิดเบื้องหลังการทดสอบนี้คือ เมื่อจำนวนเฉพาะนั้นเป็นจำนวนคี่ มันจะผ่านการทดสอบเนื่องจากข้อเท็จจริงสองประการ: ${\displaystyle n}$

• โดยทฤษฎีบทเล็กของแฟร์มาต์ ( คุณสมบัตินี้เพียงอย่างเดียวก็กำหนดแนวคิดที่อ่อนกว่าของจำนวนเฉพาะที่เป็นไปได้บนฐานซึ่งเป็นพื้นฐานของการทดสอบของแฟร์มาต์)${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$${\displaystyle a}$
• รากที่สองของ1 มอดูโลมีเพียง 1 และ −1 เท่านั้น${\displaystyle n}$

ดังนั้น โดยหลักการแย้งถ้าไม่ใช่จำนวนเฉพาะที่น่าจะเป็นไปได้มากสำหรับฐานแล้วจะเป็นจำนวนประกอบอย่างแน่นอน และเรียกว่าพยานยืนยันความเป็นจำนวนประกอบของ ${\displaystyle n}$${\displaystyle a}$${\displaystyle n}$${\displaystyle a}$${\displaystyle n}$

อย่างไรก็ตาม คุณสมบัตินี้ไม่ใช่ลักษณะเฉพาะที่แน่นอนของจำนวนเฉพาะ หากเป็นจำนวนประกอบ มันอาจยังคงเป็นจำนวนเฉพาะที่น่าจะเป็นไปได้มาก (strong probable prime) ที่มีฐานเป็นซึ่งในกรณีนี้เรียกว่าจำนวนเฉพาะเทียมที่แข็งแกร่ง (strong pseudoprime)และเป็นจำนวนโกหกที่แข็งแกร่ง (strong liar ) ${\displaystyle n}$${\displaystyle a}$${\displaystyle a}$

ไม่มีจำนวนประกอบใดที่เป็นจำนวนเฉพาะเทียมที่แข็งแกร่งสำหรับทุกฐานพร้อมกัน (ตรงกันข้ามกับการทดสอบความเป็นจำนวนเฉพาะของแฟร์มาต์ ซึ่งมีจำนวนเฉพาะเทียมของแฟร์มาต์สำหรับทุกฐานอยู่จริง นั่นคือจำนวนคาร์ไมเคิล ) อย่างไรก็ตาม ยังไม่มีวิธีง่ายๆ ในการหาพยานหลักฐาน วิธีแก้ปัญหาแบบง่ายๆ คือการลองใช้ฐานที่เป็นไปได้ทั้งหมด ซึ่งจะได้อัลกอริทึมแบบกำหนดที่ไม่ประสิทธิภาพ การทดสอบของมิลเลอร์เป็นวิธีการที่มีประสิทธิภาพมากกว่า (ดูหัวข้อการทดสอบของมิลเลอร์ด้านล่าง )

อีกวิธีหนึ่งคือการเลือกฐานแบบสุ่ม วิธีนี้จะให้การทดสอบความน่าจะ เป็นที่รวดเร็ว เมื่อnเป็นจำนวนประกอบ ฐานส่วนใหญ่จะเป็นพยาน ดังนั้นการทดสอบจะตรวจพบ ว่า nเป็นจำนวนประกอบด้วยความน่าจะเป็นที่ค่อนข้างสูง (ดูส่วนความแม่นยำด้านล่าง ) เราสามารถลดความน่าจะเป็นของผลบวกเท็จให้เหลืออัตราที่น้อยมากได้อย่างรวดเร็ว โดยการรวมผลลัพธ์ของฐานที่เลือกอย่างอิสระจำนวนมากเท่าที่จำเป็นเพื่อให้ได้อัตราดังกล่าว นี่คือการทดสอบของมิลเลอร์-ราบิน ดูเหมือนว่าจะมีผลตอบแทนที่ลดลงเมื่อลองใช้ฐานจำนวนมาก เพราะถ้าnเป็นจำนวนเฉพาะเทียมกับฐานบางฐาน ก็ดูเหมือนว่าจะมีโอกาสมากขึ้นที่จะเป็นจำนวนเฉพาะเทียมกับฐานอื่น^{[ 4 ] : §8}

โปรดสังเกตว่าa ^d ≡ 1 (mod n )เป็นจริงโดยปริยายสำหรับa ≡ 1 (mod n )เนื่องจากความสัมพันธ์สมมูลเข้ากันได้กับการยกกำลังและa ^d = a ^{2 0 d} ≡ −1 (mod n )เป็นจริงโดยปริยายสำหรับa ≡ −1 (mod n )เนื่องจากdเป็นจำนวนคี่ ด้วยเหตุผลเดียวกัน นั่นคือเหตุผลที่โดยทั่วไปแล้วค่าa แบบสุ่ม จะถูกเลือกในช่วง1 < a < n − 1

สำหรับการทดสอบn ที่มีขนาดใหญ่มาก การเลือกฐานแบบสุ่มเป็นสิ่งจำเป็น เนื่องจากเราไม่ทราบการกระจายของพยานและผู้โกหกตัวฉกาจในกลุ่มตัวเลข 2, 3, ..., n − 2 ^{[ b ]}

อย่างไรก็ตาม ชุดฐานขนาดเล็กที่เลือกไว้ล่วงหน้าเพียงไม่กี่ชุดจะรับประกันการระบุองค์ประกอบทั้งหมดได้จนถึงค่าสูงสุดที่คำนวณไว้ล่วงหน้า โดยทั่วไปแล้วค่าสูงสุดนี้จะค่อนข้างมากเมื่อเทียบกับฐาน ซึ่งทำให้การทดสอบแบบกำหนดได้รวดเร็วมากสำหรับค่าn ที่มีขนาดเล็กพอ (ดูหัวข้อการทดสอบกับชุดฐานขนาดเล็กด้านล่าง )

นี่คือบทพิสูจน์ว่า ถ้าnเป็นจำนวนเฉพาะ รากที่สองของ 1 มอดูล nจะมีเพียง 1 และ −1 เท่านั้น

นี่คือบทพิสูจน์ว่า ถ้าnเป็นจำนวนเฉพาะคี่ แล้ว n จะเป็นจำนวนเฉพาะที่มีความน่าจะเป็นสูงในฐาน a

สมมติว่าเราต้องการตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่ เราเขียนเพื่อให้ได้เราสุ่มเลือกจำนวนที่ ทำให้${\displaystyle n=221}$${\displaystyle n-1{\text{ as }}2^{2}\times 55}$${\displaystyle s=2{\text{ and }}d=55}$${\displaystyle a}$${\displaystyle 2\leq a\leq n-2}$

พูด: ${\displaystyle a=174}$

${\displaystyle {\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &174^{{2^{0}}55}{\text{ mod }}221\equiv 174^{55}\equiv 47{\text{. Since }}47\neq 1{\text{ and }}47\neq n-1{\text{, we continue.}}\\&174^{{2^{1}}55}{\text{ mod }}221\equiv 174^{110}\equiv 220=n-1\end{aligned}}}$

เนื่องจาก221 เป็นจำนวนเฉพาะ หรือไม่ก็ 174 เป็นตัวโกหกที่แข็งแกร่งสำหรับ 221 เราจึงลองสุ่มอีกครั้ง โดยครั้งนี้เลือก: ${\displaystyle 220\equiv -1{\text{ mod }}n}$${\displaystyle a}$${\displaystyle a=137}$

${\displaystyle {\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &137^{{2^{0}}55}{\text{ mod }}221\equiv 137^{55}\equiv 188{\text{. Since }}188\neq 1{\text{ and }}188\neq n-1{\text{, we continue.}}\\&137^{{2^{1}}55}{\text{ mod }}221\equiv 137^{110}\equiv 205\neq n-1\end{aligned}}}$

ดังนั้น 137 จึงเป็นพยานยืนยันถึงความเป็นจำนวนประกอบของ 221 และ 174 นั้นเป็นตัวโกหกที่ร้ายกาจมาก โปรดสังเกตว่าสิ่งนี้ไม่ได้บอกอะไรเราเกี่ยวกับตัวประกอบของ 221 (ซึ่งคือ 13 และ 17) อย่างไรก็ตาม ตัวอย่างของ 341 ในส่วนถัดไปจะแสดงให้เห็นว่าการคำนวณเหล่านี้บางครั้งอาจให้ผลลัพธ์เป็นตัวประกอบของnได้

สำหรับคำแนะนำเชิงปฏิบัติในการเลือกค่าของaโปรดดูที่การทดสอบกับชุดฐานขนาดเล็ก

อัลกอริทึมสามารถเขียนเป็นรหัสเทียมได้ดังนี้ พารามิเตอร์kกำหนดความแม่นยำของการทดสอบ ยิ่งจำนวนรอบมากเท่าไร ผลลัพธ์ก็จะยิ่งแม่นยำมากขึ้นเท่านั้น^{[ 6 ]}

อินพุต #1 : n > 2 จำนวนเต็มคี่ที่จะทดสอบว่าเป็นจำนวนเฉพาะหรือไม่ อินพุต #2 : kจำนวนรอบการทดสอบที่จะดำเนินการ เอาต์พุต : “ composite ” ถ้าพบว่าn เป็นจำนวนประกอบ “ probably prime ” ถ้าไม่ใช่ 

ให้s > 0 และd เป็นจำนวนคี่ > 0 โดยที่n − 1 = 2sd # โดยการแยกตัวประกอบกำลังของ 2 ออกจากn − 1 ทำซ้ำk ครั้ง : a ← random(2, n − 2) # nเป็นจำนวนเฉพาะที่น่าจะเป็นไปได้เสมอในฐาน 1 และn − 1 x ← ad mod n ทำซ้ำ s ครั้ง : y ← x² mod n ถ้า y = 1 และx ≠ 1 และx ≠ n − 1แล้ว# รากที่สองที่ไม่ใช่จำนวนศูนย์ของ 1 มอดู ลัส nคืนค่า“จำนวนประกอบ ” x ← y ถ้าy ≠ 1 แล้วคืนค่า “ จำนวนประกอบ ” คืนค่า “ น่าจะเป็นจำนวนเฉพาะ ” 

การใช้การยกกำลังสองซ้ำๆทำให้เวลาในการทำงานของอัลกอริทึมนี้คือO ( k n ³ )สำหรับ จำนวน nหลัก โดยที่kคือจำนวนรอบที่ดำเนินการ ดังนั้นนี่จึงเป็นอัลกอริทึมที่มีประสิทธิภาพและใช้เวลาแบบพหุนาม การ คูณ แบบ FFTเช่นอัลกอริทึม Schönhage–StrassenสามารถลดเวลาในการทำงานลงเหลือO( k n ² log n log log n ) = Õ ( k n ² )

ข้อผิดพลาดของการทดสอบความเป็นจำนวนเฉพาะวัดได้จากความน่าจะเป็นที่จำนวนประกอบจะถูกประกาศว่าเป็นจำนวนเฉพาะ ยิ่งลองใช้ฐานa มากเท่าไร ความแม่นยำของการทดสอบก็จะยิ่งดีขึ้นเท่านั้น สามารถแสดงได้ว่าถ้าnเป็นจำนวนประกอบแล้ว อย่างมากที่สุด⁠1/4ฐานaเป็นตัวโกหกที่แข็งแกร่งสำหรับn [ ^{2 ] [ 7 ] [ 8 ]}ผลที่ตามมาคือ ถ้าnเป็นจำนวนประกอบการรันการทดสอบ Miller–Rabin k ^รอบ จะประกาศว่า n น่าจะ เป็นจำนวนเฉพาะด้วยความน่าจะเป็นไม่เกิน4 ^{− k}

นี่เป็นการปรับปรุงที่ดีกว่าการทดสอบ Solovay–Strassenซึ่งมีขอบเขตข้อผิดพลาดกรณีเลวร้ายที่สุดคือ 2 ^{− k}ยิ่งไปกว่านั้น การทดสอบ Miller–Rabin นั้นแข็งแกร่งกว่าการทดสอบ Solovay–Strassen อย่างเคร่งครัดในแง่ที่ว่าสำหรับจำนวนประกอบn ทุก ตัว เซตของผู้โกหกที่แข็งแกร่งสำหรับnเป็นเซตย่อยของเซตของผู้โกหกแบบออยเลอร์สำหรับnและสำหรับn จำนวนมาก เซตย่อยนั้นเป็นเซตย่อยที่แท้จริง

นอกจากนี้ สำหรับค่าn ที่มีขนาดใหญ่ ความน่าจะเป็นที่จำนวนประกอบจะถูกประกาศว่าเป็นจำนวนเฉพาะมักจะน้อยกว่า 4 ^{− k} อย่างมีนัยสำคัญ ตัวอย่างเช่น สำหรับจำนวนn ส่วนใหญ่ ความน่าจะเป็นนี้ถูกจำกัดด้วย 8 ^{− k}สัดส่วนของจำนวนnที่ทำให้ขอบเขตบนนี้ไม่ถูกต้องจะหายไปเมื่อเราพิจารณาค่าnที่ มากขึ้น ^{[ 9 ]}ดังนั้น กรณี เฉลี่ย จึง มีความแม่นยำดีกว่า 4 ^{− k} มาก ซึ่งเป็นข้อเท็จจริงที่สามารถนำมาใช้ประโยชน์ในการสร้างจำนวนเฉพาะที่น่าจะเป็นไปได้ (ดูด้านล่าง ) อย่างไรก็ตาม ไม่ควรพึ่งพาขอบเขตข้อผิดพลาดที่ได้รับการปรับปรุงดังกล่าวในการตรวจสอบจำนวนเฉพาะที่มีการกระจายความน่าจะเป็นที่ไม่ได้รับการควบคุม เนื่องจาก ผู้โจมตี ทางด้านการเข้ารหัสอาจส่งจำนวนเฉพาะเทียมที่เลือกอย่างระมัดระวังเพื่อเอาชนะการทดสอบความเป็นจำนวนเฉพาะ^{[ c ]} ในบริบทดังกล่าวสามารถพึ่งพาได้ เฉพาะขอบเขตข้อผิดพลาด กรณีที่เลวร้ายที่สุดของ 4 ^{− k เท่านั้น}

มาตรวัดความคลาดเคลื่อนข้างต้นคือความน่าจะเป็นที่จำนวนประกอบจะถูกประกาศว่าเป็นจำนวนเฉพาะที่มีความเป็นไปได้สูงหลังจาก การทดสอบ kรอบ ในทางคณิตศาสตร์ มันคือความน่าจะเป็นแบบมีเงื่อนไข โดยที่Pคือเหตุการณ์ที่จำนวนที่กำลังทดสอบเป็นจำนวนเฉพาะ และMR คือเหตุการณ์ที่จำนวนนั้นผ่านการทดสอบมิลเลอร์-ราบินด้วยkรอบ บ่อยครั้งที่เราสนใจความน่าจะเป็นแบบมีเงื่อนไขผกผันมากกว่า นั่นคือความน่าจะเป็นที่จำนวนที่ถูกประกาศว่าเป็นจำนวนเฉพาะที่มีความเป็นไปได้สูงนั้น แท้จริงแล้วเป็นจำนวนประกอบ ความน่าจะเป็นทั้งสองนี้มีความสัมพันธ์กันโดยกฎของเบย์ส : ${\displaystyle \Pr(M\!R_{k}\mid \lnot P)}$${\displaystyle \Pr(\lnot P\mid M\!R_{k})}$

${\displaystyle {\begin{aligned}\Pr(\lnot P\mid M\!R_{k})&={\frac {\Pr(\lnot P\land M\!R_{k})}{\Pr(\lnot P\land M\!R_{k})+\Pr(P\land M\!R_{k})}}\\&={\frac {1}{1+{\frac {\Pr(M\!R_{k}\mid P)}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{\Pr(\lnot P)}}}}\\&={\frac {1}{1+{\frac {1}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{1-\Pr(P)}}}}\end{aligned}}}$

ในสมการสุดท้าย เราลดรูปนิพจน์โดยใช้ข้อเท็จจริงที่ว่าจำนวนเฉพาะทั้งหมดถูกรายงานอย่างถูกต้องว่าเป็นจำนวนเฉพาะที่มีความน่าจะเป็นสูง (การทดสอบนี้ไม่มีผลลบเท็จ ) โดยการตัดส่วนซ้ายของตัวส่วนออกเราจะได้ขอบเขตบนที่เรียบง่าย:

${\displaystyle \Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)}$

ดังนั้น ความน่าจะเป็นแบบมีเงื่อนไขนี้จึงเกี่ยวข้องไม่เพียงแต่กับการวัดข้อผิดพลาดที่กล่าวถึงข้างต้น ซึ่งมีขอบเขตจำกัดโดย 4 ^{− k} เท่านั้น แต่ยังเกี่ยวข้องกับการกระจายความน่าจะเป็นของตัวเลขที่ป้อนเข้ามาด้วย ในกรณีทั่วไป ดังที่กล่าวไว้ก่อนหน้านี้ การกระจายนี้ถูกควบคุมโดยผู้โจมตีทางด้านการเข้ารหัสลับ ดังนั้นจึงไม่เป็นที่รู้จัก เราจึงไม่สามารถอนุมานอะไรได้มากนักเกี่ยวกับเรื่องนี้อย่างไรก็ตาม ในกรณีที่เราใช้การทดสอบ Miller–Rabin เพื่อสร้างจำนวนเฉพาะ (ดูด้านล่าง ) การกระจายจะถูกเลือกโดยตัวสร้างเอง ดังนั้นเราจึงสามารถใช้ประโยชน์จากผลลัพธ์นี้ได้ ${\displaystyle \Pr(\lnot P\mid M\!R_{k})}$

Caldwell ^{[ 11 ]}ชี้ให้เห็นว่าการทดสอบจำนวนเฉพาะที่น่าจะเป็นไปได้ที่แข็งแกร่งสำหรับฐานที่แตกต่างกันบางครั้งให้การทดสอบความเป็นจำนวนเฉพาะเพิ่มเติม เช่นเดียวกับการทดสอบที่แข็งแกร่งตรวจสอบการมีอยู่ของรากที่สองของ 1 มากกว่าสองราก modulo nการทดสอบดังกล่าวสองครั้งบางครั้งสามารถตรวจสอบการมีอยู่ของรากที่สองของ −1 มากกว่าสองรากได้

สมมติว่า ในระหว่างการทดสอบจำนวนเฉพาะที่เป็นไปได้ เราพบฐานสองฐานคือa และ a ′ ซึ่ง r , r ′ ≥ 1นั่นหมายความว่าเราได้คำนวณรากที่สองสองค่าในระหว่างการทดสอบ และสามารถตรวจสอบได้ว่าซึ่งจะต้องเป็นจริงเสมอหากnเป็นจำนวนเฉพาะ ถ้าไม่เป็นเช่นนั้น แสดงว่าเราพบรากที่สองของ −1 มากกว่าสองค่า และพิสูจน์ได้ว่าnเป็นจำนวนประกอบ ${\displaystyle a^{2^{r}d}\equiv a^{\prime \,2^{r'}d}\equiv -1{\pmod {n}}}$${\displaystyle a^{2^{r-1}d}\equiv \pm a^{\prime \,2^{r'-1}d}{\pmod {n}}}$

สิ่งนี้เป็นไปได้ก็ต่อเมื่อn ≡ 1 (mod 4) และเราผ่านการทดสอบจำนวนเฉพาะที่เป็นไปได้ด้วยฐาน aสองฐานขึ้นไปโดยที่a ^d ≢ ±1 (mod n ) แต่เป็นการเพิ่มเติมที่ไม่สิ้นเปลืองต่อการทดสอบ Miller–Rabin พื้นฐาน

อัลกอริทึม Miller–Rabin สามารถทำให้เป็นแบบกำหนดได้โดยการลองค่าที่เป็นไปได้ทั้งหมดของaที่ต่ำกว่าขีดจำกัดที่กำหนด หากใช้nเป็นขีดจำกัด จะต้อง ทดลอง O( n )ครั้ง ดังนั้นเวลาในการทำงานจะเป็นแบบเลขชี้กำลังเมื่อเทียบกับขนาดlog nของข้อมูลป้อนเข้า เพื่อปรับปรุงเวลาในการทำงาน ความท้าทายจึงอยู่ที่การลดขีดจำกัดให้มากที่สุดเท่าที่จะเป็นไปได้ในขณะที่ยังคงรักษาความน่าเชื่อถือของการทดสอบไว้

ถ้าจำนวนที่ทดสอบnเป็นจำนวนประกอบ ตัวโกหกที่แข็งแกร่งa ที่เป็นจำนวนเฉพาะสัมพัทธ์กับnจะอยู่ในกลุ่มย่อย ที่เหมาะสม ของกลุ่ม ( Z / n Z )* ซึ่งหมายความว่าถ้าเราทดสอบa ทั้งหมด จากเซตที่สร้าง ( Z / n Z )* หนึ่งในนั้นจะต้องอยู่นอกกลุ่มย่อยดังกล่าว ดังนั้นจึงต้องเป็นพยานสำหรับความเป็นจำนวนประกอบของn สมมติว่า สมมติฐาน Riemann แบบทั่วไปเป็นจริง(ซึ่ง Miller เรียกอย่างสับสนว่า " สมมติฐาน Riemann แบบขยาย ") เป็นที่ทราบกันว่ากลุ่มถูกสร้างขึ้นโดยองค์ประกอบที่เล็กกว่าO(( ln n ) ² )ซึ่ง Miller ได้บันทึกไว้แล้ว^{[ 1 ]}ค่าคงที่ที่เกี่ยวข้องในสัญกรณ์ Big Oลดลงเหลือ 2 โดยEric Bach [ ^{12 ] สิ่ง}นี้นำไปสู่อัลกอริทึมการทดสอบความเป็นจำนวนเฉพาะต่อไปนี้ ซึ่งเรียกว่าการทดสอบ Millerซึ่งเป็นแบบกำหนดได้โดยสมมติว่าสมมติฐาน Riemann แบบขยายเป็นจริง:

อินพุต : n > 2 จำนวนเต็มคี่ที่จะตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่ เอาต์พุต : “ composite ” ถ้าnเป็นจำนวนประกอบ “ prime ” ถ้าไม่ใช่ 

ให้s > 0 และdเป็นจำนวนคี่ > 0 โดยที่n − 1 = 2sd # โดยการแยกตัวประกอบกำลังของ 2 ออกจากn − 1 สำหรับทุกa ในช่วง [2, min( n − 2, ⌊2(ln n ) 2⌋ )]: x ← a d mod n ทำซ้ำs ครั้ง : y ← x 2 mod n ถ้าy = 1 และx ≠ 1 และx ≠ n − 1 แล้ว# รากที่สองที่ไม่ใช่จำนวนศูนย์ของ 1 modulo nคืนค่า “ จำนวนประกอบ ” x ← y ถ้าy ≠ 1 แล้วคืนค่า “ จำนวนประกอบ ” คืนค่า “ จำนวนเฉพาะ ” 

ไม่จำเป็นต้องใช้พลังทั้งหมดของสมมติฐานรีมันน์ทั่วไปเพื่อรับรองความถูกต้องของการทดสอบ: เนื่องจากเราจัดการกับกลุ่มย่อยที่มีดัชนี คู่ จึง เพียงพอที่จะถือว่า GRH มีความถูกต้องสำหรับอักขระ Dirichletกำลังสอง^{[ 7 ]}

เวลาการทำงานของอัลกอริธึมคือÕ ( (log n ) ⁴ ) (โดยใช้การคูณตาม FFT) ^{[ 13 ]}

การทดสอบของมิลเลอร์ไม่ได้ถูกนำมาใช้ในทางปฏิบัติ สำหรับการใช้งานส่วนใหญ่ การใช้การทดสอบความน่าจะเป็นของมิลเลอร์-ราบิน หรือการทดสอบความเป็นจำนวนเฉพาะของเบลลี-พีเอสดับบลิวอย่างถูกต้อง จะให้ความมั่นใจที่เพียงพอและทำงานได้เร็วกว่ามาก นอกจากนี้ ในทางปฏิบัติยังช้ากว่าวิธีการพิสูจน์ที่ใช้กันทั่วไป เช่นAPR-CLและECPP ซึ่งให้ผลลัพธ์ที่ไม่ขึ้นอยู่กับสมมติฐานที่ยังไม่ได้รับการพิสูจน์ สำหรับวัตถุประสงค์ทางทฤษฎีที่ต้องการอัลกอริทึมแบบกำหนดเวลาเชิงพหุ นาม การทดสอบความเป็นจำนวนเฉพาะ AKSได้เข้ามาแทนที่แล้วซึ่งก็ไม่ขึ้นอยู่กับสมมติฐานที่ยังไม่ได้รับการพิสูจน์เช่นกัน

เมื่อจำนวนnที่จะทดสอบมีขนาดเล็ก การลองa < 2(ln n ) ² ทั้งหมด จึงไม่จำเป็น เนื่องจากชุดพยานที่มีศักยภาพที่เล็กกว่ามากก็เพียงพอแล้ว ตัวอย่างเช่น Pomerance, Selfridge, Wagstaff ^{[ 4 ]}และ Jaeschke ^{[ 14 ]}ได้ตรวจสอบแล้วว่า

• ถ้าn < 2,047 ก็เพียงพอที่จะทดสอบว่าa = 2 หรือไม่
• ถ้าn < 1,373,653 ก็เพียงพอที่จะทดสอบค่าa = 2 และ 3;
• ถ้าn < 9,080,191 ก็เพียงพอที่จะทดสอบค่าa = 31 และ 73;
• ถ้าn < 25,326,001 ก็เพียงพอที่จะทดสอบค่าa = 2, 3 และ 5;
• ถ้าn < 3,215,031,751 ก็เพียงพอที่จะทดสอบค่าa = 2, 3, 5 และ 7
• ถ้าn < 4,759,123,141 ก็เพียงพอที่จะทดสอบค่าa = 2, 7 และ 61
• ถ้าn < 1,122,004,669,633 ก็เพียงพอที่จะทดสอบค่าa = 2, 13, 23 และ 1662803
• ถ้าn < 2,152,302,898,747 ก็เพียงพอที่จะทดสอบค่าa = 2, 3, 5, 7 และ 11
• ถ้าn < 3,474,749,660,383 ก็เพียงพอที่จะทดสอบค่าa = 2, 3, 5, 7, 11 และ 13
• ถ้าn < 341,550,071,728,321 ก็เพียงพอที่จะทดสอบค่าa = 2, 3, 5, 7, 11, 13 และ 17
• การเพิ่มการทดสอบด้วยค่า a = 19 ไม่ได้ช่วยปรับปรุงขอบเขตก่อนหน้านี้ให้ดีขึ้น

โดยใช้ผลงานของ Feitsma และ Galway ในปี 2010 ^{[ 15 ]}ซึ่งระบุจำนวนเฉพาะเทียมฐาน 2 ทั้งหมดจนถึง 2 ⁶⁴ได้มีการขยายเพิ่มเติม (ดูOEIS :  A014233 ) โดยผลลัพธ์แรกแสดงในภายหลังโดยใช้วิธีการที่แตกต่างกันใน Jiang และ Deng: ^{[ 16 ]}

• ถ้าn < 3,825,123,056,546,413,051 ก็เพียงพอที่จะทดสอบค่าa = 2, 3, 5, 7, 11, 13, 17, 19 และ 23
• การเพิ่มการทดสอบด้วยค่าa = 29 และ 31 ไม่ได้ช่วยปรับปรุงขอบเขตก่อนหน้านี้ให้ดีขึ้น
• ถ้าn < 2 ⁶⁴ = 18,446,744,073,709,551,616 ก็เพียงพอที่จะทดสอบค่าa = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 และ 37

Sorenson และ Webster ^{[ 17 ]}ตรวจสอบข้างต้นและคำนวณผลลัพธ์ที่แม่นยำสำหรับผลลัพธ์ที่มากกว่า 64 บิตเหล่านี้:

• ถ้าn < 318,665,857,834,031,151,167,461 ก็เพียงพอที่จะทดสอบค่าa = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 และ 37
• ถ้าn < 3,317,044,064,679,887,385,961,981 ก็เพียงพอที่จะทดสอบค่าa = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 และ 41

Zhang (2007) โดยการมุ่งเน้นไปที่จำนวนเต็มเฉพาะจะให้การคาดการณ์เพิ่มเติม เช่น จำนวนเฉพาะที่ต่อเนื่องกัน 18 ตัวจะเพียงพอสำหรับn < 1,543,267,864,443,420,616,877,677,640,751,301 อย่างไรก็ตาม การพิสูจน์ว่าสิ่งนี้เป็นจริงสำหรับจำนวนเต็มทั้งหมดจนถึงขอบเขตนั้นยากกว่ามาก^{[ 18 ]}

เกณฑ์อื่นๆ ในลักษณะนี้ ซึ่งมักจะมีประสิทธิภาพมากกว่า (ต้องการฐานน้อยกว่า) เกณฑ์ที่แสดงไว้ข้างต้น มีอยู่โดยการลบข้อกำหนดที่ว่าฐานจะต้องต่อเนื่องกัน^{[ 11 ] [ 19 ] [ 20 ]}ตัวอย่างเช่น ฐานสองฐานa = 336,781,006,125 และ 9,639,812,373,923,155 ก็เพียงพอสำหรับn < 1,050,535,501; ฐานเจ็ดฐานก็เพียงพอสำหรับn < 2 ⁶⁴การเพิ่มประสิทธิภาพเพิ่มเติมโดย Steve Worley และคนอื่นๆ เกี่ยวข้องกับการแบ่งจำนวนเต็มที่น้อยกว่า N ออกเป็นเซตย่อยและเลือกพยานที่ประเมินองค์ประกอบทั้งหมดของเซตย่อยนั้นได้อย่างถูกต้อง การทดสอบดังกล่าวสามารถใช้พยานเพียง 2 ตัวสำหรับ N ทั้งหมดที่น้อยกว่า 2^64 ^{[ 21 ]}

มีรายการพยานที่เป็นไปได้จำนวนเล็กน้อยสำหรับขนาดอินพุตที่เป็นไปได้ทุกขนาด (ค่าสูงสุดbสำหรับจำนวนb บิต) อย่างไรก็ตาม ไม่มีชุดฐานที่จำกัดใดเพียงพอสำหรับจำนวนประกอบทั้งหมด Alford, Granville และ Pomerance ได้แสดงให้เห็นว่ามีจำนวนประกอบ n มากมายนับไม่ถ้วนซึ่งพยานการประกอบที่เล็กที่สุดมี ^ค่าอย่างน้อย(ln n ) ^{1/(3ln ln ln n ) [ 22} ] พวกเขายังโต้แย้งในเชิงอนุมานว่าจำนวนw ที่เล็กที่สุด ซึ่งจำนวนประกอบทุกจำนวนที่ต่ำกว่าnมีพยานการประกอบที่น้อยกว่าwควรมีลำดับΘ (log n log log n )

โดยการแทรก การคำนวณ ตัวหารร่วมมากเข้าไปในอัลกอริทึมข้างต้น บางครั้งเราสามารถหาตัวประกอบของnแทนที่จะเพียงแค่กำหนดว่าnเป็นจำนวนประกอบ ตัวอย่างเช่น เมื่อnเป็นจำนวนเฉพาะที่น่าจะเป็นไปได้สำหรับฐานa แต่ไม่ใช่จำนวนเฉพาะที่น่าจะเป็นไปได้ที่แข็งแกร่งสำหรับฐานa ^{[ 23 ] : 1402}

ถ้าxเป็นรากที่สองที่ไม่ใช่ค่าศูนย์ของ 1 มอดูล n

• เนื่องจากx² ≡ 1 (mod n ) เรา ^จึงทราบว่าn หาร x² ⁻ 1 = ( x − 1)( x + 1 ) ลงตัว
• เนื่องจากx ≢ ±1 (mod n )เราจึงทราบว่าnไม่หารx − 1และx + 1ลงตัว

จากนี้เราสรุปได้ว่าA = gcd( x − 1, n )และB = gcd( x + 1, n )เป็นตัวประกอบที่ไม่ใช่ตัวประกอบศูนย์ (ไม่จำเป็นต้องเป็นจำนวนเฉพาะ) ของn (อันที่จริง เนื่องจากnเป็นจำนวนคี่ ตัวประกอบเหล่านี้จึงเป็นจำนวนเฉพาะสัมพัทธ์ และn = AB ) ดังนั้น หากเป้าหมายคือการแยกตัวประกอบ การคำนวณ gcd เหล่านี้สามารถแทรกเข้าไปในอัลกอริทึมได้โดยใช้ทรัพยากรการคำนวณเพิ่มขึ้นเพียงเล็กน้อย ซึ่งนำไปสู่รหัสเทียมต่อไปนี้ โดยส่วนที่เพิ่มหรือเปลี่ยนแปลงจะถูกเน้นไว้:

อินพุต #1 : n > 2 จำนวนเต็มคี่ที่จะทดสอบว่าเป็นจำนวนเฉพาะหรือไม่ อินพุต #2 : kจำนวนรอบการทดสอบที่จะดำเนินการ เอาต์พุต : (“ พหุคูณของ ”, m ) หาก พบ ตัวประกอบ mที่ไม่ใช่ตัวประกอบศูนย์ของn “ จำนวนประกอบ ” หากพบว่าn เป็นจำนวนประกอบ “ น่าจะเป็นพันธุ์ชั้นดี ” มิฉะนั้น 

ให้s > 0 และd เป็นจำนวนคี่ > 0 โดยที่n − 1 = 2sd # โดยการแยกตัวประกอบกำลังของ 2 ออกจากn − 1 ทำซ้ำk ครั้ง : a ← random(2, n − 2) # nเป็นจำนวนเฉพาะที่น่าจะเป็นไปได้เสมอในฐาน 1 และn − 1 x ← ad mod n ทำซ้ำ s ครั้ง : y ← x² mod n ถ้า y = 1 และx ≠ 1 และx ≠ n − 1 แล้ว# รากที่สองที่ไม่ใช่จำนวนศูนย์ของ 1 มอดูลัสn คืนค่า (“ ตัวคูณของ ”, gcd( x − 1, n )) x ← y ถ้าy ≠ 1 แล้วคืนค่า “ จำนวนประกอบ ” คืนค่า “ น่าจะเป็นจำนวนเฉพาะ ” 

นี่ไม่ใช่ อัลกอริทึม การแยกตัวประกอบเชิงความน่าจะเป็นเพราะมันสามารถหาตัวประกอบได้เฉพาะสำหรับจำนวนnที่เป็นจำนวนเฉพาะเทียมฐานa เท่านั้น (กล่าวคือ สำหรับจำนวนnที่a ^{n −1} ≡ 1 mod n ) สำหรับจำนวนอื่นๆ อัลกอริทึมจะคืนค่า "จำนวนประกอบ" โดยไม่มีข้อมูลเพิ่มเติมใดๆ

ตัวอย่างเช่น พิจารณาn = 341 และa = 2 เราจะได้n − 1 = 85 × 4จากนั้น2 ⁸⁵ mod 341 = 32และ32 ² mod 341 = 1ซึ่งบอกเราว่าnเป็นจำนวนเฉพาะเทียมฐาน 2 แต่ไม่ใช่จำนวนเฉพาะเทียมฐาน 2 ที่แข็งแกร่ง เมื่อคำนวณหา ห.ร.ม. ในขั้นตอนนี้ เราจะพบตัวประกอบของ 341: ห.ร.ม.(32 − 1, 341) = 31ซึ่งก็คือ341 = 11 × 31

เทคนิคเดียวกันนี้สามารถนำไปใช้กับรากที่สองของค่าอื่นๆ ได้ โดยเฉพาะอย่างยิ่งรากที่สองของ −1 ที่กล่าวถึงใน§ การรวมการทดสอบหลายรายการหากการทดสอบจำนวนเฉพาะที่น่าจะเป็นไปได้ที่แข็งแกร่งสองรายการ (ที่ประสบความสำเร็จ) พบว่าx ² ≡ −1 (mod n )และy ² ≡ −1 (mod n )แต่x ≢ ± y (mod n )แล้วgcd( x − y , n )และgcd( x + y , n ) เป็นตัวประกอบที่ ^{ไม่ใช่}ตัวประกอบศูนย์ของn [ ^{11 ]}

ตัวอย่างเช่นn = 46,856,248,255,981เป็นจำนวนเฉพาะเทียมที่แข็งแกร่งสำหรับฐาน 2 และ 7 แต่ในระหว่างการทำการทดสอบ เราพบว่า

${\displaystyle 2^{(n-1)/2}\equiv 7^{(n-1)/2}\equiv -1{\pmod {n}},}$

${\displaystyle 2^{(n-1)/4}\equiv 34456063004337{\pmod {n}},{\text{ and}}}$

${\displaystyle 7^{(n-1)/4}\equiv 21307242304265{\pmod {n}}.}$

ซึ่งทำให้เราได้ตัวประกอบgcd(34456063004337 − 21307242304265, n ) = 4840261

การทดสอบมิลเลอร์-ราบินสามารถใช้สร้างจำนวนเฉพาะที่มีความน่าจะเป็นสูงได้ โดยการสุ่มเลือกจำนวนเต็มไปเรื่อยๆ จนกว่าจะได้จำนวนที่ผ่านการทดสอบ อัลกอริทึมนี้จะสิ้นสุดลงเกือบแน่นอน (เนื่องจากในแต่ละรอบการทำงานจะมีโอกาสสุ่มได้จำนวนเฉพาะ) รหัสเทียมสำหรับการสร้าง จำนวน เฉพาะ ที่มีความน่าจะเป็นสูงแบบ bบิต(โดยตั้งค่าบิตที่มีค่ามากที่สุด) มีดังนี้:

อินพุต #1 : bจำนวนบิตของผลลัพธ์ อินพุต #2 : kจำนวนรอบการทดสอบที่จะดำเนินการ เอาต์พุต : จำนวนเฉพาะที่น่าจะเป็นไปได้สูงn

ในขณะที่เป็นจริง: เลือกจำนวนเต็มคี่n แบบสุ่ม ในช่วง [2b −1 , 2b −1 ] ถ้าการทดสอบ Miller–Rabin ด้วยอินพุตnและkส่งคืนค่า “ น่าจะเป็นจำนวนเฉพาะ ” ให้ส่งคืนค่าn

แน่นอนว่าเวลาการทำงานในกรณีที่เลวร้ายที่สุดคืออนันต์ เนื่องจากลูปภายนอกอาจไม่สิ้นสุดเลย แต่โอกาสที่จะเกิดขึ้นคือศูนย์ ตามการแจกแจงแบบเรขาคณิตจำนวนการสุ่มที่คาดหวัง คือ (โดยใช้สัญลักษณ์จากก่อนหน้านี้ ) ${\displaystyle {\tfrac {1}{\Pr(M\!R_{k})}}}$

เนื่องจากจำนวนเฉพาะใดๆ ผ่านการทดสอบ ความน่าจะเป็นที่จะเป็นจำนวนเฉพาะจึงให้ค่าขอบล่างโดยประมาณของความน่าจะเป็นที่จะผ่านการทดสอบ หากเราสุ่มจำนวนเต็มคี่อย่างสม่ำเสมอในช่วง [2b ^{−1 ,} 1b ⁻¹ ] เราจะได้:

${\displaystyle \Pr(M\!R_{k})>\Pr(1)={\frac {\pi \left(2^{b}\right)-\pi \left(2^{b-1}\right)}{2^{b-2}}}}$

โดยที่ π คือฟังก์ชันนับจำนวนเฉพาะโดยใช้การขยายอนุกรมเชิงอะซิมโทติกของ π (ซึ่งเป็นการขยายทฤษฎีบทจำนวนเฉพาะ ) เราสามารถประมาณความน่าจะเป็นนี้ได้เมื่อbมีค่าเข้าสู่อินฟินิตี้ เราพบว่า:

${\displaystyle \Pr(P)={\tfrac {2}{\ln 2}}b^{-1}+{\mathcal {O}}\left(b^{-3}\right)}$

${\displaystyle {\tfrac {1}{\Pr(P)}}={\tfrac {\ln 2}{2}}b+{\mathcal {O}}\left(b^{-1}\right)}$

ดังนั้น เราจึงคาดได้ว่าตัวสร้างจะทำการทดสอบ Miller–Rabin ไม่มากไปกว่าจำนวนครั้งที่เป็นสัดส่วนกับbเมื่อพิจารณาถึงความซับซ้อนในกรณีที่เลวร้ายที่สุดของการทดสอบ Miller–Rabin แต่ละครั้ง (ดูรายละเอียดก่อนหน้านี้ ) เวลาการทำงานที่คาดหวังของตัวสร้างที่มีอินพุตbและkจะถูกจำกัดด้วยO( k b ⁴ ) (หรือÕ( k b ³ )โดยใช้การคูณแบบ FFT)

ตัวชี้วัดความคลาดเคลื่อนของเครื่องกำเนิดตัวเลขนี้คือ ความน่าจะเป็นที่มันจะสร้างตัวเลขประกอบออกมา

โดยใช้ความสัมพันธ์ระหว่างความน่าจะเป็นแบบมีเงื่อนไข (ที่แสดงไว้ในส่วนก่อนหน้านี้ ) และพฤติกรรมเชิงอะซิมโทติกของ(ที่แสดงไว้ก่อนหน้านี้) มาตรวัดข้อผิดพลาดนี้สามารถกำหนดขอบเขตบนอย่างคร่าวๆ ได้: ${\displaystyle \Pr(P)}$

${\displaystyle \Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)\leq 4^{-k}\left({\tfrac {\ln 2}{2}}b-1+{\mathcal {O}}\left(b^{-1}\right)\right).}$

ดังนั้น สำหรับค่าb ที่มากพอ การวัดความคลาดเคลื่อนนี้จะน้อยกว่าอย่างไรก็ตาม ยังมีขอบเขตที่ดีกว่านี้อีกมาก ${\displaystyle {\tfrac {\ln 2}{2}}4^{-k}b}$

โดยใช้ข้อเท็จจริงที่ว่าการทดสอบ Miller–Rabin เองมักมีขอบเขตข้อผิดพลาดที่เล็กกว่า 4 ^{− k} มาก (ดูก่อนหน้านี้ ) Damgård , LandrockและPomeranceได้กำหนดขอบเขตข้อผิดพลาดหลายประการสำหรับตัวสร้าง โดยมีพารามิเตอร์bและk หลาย ประเภท^{[ 9 ]}ขอบเขตข้อผิดพลาดเหล่านี้ช่วยให้ผู้ใช้งานสามารถเลือกk ที่เหมาะสม สำหรับความแม่นยำที่ต้องการได้

หนึ่งในขอบเขตข้อผิดพลาดเหล่านี้คือ 4 ^{− k}ซึ่งใช้ได้กับb ≥ 2 ทั้งหมด (ผู้เขียนแสดงให้เห็นเฉพาะสำหรับb ≥ 51 เท่านั้น ในขณะที่ Ronald Burthe Jr. พิสูจน์เสร็จสมบูรณ์ด้วยค่าที่เหลือ 2 ≤ b ≤ 50 ^{[ 24 ]} ) ขอบเขตง่ายๆ นี้สามารถปรับปรุงได้สำหรับค่าb ขนาดใหญ่ ตัวอย่างเช่น ขอบเขตอีกอันหนึ่งที่ผู้เขียนคนเดียวกันได้มาคือ:

${\displaystyle \left({\frac {1}{7}}b^{\frac {15}{4}}2^{-{\frac {b}{2}}}\right)4^{-k}}$

ซึ่งใช้ได้กับค่าb ≥ 21 และk ≥ b /4 ทุกค่า ขอบเขตนี้จะเล็กกว่า 4 ^{− k}เมื่อb ≥ 32

การใช้อัลกอริทึมของ Wikibook มีหน้าในหัวข้อ: การทดสอบ Primality

• ไวส์สไตน์, เอริค ดับเบิลยู. "การทดสอบ Pseudoprime ที่แข็งแกร่งของราบิน-มิลเลอร์ " แมทเวิลด์ .
• การใช้งานแบบโต้ตอบออนไลน์ของวิธีการเชิงกำหนด (อธิบายขั้นตอนการทำงานของอัลกอริธึมทีละขั้นตอน)
• แอปเพล็ต (ภาษาเยอรมัน)
• การทดสอบความเป็นจำนวนเฉพาะแบบมิลเลอร์-ราบินในภาษา C#
• การทดสอบความเป็นจำนวนเฉพาะแบบมิลเลอร์-ราบินใน JavaScript โดยใช้เลขคณิตความแม่นยำสูง