ปัญหาเศษเหลือกำลังสอง ( QRP ^{[ 1 ]} ) ในทฤษฎีจำนวนเชิงคำนวณคือการตัดสินใจว่าจำนวนเต็มที่ กำหนด และเป็นเศษเหลือกำลังสองมอดูลหรือไม่ ในที่นี้สำหรับจำนวนเฉพาะ ที่ไม่ทราบค่าสองตัว และและอยู่ในกลุ่มจำนวนที่ไม่ใช่เศษเหลือกำลังสองอย่างชัดเจน (ดูด้านล่าง) ${\displaystyle a}$${\displaystyle N}$${\displaystyle a}$${\displaystyle N}$${\displaystyle N=p_{1}p_{2}}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle a}$

ปัญหาดังกล่าวได้รับการอธิบายครั้งแรกโดยเกาส์ในหนังสือ Disquisitiones Arithmeticae ของเขา ในปี ค.ศ. 1801 เชื่อกันว่าปัญหานี้มีความยากในการคำนวณวิธีการเข้ารหัสหลายวิธีอาศัยความยากของปัญหา นี้ ดูหัวข้อ § การประยุกต์ใช้

อัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหาเศษเหลือกำลังสองจะนำไปสู่อัลกอริทึมที่มีประสิทธิภาพสำหรับ ปัญหา ทฤษฎีจำนวน อื่นๆ เช่น การตัดสินใจว่าจำนวนประกอบ ของการแยกตัวประกอบที่ไม่ทราบผลคูณของจำนวนเฉพาะ 2 หรือ 3 ตัว^{[ 2 ]}${\displaystyle N}$

กำหนดให้จำนวนเต็มและจะเรียกว่าเป็นเศษเหลือกำลังสองมอดูลถ้ามีจำนวนเต็มอยู่จริง ซึ่งทำให้ ${\displaystyle a}$${\displaystyle T}$${\displaystyle a}$${\displaystyle T}$${\displaystyle b}$

${\displaystyle a\equiv b^{2}{\pmod {T}}}$.

มิฉะนั้นเราจะเรียกว่าเป็นเศษเหลือที่ไม่เป็นกำลังสอง เมื่อเป็นจำนวนเฉพาะ มักจะใช้สัญลักษณ์เลอจองเดอร์ : ${\displaystyle T=p}$

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{ ถ้า }}a{\text{ เป็นเศษเหลือกำลังสองมอดูล }}p{\text{ และ }}a\not \equiv 0{\pmod {p}},\\-1&{\text{ ถ้า }}a{\text{ เป็นเศษเหลือที่ไม่ใช่กำลังสองมอดูล }}p,\\0&{\text{ ถ้า }}a\equiv 0{\pmod {p}}.\end{cases}}}$

นี่คืออักขระการคูณซึ่งหมายความว่าสำหรับค่า บางส่วนเท่านั้น และสำหรับค่าที่เหลือ ${\displaystyle {\big (}{\tfrac {a}{p}}{\big )}=1}$${\displaystyle (p-1)/2}$${\displaystyle 1,\ldots ,p-1}$${\displaystyle -1}$

สามารถคำนวณได้ง่ายโดยใช้กฎการผกผันกำลังสองในลักษณะที่คล้ายกับอัลกอริทึมของยุคลิดดูสัญลักษณ์เลอจองเดอร์

พิจารณาค่าที่กำหนดให้บางค่าโดยที่และเป็นจำนวนเฉพาะที่ไม่ทราบค่าสองจำนวนที่แตกต่างกัน ค่าที่กำหนดให้ จะ เป็น เศษเหลือกำลังสองมอดูลัส ก็ต่อเมื่อเป็นเศษเหลือกำลังสองมอดูลัส ทั้งและและ${\displaystyle N=p_{1}p_{2}}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle a}$${\displaystyle N}$${\displaystyle a}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle \gcd(a,N)=1}$

เนื่องจากเราไม่ทราบค่าของหรือเราจึงไม่สามารถคำนวณค่าและ ได้อย่างไรก็ตาม การคำนวณผลคูณของค่าทั้งสองนั้นทำได้ง่าย ซึ่งเรียกว่าสัญลักษณ์จาโคบี : ${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}}$${\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}$

${\displaystyle \left({\frac {a}{N}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)}$

นอกจากนี้ยังสามารถคำนวณได้อย่างมีประสิทธิภาพโดยใช้กฎการผกผันกำลังสองสำหรับสัญลักษณ์จาโคบี

อย่างไรก็ตามเราไม่สามารถบอกได้ในทุกกรณีว่าเป็นเศษเหลือกำลังสองมอดูลหรือไม่! กล่าวให้แม่นยำยิ่งขึ้น ถ้าแล้วจะต้องเป็นเศษเหลือที่ไม่ใช่กำลังสองมอดูลหรือ อย่างใดอย่าง หนึ่ง ซึ่งในกรณีนี้เราก็เสร็จสิ้นแล้ว แต่ถ้าแล้วจะเป็นกรณีที่เป็นเศษเหลือกำลังสองมอดูลทั้งและหรือเป็นเศษเหลือที่ไม่ใช่กำลังสองมอดูลทั้งและเราไม่สามารถแยกแยะกรณีเหล่านี้ได้จากการรู้เพียงแค่ว่า ${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}}$${\displaystyle a}$${\displaystyle N}$${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=-1}$${\displaystyle a}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$${\displaystyle a}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$

ซึ่งนำไปสู่การกำหนดปัญหาเศษเหลือกำลังสองอย่างแม่นยำ:

โจทย์: กำหนดให้จำนวนเต็มและโดยที่และเป็นจำนวนเฉพาะที่ไม่ทราบค่าและแตกต่างกัน และ โดยที่จงพิจารณาว่าเป็นเศษเหลือกำลังสองมอดูลัสหรือไม่ ${\displaystyle a}$${\displaystyle N=p_{1}p_{2}}$${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$${\displaystyle a}$${\displaystyle N}$

ถ้าสุ่มเลือก จำนวนเต็ม อย่างสม่ำเสมอจากจำนวนเต็มโดยที่ จะเป็นเศษเหลือกำลังสองหรือไม่ใช่เศษเหลือกำลังสองมอดูลัส มากกว่ากัน? ${\displaystyle a}$${\displaystyle 0,\ldots ,N-1}$${\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}$${\displaystyle a}$${\displaystyle N}$

ดังที่กล่าวไว้ก่อนหน้านี้ สำหรับครึ่งหนึ่งของตัวเลือกของแล้วและสำหรับส่วนที่เหลือเราจะได้โดยนัยเดียวกันนี้ก็ใช้ได้กับครึ่งหนึ่งของตัวเลือกของเช่นกัน ในทำนองเดียวกันสำหรับจากพีชคณิตพื้นฐาน จะได้ว่า นี้สามารถแบ่งออกเป็น 4 ส่วนที่มีขนาดเท่ากัน ขึ้นอยู่กับเครื่องหมายของ และ${\displaystyle a\in \{1,\ldots ,p_{1}-1\}}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=1}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=-1}$${\displaystyle a\in \{1,\ldots ,N-1\}\setminus p_{1}\mathbb {Z} }$${\displaystyle p_{2}}$${\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{\times }}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}}$${\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}$

ในปัญหาเศษเหลือกำลังสอง ที่อนุญาตดังที่กล่าวมาข้างต้นนั้น ประกอบด้วยส่วนที่สอดคล้องกับกรณีและ เท่านั้น ดังนั้น ครึ่งหนึ่งของค่าที่เป็นไปได้ทั้งหมดจึงเป็นเศษเหลือกำลังสอง และส่วนที่เหลือไม่ใช่ ${\displaystyle a}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=1}$${\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=-1}$${\displaystyle a}$

ความยากในการแก้ปัญหาเศษเหลือกำลังสองเป็นพื้นฐานสำหรับความปลอดภัยของเครื่องกำเนิดเลขสุ่มเทียมBlum Blum Shub นอกจากนี้ยังให้ระบบการเข้ารหัส Goldwasser–Micali กุญแจสาธารณะ[ ^{3 ] [ 4 ] เช่น}เดียวกับแผนการ Cocks ที่อิงตามเอกลักษณ์

• ปัญหาปริมาณสารตกค้างที่สูงขึ้น