二次残差問題

計算数論における二次剰余問題（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}}}$ 。

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

上で示した平方剰余問題で許容される は、まさにと の場合に対応する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 ]}や、恒等式に基づくコックス方式にも応用されている。

参照

• 残留物の増加問題

参考文献

1. カリスキ、バート (2011). 「二次残差問題」.暗号とセキュリティ百科事典. p. 1003. doi : 10.1007/978-1-4419-5906-5_429 . ISBN 978-1-4419-5905-8。
2. Adleman, L. (1980). 「素数と合成数の区別について」.第21回IEEEコンピュータサイエンス基礎シンポジウム (FOCS) 議事録, シラキュース, ニューヨーク州. pp.  387– 408. doi : 10.1109/SFCS.1980.28 . ISSN 0272-5428 . 
3. S. Goldwasser, S. Micali (1982). 「確率的暗号化と、部分情報を秘密に保ちながらメンタルポーカーをプレイする方法」第14回ACMコンピューティング理論シンポジウム - STOC '82 議事録. pp.  365– 377. doi : 10.1145/800070.802212 . ISBN 0897910702. S2CID  10316867 .
4. S. Goldwasser, S. Micali (1984). 「確率的暗号化」 . Journal of Computer and System Sciences . 28 (2): 270– 299. doi : 10.1016/0022-0000(84)90070-9 .