จำนวนโปรธ ( Proth number)คือจำนวนธรรมชาติNในรูปแบบที่kและnเป็นจำนวนเต็มบวกkเป็นจำนวนคี่และ จำนวนเฉพาะโปรธ ( Proth prime)คือจำนวนโปรธที่เป็นจำนวนเฉพาะ ชื่อของจำนวนเฉพาะโปรธตั้งตามชื่อของนักคณิตศาสตร์ชาวฝรั่งเศสฟรองซัวส์ โปรธ [ ^{2 ] จำนวน}เฉพาะโปรธกลุ่มแรกๆ ได้แก่ $N=k\times 2^{n}+1}$${\displaystyle 2^{n}>k}$

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857 ( OEIS :  A080076 )

ยังคงเป็นคำถามที่เปิดกว้างว่ามีจำนวนเฉพาะ Proth ที่เป็นอนันต์อยู่หรือไม่ มีการแสดงให้เห็นในปี 2022 ว่าผลรวมผกผันของจำนวนเฉพาะ Proth ลู่เข้าสู่จำนวนจริงที่ใกล้เคียง 0.747392479 ซึ่งน้อยกว่าค่า 1.093322456 สำหรับผลรวมผกผันของจำนวน Proth อย่างมาก^{[ 1 ]}

การทดสอบความเป็นจำนวนเฉพาะของจำนวนโปรธนั้นทำได้ง่ายกว่าจำนวนอื่นๆ ที่มีขนาดใกล้เคียงกันหลายจำนวน

จำนวนโปรธมีรูปแบบที่kและnเป็นจำนวนเต็มบวกเป็นจำนวนคี่ และจำนวนเฉพาะโปรธคือจำนวนเฉพาะโปรธ^{[ 2 ] [ 3 ]}หากไม่มีเงื่อนไขที่ว่าจำนวนเต็มคี่ทั้งหมดที่มากกว่า 1 จะเป็นจำนวนโปรธ^{[ 4 ]}$N=k\times 2^{n}+1}$${\displaystyle k}$${\displaystyle 2^{n}>k}$${\displaystyle 2^{n}>k}$

สามารถตรวจสอบความเป็นจำนวนเฉพาะของจำนวนโปรธได้โดยใช้ทฤษฎีบทของโปรธซึ่งกล่าวว่า จำนวนโปรธเป็นจำนวนเฉพาะก็ต่อเมื่อมีจำนวนเต็ม อยู่จำนวนหนึ่งซึ่ง เป็นจริง ${\displaystyle p}$${\displaystyle a}$

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$^{[ 3 ] [ 5 ]}

ทฤษฎีบทนี้สามารถใช้เป็นการทดสอบความน่าจะเป็นของความเป็นจำนวนเฉพาะได้ โดยการตรวจสอบค่าสุ่มหลายๆ ค่าว่าถ้า ผลลัพธ์ นี้ไม่เป็นจริงสำหรับค่าสุ่มหลายๆ ค่าแสดงว่ามีโอกาสสูงมากที่จำนวนนั้นจะเป็นจำนวนประกอบการทดสอบนี้เป็นอัลกอริทึมแบบลาสเวกัสกล่าวคือ มันจะไม่ให้ผลลัพธ์ที่ผิดพลาดแบบบวกแต่สามารถให้ผลลัพธ์ที่ผิดพลาดแบบลบได้กล่าวอีกนัยหนึ่งคือ มันจะไม่รายงานจำนวนประกอบว่าเป็น " น่าจะเป็นจำนวนเฉพาะ " แต่สามารถรายงานจำนวนเฉพาะว่าเป็น "อาจเป็นจำนวนประกอบ" ได้ ${\displaystyle a}$${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$${\displaystyle a}$${\displaystyle p}$

ในปี 2551 Sze ได้สร้างอัลกอริทึมแบบกำหนดได้ซึ่งทำงานได้ในเวลาไม่เกิน โดยที่ Õ คือ สัญกรณ์ soft-Oสำหรับการค้นหาจำนวนเฉพาะ Proth ทั่วไป มักจะคงที่ (เช่น การค้นหาจำนวนเฉพาะ 321 หรือปัญหา Sierpinski) หรือมีลำดับ(เช่น การค้นหา จำนวนเฉพาะ Cullen ) ในกรณีเหล่านี้ อัลกอริทึมจะทำงานในเวลาไม่เกินหรือเวลาสำหรับทุกค่านอกจากนี้ยังมีอัลกอริทึมที่ทำงานในเวลา^{[ 2 ] [ 6 ]}${\displaystyle {\tilde {O}}((k\log k+\log N)(\log N)^{2})}$${\displaystyle k}$${\displaystyle O(\log N)}$${\displaystyle {\tilde {O}}((\log N)^{3})}$${\displaystyle O((\log N)^{3+\epsilon })}$${\displaystyle \epsilon >0}$${\displaystyle {\tilde {O}}((\log N)^{24/7})}$

จำนวนเฟอร์มาต์เป็นกรณีพิเศษของจำนวนพรอธ โดยที่k = 1ในสถานการณ์เช่นนี้การทดสอบของเปแปงพิสูจน์ว่าจำเป็นต้องตรวจสอบเพียงฐานa = 3 เท่านั้น เพื่อยืนยันหรือปฏิเสธความเป็นจำนวนเฉพาะของจำนวนเฟอร์มาต์ได้อย่างแน่นอน

ณ ปี 2022 จำนวนเฉพาะ Proth ที่ใหญ่ที่สุดที่รู้จักคือมีความยาว 9,383,761 หลัก^{[ 7 ]}ค้นพบโดยปีเตอร์ ซาโบลซ์ ใน โครงการคอมพิวเตอร์อาสาสมัคร PrimeGridซึ่งประกาศเมื่อวันที่ 6 พฤศจิกายน 2016 ^{[ 8 ]} นอกจากนี้ยังเป็น จำนวนเฉพาะที่ไม่ใช่เมอร์เซนน์ที่ใหญ่ที่สุดอันดับสามที่รู้จักอีกด้วย^{[ 9 ]}${\displaystyle 10223\times 2^{31172165}+1}$

โครงการ"สิบเจ็ดหรือล้มเหลว" (Seventeen or Bust ) ซึ่งค้นหาจำนวนเฉพาะ Proth ที่มีค่าแน่นอนเพื่อพิสูจน์ว่า 78557 เป็นจำนวน Sierpinski ที่เล็กที่สุด ( ปัญหา Sierpinski ) ได้ค้นพบจำนวนเฉพาะ Proth ขนาดใหญ่ 11 ตัวภายในปี 2007 การแก้ ปัญหา Sierpiński เกี่ยวกับจำนวนเฉพาะและปัญหา Sierpiński ที่ขยายออกไปในลักษณะเดียวกันนี้ได้ให้ผลลัพธ์เป็นจำนวนอื่นๆ อีกหลายจำนวน ${\displaystyle t}$

เนื่องจากตัวหารของจำนวนเฟอร์มาต์ มักอยู่ในรูปแบบจึงเป็นธรรมเนียมที่จะตรวจสอบว่าจำนวนเฉพาะโพรธตัวใหม่หารจำนวนเฟอร์มาต์ได้หรือไม่^{[ 10 ]}${\displaystyle F_{n}=2^{2^{n}}+1}$${\displaystyle k\times 2^{n+2}+1}$

ณ เดือนมกราคม 2025 PrimeGridเป็นโครงการคอมพิวเตอร์ชั้นนำสำหรับการค้นหาจำนวนเฉพาะ Proth โครงการหลักของ PrimeGrid ได้แก่:

• การค้นหา Proth หลักทั่วไป
• 321 การค้นหาจำนวนเฉพาะ (ค้นหาจำนวนเฉพาะในรูปแบบหรือเรียกอีกอย่างว่าจำนวนเฉพาะ Thabit ชนิดที่สอง )${\displaystyle 3\times 2^{n}+1}$
• 27121 การค้นหาจำนวนเฉพาะ (ค้นหาจำนวนเฉพาะในรูปแบบและ)${\displaystyle 27\times 2^{n}+1}$${\displaystyle 121\times 2^{n}+1}$
• การค้นหา จำนวนเฉพาะคัลเลน (การค้นหาจำนวนเฉพาะที่มีรูปแบบ)${\displaystyle n\times 2^{n}+1}$
• ปัญหาของ Sierpinski (และปัญหาเฉพาะและปัญหาที่ขยายเพิ่มเติม) – การค้นหาจำนวนเฉพาะในรูปแบบที่kอยู่ในรายการนี้:${\displaystyle k\times 2^{n}+1}$

k ∈ {21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 209611, 222113, 225931, 227723, 229673, 237019, 238411}

ณ เดือนมิถุนายน พ.ศ. 2566 จำนวนเฉพาะ Proth ที่ใหญ่ที่สุดที่ค้นพบคือ: ^{[ 11 ]}

จำนวนโปรธชนิดที่สองคือจำนวนธรรมชาติNที่อยู่ในรูปโดยที่kและnเป็นจำนวนเต็มบวกkเป็นจำนวนคี่และจำนวนเฉพาะโปรธชนิดที่สองคือจำนวนโปรธชนิดที่สองที่เป็นจำนวนเฉพาะจำนวนเฉพาะโปรธชนิดที่สองกลุ่มแรกๆ ได้แก่ ${\displaystyle N=k\times 2^{n}-1}$${\displaystyle 2^{n}>k}$

3, 7, 11, 23, 31, 47, 79, 127, 191, 223, 239, 383, 479, 607, 863, 991, 1087, 1151, 1279, 1471, 1663, 2111, 2239, 2687, 2879, 3391, 3583, 3967, 5119, 5503, 6143, 6271, 6911, 7039, 8191, 8447, 8831, 9343 ( OEIS :  A112715 )

จำนวนเฉพาะ Proth ที่ใหญ่ที่สุดชนิดที่สองสามารถตรวจสอบความเป็นจำนวนเฉพาะได้โดยใช้การทดสอบ Lucas–Lehmer– Riesel

ณ เดือนมกราคม 2025 PrimeGridเป็นโครงการคอมพิวเตอร์ชั้นนำสำหรับการค้นหาจำนวนเฉพาะ Proth ชนิดที่สอง โครงการหลักของ PrimeGrid ได้แก่:

• การค้นหาทั่วไป Proth ไพรม์ชนิดที่สอง
• การค้นหาจำนวนเฉพาะ 321 จำนวน (ค้นหาจำนวนเฉพาะในรูปแบบหรือเรียกอีกอย่างว่าจำนวนเฉพาะ Thabit )${\displaystyle 3\times 2^{n}-1}$
• 27121 การค้นหาจำนวนเฉพาะ (ค้นหาจำนวนเฉพาะในรูปแบบและ)${\displaystyle 27\times 2^{n}-1}$${\displaystyle 121\times 2^{n}-1}$
• การค้นหา จำนวนเฉพาะแบบ Woodall (การค้นหาจำนวนเฉพาะที่มีรูปแบบ)${\displaystyle n\times 2^{n}-1}$
• ปัญหาของรีเซล (และปัญหาเฉพาะและปัญหาที่ขยายเพิ่มเติม) – การค้นหาจำนวนเฉพาะในรูปแบบที่kอยู่ในรายการนี้:${\displaystyle k\times 2^{n}-1}$

k ∈ {23669, 31859, 38473, 46663, 67117, 74699, 81041, 121889, 129007, 143047, 161669, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 485557, 494743 }

จำนวนเฉพาะ Proth ขนาดเล็ก (น้อยกว่า 10 ²⁰⁰ ) ถูกนำมาใช้ในการสร้างบันไดจำนวนเฉพาะ ซึ่งเป็นลำดับของจำนวนเฉพาะที่แต่ละพจน์ "ใกล้เคียง" (ภายในประมาณ 10 ¹¹ ) กับพจน์ก่อนหน้า บันไดดังกล่าวถูกนำมาใช้เพื่อตรวจสอบสมมติฐานที่เกี่ยวข้องกับจำนวนเฉพาะในเชิงประจักษ์ตัวอย่างเช่นสมมติฐานอ่อนของ Goldbachได้รับการตรวจสอบในปี 2008 จนถึง 8.875 × 10 ³⁰โดยใช้บันไดจำนวนเฉพาะที่สร้างจากจำนวนเฉพาะ Proth ^{[ 18 ]} (ต่อ มาHarald Helfgott ได้พิสูจน์สมมติฐานนี้^{[ 19 ] [ 20 ]} )

นอกจากนี้ จำนวนเฉพาะ Proth ยังสามารถเพิ่มประสิทธิภาพการลด den Boerระหว่างปัญหา Diffie–Hellmanและปัญหาลอการิทึมแบบไม่ต่อเนื่องได้ อีกด้วย จำนวนเฉพาะ 55 × 2 ²⁸⁶  + 1 ถูกนำมาใช้ในลักษณะนี้^{[ 21 ]}

เนื่องจากจำนวนเฉพาะ Proth มี การแสดง ไบนารี^ที่ เรียบง่าย จึงถูกนำมาใช้ในการลดโมดูลาร์อย่างรวดเร็วโดยไม่จำเป็นต้องคำนวณล่วงหน้า เช่น โดยMicrosoft [ ^{22 ]}