การทดสอบเบื้องต้นเป็นอัลกอริธึมในการตัดสินว่าจำนวนอินพุตเป็นจำนวนเฉพาะหรือไม่ การทดสอบเบื้องต้นบางอย่างกำหนดได้ พวกเขาตัดสินใจได้อย่างถูกต้องเสมอว่าตัวเลขเป็นจำนวนเฉพาะหรือประกอบ
การทดสอบเดเทอร์มินิสติกไพรมาลิตีที่เป็นที่รู้จักเร็วที่สุดถูกประดิษฐ์ขึ้นในปี 2547 มีนักวิทยาศาสตร์คอมพิวเตอร์สามคน เช่น Agrawal, Kayal และ Saxena ที่คิดค้น AKS primalitytest ซึ่งดำเนินการใน O˜ (log(n) 6 ) เวลา โดยที่ O˜ (f(n)) แสดงเป็น O(f(n).log(f(n)) k ) สำหรับจำนวนเต็ม k [1] แม้ว่าจะเป็นความก้าวหน้าครั้งสำคัญ แต่ความเร็วนี้ค่อนข้างช้าเมื่อเทียบกับข้อกำหนดด้านความปลอดภัยของข้อมูล
ข้อดีของจำนวนเฉพาะคือใช้ในการเข้ารหัส อัลกอริธึมการเข้ารหัสระบบ -RSA มาตรฐานตัวใดตัวหนึ่งต้องการหมายเลขเฉพาะเป็นคีย์ ซึ่งโดยทั่วไปแล้วจะเกิน 1024 บิตเพื่อให้มีความปลอดภัยสูงขึ้น
เมื่อจัดการกับจำนวนที่มากเช่นนี้ ย่อมไม่สร้างวิธีการดังต่อไปนี้ให้ได้ผลดีอย่างแน่นอน ไม่ใช่แค่การทำงานกับตัวเลขจำนวนมากโดยเฉพาะอย่างยิ่งเมื่อการดำเนินการที่ดำเนินการคือ / และ % ณ เวลาที่ทำการทดสอบเบื้องต้น
ดังนั้น อัลกอริธึมการทดสอบในขั้นต้นที่ดีที่สุดที่ผลิตขึ้นเท่านั้นที่สามารถตัดสินใจได้ว่าตัวเลขที่ให้มานั้นเป็น "จำนวนเฉพาะที่น่าจะเป็น" หรือแบบประกอบ
การทดสอบ Primality มีประเภทดังต่อไปนี้ -
-
อัลกอริธึมที่กำหนด − อัลกอริธึมการทดสอบไพรมาลิตีแบบกำหนดแบบกำหนดได้ยอมรับจำนวนเต็มและส่งออกเฉพาะไพรม์หรือคอมโพสิตอย่างต่อเนื่อง อัลกอริทึมนี้ให้คำตอบที่ถูกต้องเสมอ
-
อัลกอริทึมการหาร − การทดสอบเบื้องต้นที่ง่ายที่สุดมีดังนี้ −
กำหนดหมายเลขอินพุต n ตรวจสอบว่าจำนวนเต็มจาก 2 ถึง n -1 หาร n หรือไม่ ถ้า n หารด้วย m ใด ๆ ลงตัว, แล้ว n จะรวมกันไม่เช่นนั้น จะเป็นจำนวนเฉพาะ อย่างไรก็ตาม แทนที่จะทดสอบ m ทั้งหมดไม่เกิน n – 1 สิ่งสำคัญคือต้องทดสอบ m ไม่เกิน √n เท่านั้น ถ้า n เป็นค่าผสม นิตสามารถแยกตัวประกอบเป็นสองค่า อย่างน้อยหนึ่งค่าควรน้อยกว่าหรือเท่ากับ √n
-
อัลกอริทึมความน่าจะเป็น − อัลกอริธึมความน่าจะเป็นให้คำตอบที่ถูกต้องเกือบตลอดเวลา แต่ไม่ใช่ทุกครั้ง การทดสอบเหล่านี้ตัดสินว่า n เป็นไปตามเงื่อนไขอย่างน้อยหนึ่งเงื่อนไขที่ไพรม์ทั้งหมดควรปฏิบัติตามหรือไม่ อัลกอริธึมความน่าจะเป็นจะคืนค่าไพรม์หรือคอมโพสิตขึ้นอยู่กับกฎต่อไปนี้ -
-
หากจำนวนเต็มที่จะทดสอบเป็นจำนวนเฉพาะจริงๆ อัลกอริทึมจะคืนค่า aprime อย่างแน่นอน
-
ถ้าจำนวนเต็มที่จะทดสอบเป็นจำนวนรวมจริง ๆ จะส่งกลับค่าผสมที่มีความน่าจะเป็น 1 − ε แต่สามารถคืนค่าจำนวนเฉพาะที่มีความน่าจะเป็น ε ได้ ความน่าจะเป็นของข้อผิดพลาดสามารถปรับปรุงได้หากสามารถเรียกใช้อัลกอริทึม 'm' ครั้งและความน่าจะเป็นของข้อผิดพลาดลดลงเป็น Σ m .
-
การทดสอบ Fermat Primality − Fermat Primality Test เกิดขึ้นจากทฤษฎีบทน้อยของ Fermat ซึ่งระบุว่าถ้า n เป็นจำนวนเฉพาะ a
n-1
≡ 1 (mod n). ให้อินพุต n และ a
