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

ใบรับรองความเป็นจำนวนเฉพาะนำไปสู่การพิสูจน์โดยตรงว่าปัญหาต่างๆ เช่นการทดสอบความเป็นจำนวนเฉพาะและส่วนเติมเต็มของการแยกตัวประกอบจำนวนเต็มอยู่ในNPซึ่งเป็นกลุ่มของปัญหาที่ตรวจสอบได้ในเวลาพหุนามเมื่อมีคำตอบ ปัญหาเหล่านี้อยู่ในco-NP อยู่แล้วอย่างเห็นได้ ชัด นี่เป็นหลักฐานที่ชัดเจนครั้งแรกว่าปัญหาเหล่านี้ไม่ใช่NP-completeเพราะถ้าเป็นเช่นนั้น จะหมายความว่า NP เป็นเซตย่อยของ co-NP ซึ่งเป็นผลลัพธ์ที่เชื่อกันอย่างกว้างขวางว่าไม่เป็นความจริง อันที่จริง นี่เป็นการสาธิตครั้งแรกของปัญหาใน NP intersect co-NP ที่ในขณะนั้นยังไม่เป็นที่รู้จักว่าอยู่ใน P

การสร้างใบรับรองสำหรับปัญหาการหาจำนวนประกอบ เพื่อพิสูจน์ว่าจำนวนนั้นเป็นจำนวนประกอบนั้นทำได้ง่าย เพียงแค่ระบุตัวหารที่ไม่ใช่จำนวนศูนย์ก็เพียงพอแล้ว การทดสอบความเป็นจำนวนเฉพาะเชิงความน่าจะเป็นมาตรฐาน เช่นการทดสอบความเป็นจำนวนเฉพาะของ Baillie–PSW การทดสอบความเป็นจำนวนเฉพาะของ Fermatและการทดสอบความเป็นจำนวนเฉพาะของ Miller–Rabinก็สามารถสร้างใบรับรองความเป็นจำนวนประกอบได้ในกรณีที่จำนวนป้อนเข้าเป็นจำนวนประกอบ แต่จะไม่สร้างใบรับรองสำหรับจำนวนเฉพาะที่ป้อนเข้า

แนวคิดของใบรับรองจำนวนเฉพาะได้รับการนำเสนอในเชิงประวัติศาสตร์โดย ใบรับรอง ^ของ Prattซึ่งคิดค้นขึ้นในปี 1975 โดยVaughan Pratt [ ^{1 ]}ซึ่งได้อธิบายโครงสร้างและพิสูจน์ว่ามีขนาดพหุนามและสามารถตรวจสอบได้ในเวลาพหุนาม โดยอิงจากการทดสอบจำนวนเฉพาะของ Lucasซึ่งโดยพื้นฐานแล้วเป็นบทกลับของทฤษฎีบทเล็กของ Fermatพร้อมเงื่อนไขเพิ่มเติมเพื่อให้เป็นจริง:

ทฤษฎีบทของลูคัส : สมมติว่าเรามีจำนวนเต็มaที่มีคุณสมบัติดังนี้:

• a ^{n − 1} ≡ 1 (mod n ),
• สำหรับตัวประกอบเฉพาะq ทุกตัว ของn − 1 นั้น ไม่เสมอไปที่a ^{( n  − 1)/ q} ≡ 1 (mod n )

ดังนั้นnจึงเป็นจำนวนเฉพาะ

เมื่อกำหนดค่าa ดังกล่าว (เรียกว่าพยาน ) และการแยกตัวประกอบเฉพาะของn  − 1 แล้ว การตรวจสอบเงื่อนไขข้างต้นอย่างรวดเร็วนั้นทำได้ง่ายมาก: เราเพียงแค่ต้องทำการยกกำลังแบบมอดูลาร์จำนวนเชิงเส้นเท่านั้น เนื่องจากจำนวนเต็มทุกจำนวนมีตัวประกอบเฉพาะน้อยกว่าจำนวนบิต และแต่ละจำนวนสามารถทำได้โดยการยกกำลังด้วย การยกกำลัง สองใน O(log n ) การคูณ (ดูสัญกรณ์บิ๊กโอ ) แม้แต่การคูณจำนวนเต็มแบบง่ายๆ ก็ใช้เวลา เพียง O((log n ) ^{4 ) เท่านั้น การใช้} อัลกอริธึมการคูณที่มีเวลาการทำงานเชิงเส้นกำกับที่ดีที่สุดเท่าที่ทราบ ซึ่งพัฒนาโดย David Harvey และJoris van der Hoevenเราสามารถลดเวลาการทำงานนี้ลงเหลือ O((log n ) ³ (log log n )) หรือใช้สัญกรณ์ซอฟต์โอ Õ((log n ) ³ )

อย่างไรก็ตาม เป็นไปได้ที่จะหลอกผู้ตรวจสอบให้ยอมรับจำนวนประกอบได้โดยการให้ "การแยกตัวประกอบเฉพาะ" ของn  − 1 ที่รวมถึงจำนวนประกอบ ตัวอย่างเช่น สมมติว่าเราอ้างว่าn  = 85 เป็นจำนวนเฉพาะ โดยให้a  = 4 และn  − 1 = 6 × 14 เป็น "การแยกตัวประกอบเฉพาะ" จากนั้น (โดยใช้q  = 6 และq  = 14):

• 4 เป็นจำนวนเฉพาะสัมพัทธ์กับ 85
• 4 ⁸⁵⁻¹ ≡ 1 (mod 85)
• 4 ^(85−1)/6 ≡ 16 (ม็อด 85), 4 ^(85−1)/14 ≡ 16 (ม็อด 85)

เราอาจสรุปผิดพลาดว่า 85 เป็นจำนวนเฉพาะ เราไม่ต้องการบังคับให้ผู้ตรวจสอบต้องแยกตัวประกอบของจำนวนนั้นโดยตรง ดังนั้นวิธีที่ดีกว่าในการหลีกเลี่ยงปัญหานี้คือการให้ใบรับรองความเป็นจำนวนเฉพาะสำหรับตัวประกอบเฉพาะแต่ละตัวของn  − 1 ด้วย ซึ่งเป็นเพียงตัวอย่างที่เล็กกว่าของปัญหาเดิม เราดำเนินการแบบเรียกซ้ำในลักษณะนี้ต่อไปจนกว่าเราจะถึงจำนวนที่ทราบว่าเป็นจำนวนเฉพาะ เช่น 2 ในที่สุดเราจะได้ต้นไม้ของจำนวนเฉพาะ โดยแต่ละจำนวนเฉพาะจะเชื่อมโยงกับพยานaตัวอย่างเช่น นี่คือใบรับรอง Pratt ที่สมบูรณ์สำหรับจำนวน 229:

• 229 ( a  = 6, 229 − 1 = 2 ²  × 3 × 19),
  • 2 (จำนวนเฉพาะที่ทราบ)
  • 3 ( a  = 2, 3 − 1 = 2)
    • 2 (จำนวนเฉพาะที่ทราบ)
  • 19 ( a  = 2, 19 − 1 = 2 × 3 ² ),
    • 2 (จำนวนเฉพาะที่ทราบ)
    • 3 ( a  = 2, 3 − 1 = 2)
      • 2 (จำนวนเฉพาะที่ทราบแล้ว)

สามารถแสดงได้ว่าต้นไม้พิสูจน์นี้มีค่าไม่เกิน 2 โดยใช้การพิสูจน์แบบอุปนัยอย่างง่าย (โดยอิงจากทฤษฎีบทที่ 2 ของ Pratt) ผลลัพธ์นี้ใช้ได้กับ 3 ด้วย โดยทั่วไป ให้เลือกp > 3 และให้ลูกของมันในต้นไม้เป็นp ₁ , ..., p _kตามสมมติฐานแบบอุปนัย ต้นไม้ที่มีรากอยู่ที่p _iจะมีค่าไม่เกินดังนั้นต้นไม้ทั้งหมดจะมีค่าไม่เกิน ${\displaystyle 4\log _{2}n-4}$${\displaystyle 4\log _{2}p_{i}-4}$

${\displaystyle 1+\sum _{i=1}^{k}(4\log _{2}p_{i}-4)=-4k+4\log _{2}p_{1}\cdots p_{k}\leq 4\log _{2}p-4,}$

เนื่องจากk ≥ 2 และp ₁ ... p _k ≤ p  − 1 เนื่องจากแต่ละค่ามีบิตอย่างมากที่สุด log nบิต ดังนั้นจึงแสดงให้เห็นว่าใบรับรองมีขนาด O((log n ) ² ) บิต

เนื่องจากมีค่า O(log n ) ค่าอื่นที่ไม่ใช่ 2 และแต่ละค่าต้องใช้การยกกำลังอย่างมากที่สุดหนึ่งครั้งในการตรวจสอบ (และการยกกำลังใช้เวลาส่วนใหญ่ในการทำงาน) ดังนั้นเวลาทั้งหมดจึงเป็น O((log n ) ³ ( log log n )(log log log n )) หรือ Õ((log n ) ³ ) ซึ่งค่อนข้างเป็นไปได้สำหรับตัวเลขในช่วงที่นักทฤษฎีจำนวนเชิงคำนวณมักใช้กัน

อย่างไรก็ตาม แม้ว่าในทางทฤษฎีจะมีประโยชน์และตรวจสอบได้ง่าย แต่การสร้างใบรับรอง Pratt สำหรับn นั้นจำเป็นต้องแยกตัวประกอบn  − 1 และจำนวนอื่นๆ ที่อาจมีขนาดใหญ่ ซึ่งทำได้ง่ายสำหรับจำนวนพิเศษบางจำนวน เช่นจำนวนเฉพาะของแฟร์มาต์แต่ในปัจจุบันทำได้ยากกว่าการทดสอบความเป็นจำนวนเฉพาะอย่างง่ายสำหรับจำนวนเฉพาะขนาดใหญ่ที่มีรูปแบบทั่วไปมาก

เพื่อแก้ไขปัญหาการสร้างใบรับรองที่มีประสิทธิภาพสำหรับจำนวนที่มากขึ้น ในปี 1986 Shafi GoldwasserและJoe Kilianได้อธิบายใบรับรองประเภทใหม่ที่อิงตามทฤษฎีเส้นโค้งวงรี [ ^{2 ] ซึ่ง}ต่อมาAOL AtkinและFrançois Morain ได้นำมาใช้ เป็นพื้นฐานสำหรับใบรับรอง Atkin-Goldwasser-Kilian-Morain ซึ่งเป็นใบรับรองประเภทที่สร้างและตรวจสอบโดย ระบบ การพิสูจน์จำนวนเฉพาะเส้นโค้งวงรี (ECPP) ^{[ 3 ]}เช่นเดียวกับใบรับรอง Pratt ที่อิงตามทฤษฎีบทของ Lucasใบรับรอง Atkin–Goldwasser–Kilian–Morain ก็อิงตามทฤษฎีบทต่อไปนี้ของ Goldwasser และ Kilian (บทที่ 2 ของ "จำนวนเฉพาะเกือบทั้งหมดสามารถรับรองได้อย่างรวดเร็ว"):

ทฤษฎีบท : สมมติว่าเราได้รับข้อมูลดังต่อไปนี้:

• จำนวนเต็มบวกn ที่หาร ด้วย 2 หรือ 3 ไม่ลงตัว;
• M _x , M _y , A, B ใน(จำนวนเต็ม mod n ) ที่สอดคล้องกับ M _y ² = M _x ³ + AM _x + B และ 4A ³ + 27B ² เป็นจำนวน เฉพาะสัมพัทธ์กับn${\displaystyle \mathbb {Z} _{n}}$
• จำนวนเฉพาะ${\displaystyle q>n^{1/2}+1+2n^{1/4}}$

ดังนั้น M = (M _x , M _y ) เป็นจุดที่ไม่ใช่เอกลักษณ์บนเส้นโค้งวงรีy ² = x ³ + Ax + B ให้k M เป็น M ที่บวกกับตัวเองkครั้งโดยใช้การบวกเส้นโค้งวงรีแบบมาตรฐาน ถ้าq M เป็นสมาชิกเอกลักษณ์ I แล้วnจะเป็นจำนวนเฉพาะ

ในทางเทคนิคแล้ว เส้นโค้งวงรีสามารถสร้างขึ้นได้เฉพาะบนฟิลด์เท่านั้น และจะเป็นฟิลด์ได้ก็ต่อเมื่อnเป็นจำนวนเฉพาะ ดังนั้นดูเหมือนว่าเรากำลังสมมติผลลัพธ์ที่เราพยายามพิสูจน์อยู่ ความยากลำบากเกิดขึ้นในขั้นตอนวิธีบวกเส้นโค้งวงรี ซึ่งใช้ตัวผกผันในฟิลด์ที่อาจไม่มีอยู่จริงอย่างไรก็ตาม สามารถแสดงได้ (บทพิสูจน์ย่อยที่ 1 ของ "Almost All Primes Can Be Quickly Certified") ว่าหากเราเพียงแค่ทำการคำนวณราวกับว่าเส้นโค้งนั้นถูกกำหนดไว้อย่างดี และไม่พยายามหาตัวผกผันขององค์ประกอบที่ไม่มีตัวผกผัน ผลลัพธ์ก็ยังคงถูกต้อง หากเราพบองค์ประกอบที่ไม่มีตัวผกผัน นั่นแสดงว่าnเป็นจำนวนประกอบ ${\displaystyle \mathbb {Z} _{n}}$${\displaystyle \mathbb {Z} _{n}}$

ในการสร้างใบรับรองจากทฤษฎีบทนี้ เราจะเข้ารหัส M _x , M _y , A, B และq ก่อน จากนั้นจึงเข้ารหัสการพิสูจน์ความเป็นจำนวนเฉพาะแบบเรียกซ้ำสำหรับq < nต่อไปเรื่อยๆ จนกว่าจะถึงจำนวนเฉพาะที่ทราบ ใบรับรองนี้มีขนาด Õ((log n ) ² ) และสามารถตรวจสอบได้ในเวลา Õ((log n ) ⁴ ) ยิ่งไปกว่านั้น อัลกอริทึมที่สร้างใบรับรองเหล่านี้สามารถแสดงให้เห็นได้ว่าใช้เวลาแบบพหุนามที่คาดหวังได้สำหรับจำนวนเฉพาะเกือบทั้งหมด ยกเว้นเพียงส่วนน้อย และสัดส่วนนี้จะลดลงแบบเลขชี้กำลังตามขนาดของจำนวนเฉพาะ ดังนั้นจึงเหมาะอย่างยิ่งสำหรับการสร้างจำนวนเฉพาะสุ่มขนาดใหญ่ที่ได้รับการรับรอง ซึ่งเป็นแอปพลิเคชันที่สำคัญใน แอปพลิเคชัน การเข้ารหัสลับเช่น การสร้างคีย์ RSA ที่พิสูจน์ได้ว่าถูกต้อง

เวลาที่ใช้ในการสร้างใบรับรอง ECPP นั้นไม่มีขอบเขตจำกัด แต่การอนุมานเชิงฮิวริสติกให้ค่า Õ((log n ) ⁶ ) ซึ่งดำเนินการอย่างง่ายๆ ดังเช่นใน Goldwasser-Kilian Atkin และ Morain ลดตัวเลขลงเหลือ Õ((log n ) ⁵ ) FastECPP (Shallit, Franke, Morain, Enge) ได้ลดเวลาลงเหลือ Õ((log n ) ⁴ ) ^{[ 4 ]}

การสร้างจำนวนเฉพาะที่พิสูจน์ได้โดยอาศัยรูปแบบต่างๆ ของทฤษฎีบทของ Pocklington (ดูการทดสอบความเป็นจำนวนเฉพาะของ Pocklington ) ^{[ 5 ]}อาจเป็นเทคนิคที่มีประสิทธิภาพในการสร้างจำนวนเฉพาะ (โดยทั่วไปต้นทุนจะน้อยกว่าการสร้างแบบความน่าจะเป็น) พร้อมด้วยประโยชน์เพิ่มเติมของใบรับรองความเป็นจำนวนเฉพาะในตัว แม้ว่าสิ่งเหล่านี้อาจดูเหมือนเป็นจำนวนเฉพาะพิเศษ โปรดสังเกตว่าจำนวนเต็มเฉพาะทุกจำนวนสามารถสร้างได้ด้วยอัลกอริทึมการสร้างที่พิสูจน์ได้โดยอาศัย Pocklington

ให้โดยที่เป็นจำนวนเฉพาะที่แตกต่างกัน โดยมีจำนวนเต็มมากกว่าศูนย์ และมีพยานหลักฐาน ที่สอดคล้องกับเงื่อนไข ดังต่อไปนี้: ${\displaystyle P=Rh+1}$${\displaystyle R=\prod q_{j}^{e_{j}}}$${\displaystyle q_{j}}$${\displaystyle e_{j}}$${\displaystyle g}$

1.${\displaystyle g^{Rh}\equiv 1{\bmod {P}}}$

1

2. สำหรับทุกคน${\displaystyle \gcd((g^{Rh/q_{j}}-1{\bmod {P}}),P)=1}$${\displaystyle q_{j}}$

2

ดังนั้น P จะเป็นจำนวนเฉพาะ ถ้าเงื่อนไขใดเงื่อนไขหนึ่งต่อไปนี้เป็นจริง:

ก) (ดู[ 6 ] ) หรือเทียบเท่า${\displaystyle R\geq h}$${\displaystyle R>P^{1/2}}$

3ก

ข) (ดู[ 7 ] : บทสรุป 1 ) หรือเทียบเท่าและ ${\displaystyle R\geq h^{1/2}}$${\displaystyle R>P^{1/3}}$ กับ,${\displaystyle {\begin{array}{lr}a\equiv h{\bmod {R}}&0\leq a<R\\b=(ha)/R\end{array}}}$ โดยที่และมีจำนวนเฉพาะเล็ก ๆ อยู่จำนวนหนึ่งซึ่งทำให้${\displaystyle (a-4b)\neq 0}$${\displaystyle r>2}$${\displaystyle (a-4b)^{r/2}\neq 1{\bmod {r}}}$

3b

ใบรับรองความเป็นจำนวนเฉพาะของ Pocklington ประกอบด้วยจำนวนเฉพาะ P, เซตของจำนวนเฉพาะที่หาร P ลงตัวโดยแต่ละจำนวนเฉพาะจะมีใบรับรองความเป็นจำนวนเฉพาะของ Pocklington ของตนเอง หรือมีขนาดเล็กพอที่จะเป็นจำนวนเฉพาะที่ทราบได้ และพยาน ${\displaystyle q_{j}}$${\displaystyle (P-1)}$${\displaystyle g}$

ขั้นตอนที่จำเป็นสำหรับการขอใบรับรองนี้ (และลำดับของค่าใช้จ่ายในการคำนวณ) ควรเป็นผลรวมของขั้นตอนเหล่านี้:

1. ตรวจสอบว่าจำนวนทั้งหมดเป็นจำนวนเฉพาะและหารลงตัวโดยจะได้ค่าและในกระบวนการนี้ ซึ่งจะใช้เวลาน้อยกว่าขั้นตอนที่เหลือ${\displaystyle q_{j}}$${\displaystyle P-1}$${\displaystyle R}$${\displaystyle h}$
2. ตรวจสอบว่า ( 1 ) เป็นจริง ความซับซ้อนนี้เท่ากับการทดสอบความเป็นจำนวนเฉพาะของแฟร์มาต์ Õ((log P ) ² )
3. ตรวจสอบว่า ( 2 ) เป็นจริง ซึ่งต้องคำนวณ gcd ซึ่งสำหรับจำนวนมากมักจะใช้อัลกอริทึมยุคลิดแบบขยายโดยคำนวณจากจำนวนเฉพาะที่กำหนด แต่ละการดำเนินการใช้เวลาตั้งแต่ Õ((log P ) ² ) ถึง Õ((log P ) ³ ) ขึ้นอยู่กับขนาดสัมพัทธ์ของกับ${\displaystyle q_{j}}$${\displaystyle P}$
4. ตรวจสอบว่าขั้นตอนสุดท้ายถูกต้องหรือไม่ ขั้นตอนนี้โดยประมาณคือ:
   • ${\displaystyle \log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{3^{k}}}\right)=1.5\log _{2}{P}}$สำหรับเวอร์ชัน ( 3b ) ถึง
   • ${\displaystyle \log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{2^{k}}}\right)=2\log _{2}{P}}$สำหรับเวอร์ชัน ( 3a )

ดูเอกสารของPARI/GP เพิ่มเติม ^{[ 8 ]}

ให้. สังเกตว่าและ, . ${\displaystyle P=1056893}$${\displaystyle (P-1)=1621\cdot 163\cdot 2^{2}}$${\displaystyle P^{1/2}=1028.053\ldots }$${\displaystyle P^{1/3}=101.86156\ldots }$

• โดยใช้ 'พยาน' 2 สมการที่1จะเป็นจริง และสม การ ที่2โดยใช้และ${\displaystyle q=163}$${\displaystyle q=1621}$
• สำหรับเวอร์ชัน3aใบรับรองต้องการเพียง.${\displaystyle P=1056893,\ q=1621,\ g=2}$
• สำหรับเวอร์ชัน3bใบรับรองต้องการเพียงแต่ยังมีขั้นตอนเพิ่มเติมอีกเล็กน้อย: ${\displaystyle P=1056893,\ q=163,\ g=2}$
  • ${\displaystyle h=(1056893-1)/163=6484}$
  • ${\displaystyle a\equiv h\equiv 127{\bmod {163}}}$และ${\displaystyle b=\left(6484-127\right)/163=39}$
  • การใช้งานล้มเหลว:${\displaystyle r=3}$${\displaystyle \left(127^{2}-4\cdot 39\right)^{(3-1)/2}\equiv (1^{2}-0)^{1}\equiv 1{\bmod {3}}}$
  • การใช้งานสำเร็จ: และเป็นจำนวนเฉพาะ${\displaystyle r=5}$${\displaystyle \left(127^{2}-4\cdot 39\right)^{(5-1)/2}\equiv (2^{2}-1)^{2}\equiv 2{\bmod {5}}}$${\displaystyle P}$

ใบรับรองที่อิงตามวิธีการของ Gerbicz มีจุดประสงค์เพื่อพิสูจน์ความถูกต้องของ กระบวนการ ยกกำลังแบบโมดูลาร์ที่ใช้ในการทดสอบความน่าจะเป็นของ Proth และ Fermat รวมถึงขั้นตอนแรก ๆ ของการทดสอบ Pocklington นอกจากนี้ยังได้รับการดัดแปลงเพื่อใช้ในการคำนวณพจน์ลำดับ Lucas ซึ่งใช้ในการทดสอบ Lucas–Lehmer และ Lucas–Lehmer–Riesel แบบกำหนดได้ ใบรับรองประเภทนี้ต้องใช้พื้นที่และเวลาในการผลิตมาก ${\displaystyle O(\log ^{2}n)}$

ใบรับรองที่สร้างขึ้นนั้นใช้พื้นที่ในการส่งและ ใช้เวลา ในการตรวจสอบ(ซึ่งเป็นจำนวน กำลังสองของเวลา) (ข้อความนี้สมมติว่าค่า B คงที่ ซึ่งเป็นพารามิเตอร์สำคัญในการปรับแต่งในทางปฏิบัติ: ยิ่งค่าB ต่ำลง จะใช้พื้นที่ดิสก์มากขึ้นในการสร้างใบรับรองและใช้เวลาน้อยลงในการตรวจสอบ ในทางปฏิบัติจะใช้พื้นที่หลายกิกะไบต์) ${\displaystyle O(\log n)}$${\displaystyle O(1)}$${\displaystyle O(\log n)}$

มันถูกนำไปใช้กับตัวเลขขนาดใหญ่มากซึ่งการยกกำลังเป็นงานที่มีค่าใช้จ่ายสูง ตัวอย่างเช่น หลักฐานของ Gerbicz-Pietrzak ถูกใช้เพื่อยืนยันการทดสอบความเป็นจำนวนเฉพาะของ Fermat สำหรับ ซึ่งเป็นจำนวนเฉพาะ Mersenneที่พบในปี 2024 ^{[ 9 ]}${\displaystyle 2^{136279841}-1}$

โครงการ ค้นหา Mersenne Prime ของอินเทอร์เน็ตขนาดใหญ่และโครงการที่เกี่ยวข้อง เช่น (ส่วนหนึ่งของ) PrimeGridใช้แผนการ "Gerbicz-Pietrzak" ของ Pavel Atnashev ซึ่งรวมการตรวจสอบข้อผิดพลาดของ Gerbicz สำหรับการยกกำลังแบบโมดูลาร์เข้ากับฟังก์ชันการหน่วงเวลาที่ตรวจสอบได้ของ Pietrzak เพื่อสร้าง "หลักฐาน" ที่ตรวจสอบได้ง่ายของการยกกำลังแบบโมดูลาร์ไปยังกำลังของ^{2m [ 10 ] [ 11 ]}

แผนการตรวจสอบข้อผิดพลาดของ Gerbicz เดิมทีถูกกำหนดไว้สำหรับการทดสอบ Prothแต่ต่อมาได้ขยายไปยังการทดสอบความเป็นจำนวนเฉพาะของ Fermatรูปแบบดั้งเดิมจะตรวจสอบการคำนวณโดยการเพิ่มตัวแปรเพิ่มเติมและค่าคงที่การปรับขนาดL ที่กำหนดเอง ดังนั้นจึงมีความสัมพันธ์เวียนเกิดซึ่งสามารถใช้เพื่ออัปเดต d(t) ทุกๆLรอบของการคูณเลขชี้กำลังสองเท่า นอกจากนี้ยังมีความสัมพันธ์ซึ่งใช้ในการตรวจสอบการคำนวณทุกๆB = L² ^รอบหากไม่ตรงกันจะส่งผลให้มีการย้อนกลับไปยังทูเปิ ล "จุดตรวจสอบ" ที่บันทึกไว้ก่อนหน้า นี้ของ^{[ 12 ]}${\displaystyle u(t)={a^{k}}^{2^{t}}{\pmod {N}}}$${\displaystyle d(t)=\textstyle \prod _{i=0}^{t}u(iL){\pmod {N}}}$${\displaystyle d(t+1)=d(t)\cdot u((t+1)\cdot L){\pmod {N}}}$${\displaystyle d(t+1)=u(0)\cdot d(t)^{2^{L}}{\pmod {N}}}$${\displaystyle (t,u,d)}$

ด้วยการเพิ่มรูปแบบ Pietrzak VDF ^{[ 13 ]}ไคลเอนต์ที่คำนวณจะสร้างไฟล์ "ใบรับรอง" โดยใช้เศษ "จุดตรวจสอบ" ที่บันทึกไว้จากการคำนวณ ส่งผลให้ได้ไฟล์ของ องค์ประกอบต่างๆ ไคลเอนต์จะอัปโหลดใบรับรองไปยังเซิร์ฟเวอร์ จากนั้นเซิร์ฟเวอร์จะกำหนดใบรับรองนั้นให้กับไคลเอนต์ "ผู้ตรวจสอบ" จากนั้นผู้ตรวจสอบจะใช้รูปแบบ Pietrzak เวอร์ชันที่ไม่โต้ตอบเพื่อตรวจสอบผลลัพธ์^{[ 14 ]}${\displaystyle O(\log(m/L))}$

มีการเผยแพร่ การสรุปทั่วไปของแผนการ Pietrzak ไปยังลำดับ Lucasซึ่งมีการตรวจสอบการ คำนวณของ ^{[ 15 ]}${\displaystyle U_{2^{m}}(P,Q){\bmod {n}}}$${\displaystyle V_{2^{m}}(P,Q){\bmod {n}}}$

ข้อจำกัดหลักของ Gerbicz-Pietrzak คือใช้ได้เฉพาะกับการยกกำลังแบบโมดูลาร์ไปยังกำลังของ 2m เท่านั้น^วิธีการ Gerbicz-Li ถูกพัฒนาขึ้นสำหรับPrimeGridเพื่อเอาชนะข้อจำกัดนี้ โดยตรวจสอบการยกกำลังแบบโมดูลาร์จากซ้ายไปขวาไปยังกำลังn ใดๆ ก็ได้ ให้Lเป็นความยาวของการขยายเลขฐานสองของnดังนั้นกระบวนการที่จะตรวจสอบคือการคำนวณโดยใช้ความสัมพันธ์เวียนเกิดต่อไปนี้: ${\displaystyle n=n_{0}2^{0}+n_{1}2^{1}+\dots +n_{L-1}2^{L-1}}$${\displaystyle u_{i}=a^{\lfloor n/2^{i}\rfloor }}$

$${\displaystyle {\begin{aligned}u_{i}={\begin{cases}1&L\leq i\\u_{i+1}^{2}\cdot a^{n_{i}}&{\text{otherwise}}\end{cases}}\end{aligned}}}$$

ดังนั้นจึงมีความสัมพันธ์อยู่เช่นเดียวกับแผนการของ Gerbicz ลูกค้าที่คำนวณจะบันทึกค่าคงที่บางค่าซึ่งเป็นพหุคูณของจากนั้นจะตรวจสอบความเท่าเทียมกันระหว่างและทุกบล็อก โดยเพิ่มพจน์น้ำหนักแบบสุ่มสำหรับความถูกต้องในการพิสูจน์เพื่อความปลอดภัย: ${\displaystyle u_{i}=u_{i+j}^{2^{j}}a^{\left\lfloor {\frac {n}{2^{i}}}\right\rfloor {\bmod {2}}^{j}}}$${\displaystyle u_{0},u_{B},u_{2B},\dots }$${\displaystyle B}$${\displaystyle L}$${\displaystyle u_{iB}}$${\displaystyle u_{(i+1)B}}$${\displaystyle B}$${\displaystyle w_{i}}$

$${\displaystyle {\begin{aligned}\prod _{i=0}u_{iB}^{w_{i}}&{\overset {\text{?}}{=}}\prod _{i=0}u_{(i+1)B}^{w_{i}2^{B}}a^{\left(\left\lfloor {\frac {n}{2^{iB}}}\right\rfloor {\bmod {2}}^{B}\right)w_{i}}\\&=\left(\prod _{i=0}u_{(i+1)B}^{w_{i}}\right)^{2^{B}}a^{\sum \limits _{i=0}\left(\left\lfloor {\frac {n}{2^{iB}}}\right\rfloor {\bmod {2}}^{B}\right)w_{i}}\end{aligned}}}$$

การแฮชยังใช้เพื่อสร้างหลักฐานที่ไม่โต้ตอบสำหรับการใช้งานโดยผู้ดำเนินการ PrimeGrid อีกด้วย^{[ 14 ]}

Pavel Atnashev ได้ขยาย Gerbicz-Li ไปสู่การคำนวณ เทอม ลำดับ Lucas ใดๆ ด้วย[ ^{16 ]}การขยายนี้ใช้ใน "การทดสอบ Morrison" ของเขา ซึ่งเป็นการขยายการทดสอบ LLR ด้วยค่าเริ่มต้น Rödseth ใน^{ซอฟต์แวร์} PrimeGrid "PRST" ^{[ 17 ]}${\displaystyle Q=-1}$

"PRIMES is in P" ^{[ 18 ]}เป็นความก้าวหน้าครั้งสำคัญในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี บทความนี้ตีพิมพ์โดยManindra Agrawal , Nitin SaxenaและNeeraj Kayalในเดือนสิงหาคม พ.ศ. 2545 พิสูจน์ว่าปัญหาที่มีชื่อเสียงในการตรวจสอบความเป็นจำนวนเฉพาะของจำนวนสามารถแก้ไขได้แบบกำหนดในเวลาพหุนาม ผู้เขียนได้รับรางวัล Gödel Prize ประจำปี 2549 และรางวัล Fulkerson Prize ประจำปี 2549 สำหรับผลงานนี้

เนื่องจากการทดสอบความเป็นจำนวนเฉพาะสามารถทำได้แบบกำหนดได้ในเวลาพหุนามโดยใช้การทดสอบความเป็นจำนวนเฉพาะ AKSดังนั้นจำนวนเฉพาะจึงอาจถือได้ว่าเป็นใบรับรองความเป็นจำนวนเฉพาะของตัวมันเอง การทดสอบนี้ใช้เวลา Õ((log n ) ⁶ ) ในทางปฏิบัติ วิธีการตรวจสอบนี้มีค่าใช้จ่ายสูงกว่าการตรวจสอบใบรับรอง Pratt แต่ไม่จำเป็นต้องมีการคำนวณใดๆ เพื่อตรวจสอบใบรับรองนั้นเอง

จากการทดลองอย่างละเอียดถี่ถ้วน เป็นที่ทราบกันว่าการทดสอบความเป็นจำนวนเฉพาะของ Baillie–PSWไม่มีจำนวนเฉพาะเทียมที่ต่ำกว่า 2 ⁶⁴ดังนั้น 2 ⁶⁴จึงเป็นจุดตัดที่คาดว่าจะมีใบรับรองจำนวนเฉพาะสำหรับตัวเลขที่กำหนด^{[ 19 ]}

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

• รูปแบบ Primo สำหรับ ECPP เดิมทีใช้โดยโปรแกรม GUI ของ Linux ที่ชื่อ Primo ^{[ 20 ]}
• รูปแบบ PARI สำหรับ ECPP และ N-1 (Pocklington) ที่ใช้ในPARI/ GP ^{[ 8 ]}

โปรแกรม ECPP ที่รวดเร็ว Cm รองรับการสร้างทั้งรูปแบบ Primo และ PARI โดยใช้การประมวลผลแบบขนาน MPI เพื่อปรับขนาดข้ามคอมพิวเตอร์หลายเครื่อง^{[ 21 ]}และใช้ขั้นตอนวิธี FastECPP ^{[ 4 ]}

GIMPS (PrimeNet) และ PrimeGrid ใช้รูปแบบเฉพาะของตนเองสำหรับใบรับรองการยกกำลังแบบ Gerbicz ซึ่งไม่เป็นที่ยอมรับอย่างกว้างขวางในโปรแกรมหรือโครงการอื่นๆ

• Mathworld: ใบรับรองความเป็นจำนวนเฉพาะ
• Mathworld: ประกาศนียบัตร Pratt
• Mathworld: ประกาศนียบัตร Atkin-Goldwasser-Kilian-Morain
• คำศัพท์สำคัญ: ใบรับรองความเป็นดั้งเดิม
• Vašek Chvátal . บันทึกการบรรยายเรื่องการพิสูจน์ความเป็นจำนวนเฉพาะของ Pratt . ภาควิชาวิทยาการคอมพิวเตอร์ มหาวิทยาลัยรัตเกอร์ส. เวอร์ชัน PDF ที่มหาวิทยาลัยคอนคอร์เดีย