二次残差問題

計算数論における二次剰余問題（QRP [ ^1]）は、整数および が与えられたときに、 を法とする二次剰余であるかどうかを判断する問題である。ここで、2つの未知の素数 および について、およびは明らかに二次剰余ではない数である（以下を参照）。 ${\displaystyle a}$${\displaystyle N}$${\displaystyle a}$ ${\displaystyle N}$${\displaystyle N=p_{1}p_{2}}$ ${\displaystyle p_{1}}$${\displaystyle p_{2}}$${\displaystyle a}$

この問題は、1801 年にガウスが著書『算術論』で初めて説明しました。この問題は計算上困難であると考えられています。いくつかの暗号化手法は、この問題の困難性に依存しています。§ 応用を参照してください。

二次残差問題に対する効率的なアルゴリズムは、未知の因数分解の合成が2つの素数の積か3つの素数の積かを決定するなど、他の数論問題に対する効率的なアルゴリズムを直ちに意味します。^[2] ${\displaystyle N}$

整数と が与えられたとき、を法とする平方剰余とは、 となる整数が存在するときである。 ${\displaystyle a}$${\displaystyle T}$${\displaystyle a}$${\displaystyle T}$${\displaystyle b}$

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

それ以外の場合は、2次非剰余であると言います。が素数の場合、慣例的にルジャンドル記号を使用します。 ${\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}$

ユークリッドの互除法に似た方法で二次の相互法則を使用して計算するのは簡単です。ルジャンドル記号を参照してください。

ここで、 と が2 つの異なる未知の素数である、いくつかの与えられた を考えます。 が を法とする平方剰余である場合、かつ がとおよび の両方を法とする平方剰余である場合に限ります。 ${\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 )}}$

上記の平方剰余問題で許される は、および の場合に対応する 2 つの部分を正確に構成します。したがって、可能性のある のちょうど半分が平方剰余であり、残りは平方剰余ではありません。 ${\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 疑似乱数生成器の安全性の基礎となっている。また、この問題は公開鍵 ゴールドワッサー・ミカリ暗号システム[ ^{3] [4]}や同一性に基づく コックス方式にも応用されている。

• 残留物問題の増加