ในด้านการเข้ารหัสลับระบบการเข้ารหัสลับแบบกุญแจสาธารณะส่วนใหญ่ตั้งอยู่บนปัญหาที่เชื่อกันว่าไม่สามารถแก้ไขได้ปัญหาเศษเหลือที่สูงกว่า (เรียกอีกอย่างว่าปัญหาเศษเหลือลำดับที่n ^{[ 1 ]} ) เป็นหนึ่งในปัญหาดังกล่าว ปัญหานี้แก้ไขได้ง่าย กว่า การแยกตัวประกอบจำนวนเต็มดังนั้นสมมติฐานที่ว่าปัญหานี้แก้ไขได้ยากจึงแข็งแกร่งกว่าสมมติฐานที่ว่าการแยกตัวประกอบจำนวนเต็มนั้นยาก

ถ้าnเป็นจำนวนเต็มแล้วจำนวนเต็มมอดูล nจะก่อให้เกิดริงถ้าn = pqโดยที่pและqเป็นจำนวนเฉพาะแล้วทฤษฎีบทเศษเหลือของจีนบอกเราว่า

${\displaystyle \mathbb {Z} /n\mathbb {Z} \simeq \mathbb {Z} /p\mathbb {Z} \times \mathbb {Z} /q\mathbb {Z} }$

หน่วยต่างๆในริงใดๆ จะรวม กันเป็น กลุ่มภายใต้การคูณ และกลุ่มของหน่วยในริงนั้นโดยทั่วไปจะใช้สัญลักษณ์แทน ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

จากไอโซมอร์ฟิซึมของวงแหวนข้างต้น เราจะได้ว่า

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\simeq (\mathbb {Z} /p\mathbb {Z} )^{\times }\times (\mathbb {Z} /q\mathbb {Z} )^{\times }}$

เป็นการสมสัณฐานของกลุ่มเนื่องจากถือว่าpและq เป็นจำนวนเฉพาะ ดังนั้นกลุ่ม และจึงเป็นกลุ่มวัฏจักรที่มีอันดับp −1 และq −1 ตามลำดับ ถ้าdเป็นตัวหารของp −1 แล้วเซตของ กำลังที่ dในจะเป็นกลุ่มย่อยที่มีดัชนีdถ้า gcd( d , q −1) = 1 แล้ว สมาชิก ทุกตัวในจะเป็น กำลังที่ dดังนั้นเซตของ กำลังที่ dในจึงเป็นกลุ่มย่อยที่มีดัชนีd ด้วย โดยทั่วไป ถ้า gcd( d , q −1) = gแล้วจะมี กำลังที่ d จำนวน ( q −1)/ gตัวในดังนั้นเซตของ กำลังที่ dในจึงมีดัชนีdgโดยทั่วไปจะพบเห็นกรณีนี้เมื่อd = 2 และเรากำลังพิจารณากลุ่มย่อยของเศษกำลังสองซึ่งเป็นที่ทราบกันดีว่าหนึ่งในสี่ของสมาชิกในกลุ่มย่อยนี้เป็นเศษกำลังสอง (เมื่อnเป็นผลคูณของจำนวนเฉพาะสองตัว ดังเช่นในกรณีนี้) ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

ประเด็นสำคัญคือ สำหรับตัวหารd ใดๆ ของp −1 (หรือq −1) เซตของ กำลังที่ dจะก่อตัวเป็นกลุ่มย่อยของ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}$

กำหนดให้จำนวนเต็มn = pqโดยที่pและqไม่ทราบค่า จำนวนเต็มdที่d หาร p −1 ลงตัวและจำนวนเต็มx < nเป็นไปไม่ได้ที่จะตรวจสอบว่าxเป็น กำลังที่ d (หรือเทียบเท่ากับ เศษที่ d ) มอดูลn หรือ ไม่

โปรดสังเกตว่า ถ้า ทราบ ค่า pและqแล้ว จะสามารถระบุได้ง่ายว่าxเป็นเศษเหลือลำดับที่d ของโมดูลัส n หรือไม่ เพราะxจะเป็นเศษเหลือลำดับที่d ของโมดูลัส p ก็ต่อเมื่อ

${\displaystyle x^{(p-1)/d}\equiv 1{\pmod {p}}}$

เมื่อd = 2 ปัญหา นี้เรียกว่าปัญหาเศษเหลือกำลังสอง

ความปลอดภัยเชิงความหมายของระบบการเข้ารหัส Benalohและระบบการเข้ารหัส Naccache–Sternขึ้นอยู่กับความยากลำบากในการแก้ปัญหาดังกล่าว