การทดสอบความเป็นจำนวนเฉพาะของ Solovay–Strassenซึ่งพัฒนาโดยRobert M. SolovayและVolker Strassenในปี 1977 เป็นการทดสอบความเป็นจำนวนเฉพาะเชิงความน่าจะเป็น เพื่อตรวจสอบว่าจำนวนนั้นเป็นจำนวนประกอบหรือน่าจะเป็นจำนวนเฉพาะหรือไม่ แนวคิดเบื้องหลังการทดสอบนี้ถูกค้นพบโดย MM Artjuhov ในปี 1967 ^{[ 1 ]} (ดูทฤษฎีบท E ในเอกสาร) การทดสอบนี้ส่วนใหญ่ถูกแทนที่ด้วยการทดสอบความเป็นจำนวนเฉพาะของ Baillie–PSWและการทดสอบความเป็นจำนวนเฉพาะของ Miller–Rabin แล้วแต่มีความสำคัญทางประวัติศาสตร์อย่างมากในการแสดงให้เห็นถึงความเป็นไปได้ในทางปฏิบัติของระบบ การเข้ารหัสRSA

ออยเลอร์พิสูจน์^{[ 2 ]}ว่าสำหรับจำนวนเฉพาะคี่p ใดๆ และจำนวนเต็มa ใด ๆ

${\displaystyle a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right){\pmod {p}}}$

สัญลักษณ์เลอจองเดอร์อยู่ที่ไหนสัญลักษณ์จาโคบีเป็นการขยายความของสัญลักษณ์เลอจองเดอร์ไปสู่​​โดยที่nสามารถเป็นจำนวนเต็มคี่ใดๆ ก็ได้ สัญลักษณ์จาโคบีสามารถคำนวณได้ในเวลาO ((log  n )²) โดยใช้การขยายความของ กฎการผกผันกำลังสอง ของจาโค บี ${\displaystyle \left({\tfrac {a}{p}}\right)}$${\displaystyle \left({\tfrac {a}{n}}\right)}$

เมื่อกำหนดจำนวนคี่nเราสามารถพิจารณาได้ว่าความสอดคล้องกันนั้นเกิดขึ้นหรือไม่

${\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}$

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

สำหรับจำนวนประกอบคี่n ทุกจำนวน อย่างน้อยครึ่งหนึ่งของฐานทั้งหมด

${\displaystyle a\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$

พยาน (ออยเลอร์) คือเซตของผู้โกหกแบบออยเลอร์ ซึ่งเป็นกลุ่มย่อยที่แท้จริงของตัวอย่างเช่น สำหรับเซตของผู้โกหกแบบออยเลอร์มีอันดับ 8 และและมีอันดับ 48 ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$${\displaystyle n=65}$${\displaystyle =\{1,8,14,18,47,51,57,64\}}$${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$

สิ่งนี้แตกต่างจากการทดสอบความเป็นจำนวนเฉพาะของแฟร์มาต์ซึ่งสัดส่วนของพยานอาจมีน้อยกว่ามาก ดังนั้นจึงไม่มีจำนวนประกอบ (คี่) nที่ไม่มีพยานจำนวนมาก ซึ่งแตกต่างจากกรณีของจำนวนคาร์ไมเคิลสำหรับการทดสอบของแฟร์มาต์

สมมติว่าเราต้องการตรวจสอบว่าn = 221เป็นจำนวนเฉพาะหรือไม่ เราเขียนว่า ( n −1)/2=110

เราสุ่มเลือกค่าa (มากกว่า 1 และน้อยกว่าn ): 47. โดยใช้วิธีที่มีประสิทธิภาพในการยกกำลังจำนวน (mod n ) เช่นการยกกำลังเลขฐานสองเราคำนวณได้ดังนี้:

• a ^{( n −1)/2}ม็อดn = 47 ¹¹⁰ม็อด 221 = −1 ม็อด 221
• ${\displaystyle \left({\tfrac {a}{n}}\right){\bmod {n}}=\left({\tfrac {47}{221}}\right){\bmod {2}}21=-1{\bmod {2}}21}$

สิ่งนี้แสดงให้เห็นว่า 221 เป็นจำนวนเฉพาะ หรือ 47 เป็นตัวโกหกของออยเลอร์สำหรับ 221 เราลองสุ่มค่าa อีกครั้ง คราวนี้เลือกa = 2 :

• a ^{( n −1)/2}ม็อดn = 2 ¹¹⁰ม็อด 221 = 30 ม็อด 221
• ${\displaystyle \left({\tfrac {a}{n}}\right){\bmod {n}}=\left({\tfrac {2}{221}}\right){\bmod {2}}21=-1{\bmod {2}}21}$.

ดังนั้น 2 จึงเป็นพยานออยเลอร์สำหรับความเป็นจำนวนประกอบของ 221 และ 47 แท้จริงแล้วเป็นตัวโกหกของออยเลอร์ โปรดทราบว่าสิ่งนี้ไม่ได้บอกอะไรเราเกี่ยวกับตัวประกอบเฉพาะของ 221 ซึ่งแท้จริงแล้วคือ 13 และ 17

สามารถเขียนอัลกอริทึมในรูปแบบรหัสเทียมได้ดังนี้:

อินพุต : nค่าที่ใช้ทดสอบความเป็นจำนวนเฉพาะ kพารามิเตอร์ที่กำหนดความแม่นยำของการทดสอบ เอาต์พุต : จำนวนประกอบถ้าnเป็นจำนวนประกอบ มิเช่นนั้นอาจเป็นจำนวนเฉพาะทำซ้ำkครั้ง: เลือกค่าaแบบสุ่มในช่วง [2, n − 1] ถ้าx  = 0 หรือส่งคืนจำนวนประกอบแล้วส่งคืนจำนวนเฉพาะที่น่าจะเป็นไปได้${\displaystyle x\gets \left({\tfrac {a}{n}}\right)}$${\displaystyle a^{(n-1)/2}\not \equiv x{\pmod {n}}}$

เมื่อใช้อัลกอริธึมที่รวดเร็วสำหรับการยกกำลังแบบโมดูลาร์เวลาในการทำงานของอัลกอริธึมนี้คือ O( k · log ³ⁿ )โดยที่kคือจำนวนค่าที่แตกต่างกันของaที่ถูกทดสอบ

เป็นไปได้ที่อัลกอริทึมจะให้คำตอบที่ไม่ถูกต้อง หากอินพุต "n" เป็นจำนวนเฉพาะจริง ๆ ผลลัพธ์ที่ได้จะเป็น "น่าจะเป็นจำนวนเฉพาะ" เสมออย่างถูกต้อง

เมื่อnเป็นจำนวนคี่และเป็นจำนวนประกอบ อย่างน้อยครึ่งหนึ่งของa ทั้งหมด ที่มี gcd( a , n ) = 1 จะเป็นพยานออยเลอร์ เราสามารถพิสูจน์ได้ดังนี้: ให้ { a₁ a₂ , ..., }เป็นผู้โกหกออยเลอร์ และaᵢ เป็นพยานออยเลอร์ ดังนั้น สำหรับi  = 1, 2, ... m :

${\displaystyle (a\cdot a_{i})^{(n-1)/2}=a^{(n-1)/2}\cdot a_{i}^{(n-1)/2}=a^{(n-1)/2}\cdot \left({\frac {a_{i}}{n}}\right)\not \equiv \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right){\pmod {n}}.}$

เนื่องจากข้อเท็จจริงต่อไปนี้เป็นจริง:

${\displaystyle \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right)=\left({\frac {a\cdot a_{i}}{n}}\right),}$

ตอนนี้เรารู้แล้วว่า

${\displaystyle (a\cdot a_{i})^{(n-1)/2}\not \equiv \left({\frac {a\cdot a_{i}}{n}}\right){\pmod {n}}.}$

สิ่งนี้แสดงให้เห็นว่าa แต่ละตัว ให้ค่าa · a ซึ่งเป็นพยานออยเลอร์ด้วย ดังนั้น ผู้โกหกออยเลอร์แต่ละคนจึงให้พยานออยเลอร์ และจำนวนพยานออยเลอร์จึงมากกว่าหรือเท่ากับจำนวนผู้โกหกออยเลอร์ ดังนั้น เมื่อnเป็นจำนวนประกอบ อย่างน้อยครึ่งหนึ่งของa ทั้งหมด ที่มี gcd( a , n ) = 1 จะเป็นพยานออยเลอร์

ดังนั้น ความน่าจะเป็นของความล้มเหลวจึงมีค่าสูงสุดเพียง 2 ^{− k} (เปรียบเทียบกับความน่าจะเป็นของความล้มเหลวสำหรับการทดสอบความเป็นจำนวนเฉพาะของมิลเลอร์-ราบินซึ่งมีค่าสูงสุดเพียง 4 ^{− k} )

เพื่อวัตถุประสงค์ของการเข้ารหัส ยิ่งเราทดสอบ ฐานa มากเท่าไร กล่าวคือ หากเราเลือกค่าk ที่มีขนาดใหญ่เพียงพอ ความแม่นยำของการทดสอบก็จะยิ่งดีขึ้นเท่านั้น ดังนั้นโอกาสที่อัลกอริทึมจะล้มเหลวในลักษณะนี้จึงน้อยมากจนจำนวนเฉพาะ (เทียม) ถูกนำมาใช้ในทางปฏิบัติในแอปพลิเคชันการเข้ารหัส แต่สำหรับแอปพลิเคชันที่จำเป็นต้องมีจำนวนเฉพาะควรใช้ การทดสอบเช่น ECPPหรือการทดสอบความเป็นจำนวนเฉพาะของ Pocklington ^{[ 3 ]} ซึ่ง พิสูจน์ความเป็นจำนวนเฉพาะ

ขอบเขต 1/2 ของความน่าจะเป็นของข้อผิดพลาดในรอบเดียวของการทดสอบ Solovay–Strassen นั้นใช้ได้กับค่าอินพุตn ใดๆ แต่ค่าnที่ทำให้ขอบเขตนี้เป็นจริง (โดยประมาณ) นั้นหายากมาก โดยเฉลี่ยแล้ว ความน่าจะเป็นของข้อผิดพลาดของอัลกอริทึมนั้นน้อยกว่ามาก คือ น้อยกว่า

${\displaystyle 2^{-k}\exp \left(-(1+o(1)){\frac {\log x\,\log \log \log x}{\log \log x}}\right)}$

สำหรับkรอบของการทดสอบ ใช้กับ n ≤ x ที่สุ่มอย่างสม่ำเสมอ[ 4 ] [ ^{5 ] ขอบเขตเดียวกันนี้ยัง}ใช้กับปัญหาที่เกี่ยวข้องของความน่าจะเป็นแบบมีเงื่อนไขของnที่เป็นจำนวนประกอบสำหรับจำนวนสุ่มn ≤ xซึ่งได้รับการประกาศว่าเป็นจำนวนเฉพาะในkรอบของการทดสอบ

อัลกอริทึม Solovay–Strassen แสดงให้เห็นว่าปัญหาการตัดสินใจ^COMPOSITEอยู่ในระดับความซับซ้อนRP [ ^{6 ]}

• Solovay, Robert M.; Strassen, Volker (1977). "การทดสอบ Monte-Carlo อย่างรวดเร็วสำหรับความเป็นจำนวนเฉพาะ" SIAM Journal on Computing . 6 (1): 84– 85. doi : 10.1137/0206006 .ดูเพิ่มเติมที่Solovay, Robert M.; Strassen, Volker (1978). "Erratum: A fast Monte-Carlo test for primality". SIAM Journal on Computing . 7 (1): 118. doi : 10.1137/0207009 .
• Dietzfelbinger, Martin (2004-06-29). "การทดสอบความเป็นจำนวนเฉพาะในเวลาพหุนาม จากอัลกอริทึมแบบสุ่มไปจนถึง "จำนวนเฉพาะอยู่ใน P"" บันทึกการบรรยายในสาขาวิทยาการคอมพิวเตอร์เล่มที่ 3000 สำนักพิมพ์สปริงเกอร์ISBN 978-3-540-40344-9.

• การนำการทดสอบความเป็นจำนวนเฉพาะของ Solovay–Strassen มา ใช้ใน Maple