น่าจะเป็นจำนวนเฉพาะ

ในทฤษฎีจำนวน จำนวนเฉพาะที่น่าจะเป็น (Probable PrimeหรือPRP ) คือจำนวนเต็มที่ตรงตามเงื่อนไขเฉพาะอย่างหนึ่ง ซึ่งเป็นเงื่อนไขที่จำนวนเฉพาะทุกจำนวน ตรงตาม เงื่อนไขนี้แต่จำนวนประกอบส่วนใหญ่ไม่ตรงตามเงื่อนไขดังกล่าว จำนวนเฉพาะที่น่าจะเป็นแต่ละประเภทจะมีเงื่อนไขเฉพาะที่แตกต่างกัน แม้ว่าอาจจะมีจำนวนเฉพาะที่น่าจะเป็นที่เป็นจำนวนประกอบ (เรียกว่าจำนวนเฉพาะเทียม ) แต่โดยทั่วไปแล้วเงื่อนไขจะถูกเลือกเพื่อให้ข้อยกเว้นดังกล่าวเกิดขึ้นได้ยาก

การทดสอบความเป็นจำนวนประกอบของแฟร์มาต์ ซึ่งอิงตามทฤษฎีบทเล็กของแฟร์มาต์ทำงานดังนี้: กำหนดจำนวนเต็มnให้เลือกจำนวนเต็มaที่ไม่ใช่พหุคูณของn (โดยทั่วไป เราจะเลือกaในช่วง1 < a < n − 1 ) คำนวณa ^{n − 1}มอดูล nถ้าผลลัพธ์ไม่ใช่ 1 แสดงว่าnเป็นจำนวนประกอบ ถ้าผลลัพธ์เป็น 1 แสดงว่าnมีแนวโน้มที่จะเป็นจำนวนเฉพาะnจึงเรียกว่าจำนวนเฉพาะที่น่าจะเป็นฐานa จำนวนเฉพาะที่น่าจะเป็นฐาน aแบบอ่อน คือจำนวนเต็มที่เป็นจำนวนเฉพาะที่น่าจะเป็นฐานaแต่ไม่ใช่จำนวนเฉพาะที่น่าจะเป็นฐานa แบบเข้ม (ดูด้านล่าง)

สำหรับฐานคงที่aเป็นเรื่องผิดปกติที่จำนวนประกอบจะเป็นจำนวนเฉพาะที่เป็นไปได้ (นั่นคือ จำนวนเฉพาะเทียม) สำหรับฐานนั้น ตัวอย่างเช่น จนถึง 25 พันล้าน มีจำนวนประกอบคี่ 11,408,012,595 จำนวน แต่มีจำนวนเฉพาะเทียมฐาน 2 เพียง 21,853 จำนวน^{[ 1 ]}^{: 1005}จำนวนจำนวนเฉพาะคี่ในช่วงเดียวกันคือ 1,091,987,404

คุณสมบัติ

ความน่าจะเป็นของจำนวนเฉพาะเป็นพื้นฐานสำหรับอัลกอริทึม การทดสอบจำนวนเฉพาะ ที่มีประสิทธิภาพ ซึ่งมีการประยุกต์ใช้ในด้านการเข้ารหัสลับ อัลกอริทึมเหล่านี้มักมี ลักษณะ เป็นความน่าจะเป็นแนวคิดคือ ในขณะที่มีจำนวนเฉพาะประกอบที่น่าจะเป็นฐานaสำหรับa ใดๆ ที่กำหนดไว้ เราอาจหวังว่าจะมีค่าคงที่P < 1 อยู่ค่าหนึ่ง เช่น สำหรับจำนวนประกอบn ใดๆหากเราเลือกaแบบสุ่ม ความน่าจะเป็นที่nจะเป็นจำนวนเฉพาะเทียมฐานaจะมีค่าไม่เกินPหากเราทำการทดสอบนี้ซ้ำk ครั้ง โดยเลือก aใหม่ทุกครั้ง ความน่าจะเป็นที่n จะเป็นจำนวนเฉพาะเทียมฐาน aทั้งหมดที่ทดสอบจะมีค่าไม่เกินP ^kและเนื่องจากค่านี้ลดลงแบบเลขชี้กำลัง จึงต้องการ ค่า k เพียงเล็กน้อย เพื่อให้ความน่าจะเป็นนี้มีค่าน้อยมากจนแทบไม่มีนัยสำคัญ (เมื่อเทียบกับตัวอย่างเช่น ความน่าจะเป็นของข้อผิดพลาดของฮาร์ดแวร์คอมพิวเตอร์)

น่าเสียดายที่ข้อความนี้ไม่ถูกต้องสำหรับจำนวนเฉพาะที่มีโอกาสน้อยแบบอ่อน เนื่องจากมีจำนวนคาร์ไมเคิล อยู่ แต่ข้อความนี้ถูกต้องสำหรับแนวคิดที่ละเอียดกว่าเกี่ยวกับความน่าจะเป็นของจำนวนเฉพาะ เช่น จำนวนเฉพาะที่มีโอกาสมากแบบเข้มแข็ง ( P = 1/4, อัลกอริทึม ของมิลเลอร์- ราบิน ) หรือจำนวนเฉพาะที่มีโอกาสมากแบบออยเลอร์ ( P = 1/2, อัลกอริทึม ของโซโลเวย์-สตรัสเซน )

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

บางครั้งการทดสอบ PRP จะถูกนำมาใช้ร่วมกับตารางจำนวนเฉพาะเทียมขนาดเล็ก เพื่อตรวจสอบความเป็นจำนวนเฉพาะของจำนวนที่กำหนดซึ่งมีค่าน้อยกว่าเกณฑ์ที่กำหนดได้อย่างรวดเร็ว

การเปลี่ยนแปลง

จำนวนเฉพาะที่น่าจะ เป็นของออยเลอร์ในฐาน a คือจำนวนเต็มที่ระบุว่าเป็นจำนวนเฉพาะโดยทฤษฎีบทที่แข็งแกร่งกว่าเล็กน้อยที่ว่าสำหรับจำนวนเฉพาะ p ใดๆ a ( p − 1 ) / ²^{เท่ากับ}^โม^ดูลัสpโดยที่คือสัญลักษณ์ของจาโคบีจำนวนเฉพาะที่น่าจะเป็นของออยเลอร์ที่เป็นจำนวนประกอบเรียกว่าจำนวนเฉพาะเทียมของออยเลอร์-จาโคบีในฐานaจำนวนเฉพาะเทียมของออยเลอร์-จาโคบีที่เล็กที่สุดในฐาน 2 คือ 561 ^[¹^]^:¹⁰⁰⁴ มีจำนวนเฉพาะเทียมของออยเลอร์-จาโคบีในฐาน 2 จำนวน 11347 ตัวที่น้อยกว่า 25·10 ⁹^[¹^]^:¹⁰⁰⁵ $({\tfrac {a}{p}})$ $({\tfrac {a}{p}})$

การทดสอบของแฟร์มาต์อาจปรับปรุงได้โดยใช้ข้อเท็จจริงที่ว่ารากที่สองของ 1 มอดูลจำนวนเฉพาะ a มีเพียง 1 และ−1เท่านั้น เขียนn = d · 2 ^s + 1 โดยที่dเป็นจำนวนคี่ จำนวนnเป็นจำนวนเฉพาะที่น่าจะเป็นไปได้มาก ( SPRP ) ฐานaถ้า:

a^{d}\equiv 1{\pmod {n}},\;

หรือ

a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ สำหรับบางค่า }}0\leq r\leq s-1.\,

จำนวนเฉพาะที่เป็นไปได้แบบแข็งแกร่งเชิงประกอบบนฐานaเรียกว่าจำนวนเฉพาะเทียมแบบแข็งแกร่งบนฐานaจำนวนเฉพาะที่เป็นไปได้แบบแข็งแกร่งบนฐานa ทุกตัว จะเป็นจำนวนเฉพาะที่เป็นไปได้แบบออยเลอร์บนฐานเดียวกันด้วย แต่ในทางกลับกันนั้นไม่เป็นเช่นนั้น

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

ตัวอย่างการทดสอบหาจำนวนเฉพาะที่มีความเป็นไปได้สูง

เพื่อทดสอบว่า 97 เป็นจำนวนเฉพาะที่มีความเป็นไปได้สูงบนฐาน 2 หรือไม่:

ขั้นตอนที่ 1: หาค่าและสำหรับค่า ที่โดยที่เป็นค่าคี่ $d$ $d$ $s$ $s$ $96=d\cdot 2^{s}$ $96=d\cdot 2^{s}$ $d$ $d$
- หากเริ่มต้นด้วยจะเป็น $s=0$ $d$ $96$
- เมื่อเพิ่มขึ้นเราจะเห็นว่าและเนื่องจาก $s$ $d=3$ $s=5$ $96=3\cdot 2^{5}$
ขั้นตอนที่ 2: เลือกเราจะเลือก $a$ $1<a<97-1$ $a=2$
ขั้นตอนที่ 3: คำนวณเช่นเนื่องจากมันไม่สอดคล้องกับเราจึงดำเนินการทดสอบเงื่อนไขถัดไป $a^{d}{\bmod {n}}$ $2^{3}{\bmod {9}}7$ $1$
ขั้นตอนที่ 4: คำนวณหาค่าถ้าค่า สอดคล้องกับแสดงว่า น่าจะเป็นจำนวนเฉพาะ มิฉะนั้นจะเป็นจำนวนเฉพาะ $2^{3\cdot 2^{r}}{\bmod {9}}7$ $2^{3\cdot 2^{r}}{\bmod {9}}7$ $0\leq r<s$ $0\leq r<s$ $96$ $96$ $97$ $97$ $97$ $97$
ดังนั้น จึงเป็นจำนวนเฉพาะฐาน 2 ที่น่าจะเป็นไปได้สูง (และด้วยเหตุนี้จึงเป็นจำนวนเฉพาะฐาน 2 ที่น่าจะเป็นไปได้) และในความเป็นจริงแล้วมันก็เป็นจำนวนเฉพาะด้วย $97$