การหาจำนวนเฉพาะที่คดเคี้ยวมาก

ปัญหาเกี่ยวกับการใช้การแสดงออกของ Chernick $(6k+1)(12k+1)(18k+1)$ และหลักการทั่วไปของมันคือจำนวนนั้นสอดคล้องกับ 1 mod 3 เสมอ ดังนั้นจำนวนสองเท่าบวกหนึ่งจึงหารลงตัวและด้วยเหตุนี้จึงไม่เป็นจำนวนเฉพาะ ทั้งหมดจะไม่สูญหายไป อย่างไรก็ตาม และวิธีการของ Loh และ Niebur "อัลกอริธึมใหม่สำหรับการสร้างตัวเลขคาร์ไมเคิลขนาดใหญ่" (ซึ่งเป็นแรงบันดาลใจให้โด่งดัง Alford, Granville และ Pomerance "มีจำนวนคาร์ไมเคิลมากมายนับไม่ถ้วน" ผลลัพธ์) สามารถใช้เพื่อสร้างตัวเลขคาร์ไมเคิลขนาดใหญ่ที่เป็น 2 mod 3 และมีหลายปัจจัย (ทำให้เหมาะสำหรับการใช้งานที่คดเคี้ยวของคุณ)

จากคำแนะนำของเราจากอัลกอริทึม C ของ Loh และ Niebur (หน้า 285) เราเพิ่มเงื่อนไขพิเศษเล็กน้อย:

1. เลือกผลิตภัณฑ์ที่มีพลังพิเศษ $\Lambda\leftarrow 2^{h_1}q_2^{h_2}\cdots q_r^{h_r}$ ที่ไหน $h_i$ ล้วนเป็นแง่บวกและไม่มีข้อใดข้อหนึ่ง $q_i$ คือ 3. (การก่อสร้างจะทำงานได้ดีที่สุดถ้า $q_i$ เป็นจำนวนเฉพาะขนาดเล็กดังนั้นการ $q_2=5$, $q_3=7$ และอื่นๆเป็นทางเลือกที่ดี)
2. ทดสอบทั้งหมด $p(\alpha_1,\ldots,\alpha_r)\leftarrow 2^{\alpha_1}q_2^{\alpha_2}\cdots q_r^{\alpha_r}+1$ กับ $0\le \alpha_i\le h_i$ สำหรับความเป็นอันดับหนึ่ง รวบรวมค่าสำเร็จเป็นชุด $\คณิตศาสตร์ S$ (เว้น $\แลมบ์ดา+1$). คุณอาจต้องการข้ามจำนวนเฉพาะ 3 ในกรณีที่จำนวนเฉพาะสมมุติฐานหารด้วย 3 ลงตัวเล็กน้อย หรือเพราะมันเป็นทางเลือกที่เป็นไปได้สำหรับฐานสำหรับการทดสอบแฟร์มาต์
3. คำนวณ $\prod_{p\in\mathcal S}\pmod\Lambda$ และเรียกสิ่งตกค้างนี้ว่า $s$.
4. ทดสอบชุดย่อย $\mathcal T\subset\mathcal S$ ซึ่งมีคาร์ดินัลลิตี้ที่มีความเท่าเทียมกันต่างกันไป $\คณิตศาสตร์ S$ จนกว่าเราจะพบส่วนย่อยดังกล่าว $\prod_{p\in\mathcal T}p\equiv s\pmod\Lambda$
5. ชุด $N=\prod_{p\in\mathcal S\backslash\mathcal T}p$. นี่จะเป็นเลขคาร์ไมเคิล จะมีตัวประกอบเฉพาะเป็นเลขคี่ และจะคอนกรูเอนต์กับ 2 มอดูล 3

ควรมีความหลากหลายเพียงพอในตัวเลือกของ $\คณิตศาสตร์ T$ เพื่อให้ได้เบอร์คาร์ไมเคิลที่มีขนาดเหมาะสม จากนั้นคุณสามารถคูณด้วยสองและเพิ่มหนึ่ง เนื่องจากจำนวนผลลัพธ์ตรงกัน $3\pmod\แลมบ์ดา$, มันจะไม่หารด้วยการหารเฉพาะใดๆ ลงตัว $\แลมบ์ดา$ และมีโอกาสดีกว่าค่าเฉลี่ยมากในการเป็นนายก (ซึ่งก็ดี)