ตัวตรวจสอบจำนวนเฉพาะ

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

สำหรับตัวเลขต่ำกว่า 10¹² (หนึ่งล้านล้าน) มันทำการหารทดลองจริง: เริ่มจาก 2 ทดลองจำนวนเต็มทุกตัวที่เป็นไปได้จนถึงค่าปัดลงของ √n ว่าเป็นตัวหารหรือไม่ หยุดทันทีเมื่อมีตัวหนึ่งหารลงตัว (จำนวนประกอบ) หรือยืนยันว่าไม่มีเลยเมื่อตรวจสอบทุกตัวจนถึง √n ครบแล้ว (จำนวนเฉพาะ) สำหรับกรณีที่มีตัวทดลองจำนวนมาก ร่องรอยที่แสดงจะจำกัดแค่ ~18 ตัวแรกที่ทดลองบวกกับตัวสุดท้าย พร้อมหมายเหตุตามตรงว่ามีการข้ามการแสดงผลไปกี่ตัว — แต่โค้ดยังคงตรวจสอบทุกตัวอย่างแท้จริง ไม่มีการข้ามการคำนวณใด ๆ

สำหรับตัวเลขที่มีขนาดเท่ากับหรือสูงกว่าขีดแบ่งนั้น — ช่วงขนาดที่ใช้ในวิทยาการเข้ารหัสลับ — การหารทดลองจะใช้เวลานานเกินไป เครื่องมือจึงเปลี่ยนไปใช้การทดสอบจำนวนเฉพาะแบบ Miller–Rabin ด้วยชุดตัวยืนยันจำนวนเฉพาะ 13 ตัวที่กำหนดตายตัว (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41) ชุดตัวยืนยันชุดนี้คือผลลัพธ์ที่เป็นที่รู้จักกันดี: มันไม่ให้ผลบวกลวงสำหรับ n ใด ๆ ที่ต่ำกว่า 3,317,044,064,679,887,385,961,981 (ประมาณ 3.3×10²⁴) ซึ่งเป็นขอบเขตที่ยืนยันด้วยการคำนวณ (ดู Sorenson & Webster, 2015 และตารางตัวยืนยันแบบกำหนดตายตัวซึ่งเป็นที่ยอมรับกันอย่างกว้างขวางที่มันสังกัดอยู่) เมื่อเกินขอบเขตนี้ไป การทดสอบแบบเดิมก็ยังคงทำงาน แต่เครื่องมือจะแจ้งคุณตามตรงว่าการรับประกันกลายเป็นการรับประกันเชิงความน่าจะเป็นที่สูงมาก แทนที่จะเป็นความแน่นอนทางคณิตศาสตร์

ร่องรอย Miller–Rabin เขียน n − 1 = 2ˢ × d โดยที่ d เป็นจำนวนคี่ จากนั้นเดินผ่านการยกกำลังมอดุโลแบบ BigInt จริง — ยกกำลังสองและคูณ รีดิวซ์มอดุโล n ทุกขั้นตอนย่อย ตัวเลขจึงไม่มีวันระเบิด — ทีละบิตสำหรับตัวยืนยันตัวแรก และรายงานคำวินิจฉัยของตัวยืนยันแต่ละตัว รวมถึงตัวยืนยันที่พิสูจน์ความเป็นจำนวนประกอบ หากตัวเลขนั้นกลายเป็นว่าไม่ใช่จำนวนเฉพาะ ทุกอย่างทำงานในเบราว์เซอร์ของคุณเอง ไม่มีเซิร์ฟเวอร์ ไม่มี API ภายนอก ไม่มีข้อมูลใด ๆ ออกจากอุปกรณ์ของคุณเลย