Quadratic residuosity problem とは

計算数論における二次の残差問題は、整数 a {\displaystyle a} N {\displaystyle N} を与え、 a {\displaystyle a} が2次の剰余であるかどうかを決定することである。 2つの未知の素数 p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} a {\displaystyle a} a {\displaystyle a} は明らかに2次の非残差ではない数の中にあります(下記参照)。
この問題は1801年にGaussによってDisquisitiones Arithmeticaeに最初に記述された。この問題は計算上困難であると考えられている。いくつかの暗号化方法は、その硬度に依存しています。アプリケーションを参照してください。
二次残留問題の効率的なアルゴリズムは、未知の因子分解の複合 N {\displaystyle N} が2または3の素数の積であるかどうかを決定するなど、他の数論的問題に対する効率的なアルゴリズムを即座に意味する。