Problem in computational number theory
計算数論における 二次剰余問題 （ QRP [ 1] ）は、 整数 と が与えられたとき、 を法とする二次剰余かどう か を 判定する 問題である 。ここでは、2つの未知の 素数 と について 、 と は 明らかに二次剰余ではない数である（下記参照）。 a {\displaystyle a} N {\displaystyle N} a {\displaystyle a} N {\displaystyle N} N = p 1 p 2 {\displaystyle N=p_{1}p_{2}} p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} a {\displaystyle a}
この問題は、1801年に ガウスが 著書『算術論』 で 初めて記述しました。この問題は 計算的に困難 であると考えられています。いくつかの暗号手法は、この問題の計算 困難性に依存しています 。 「応用」の項を参照してください。
二次剰余問題に対する 効率的な アルゴリズムは、未知の因数分解の 合成数 が2つの素数の積か3つの素数の積かを決定するなど、他の 数論的 問題に対する効率的なアルゴリズムを直ちに意味する。 [2] N {\displaystyle N}
整数 と が与えられたとき 、を法とする 平方剰余 とは、 となる 整数が存在するとき である。 a {\displaystyle a} T {\displaystyle T} a {\displaystyle a} T {\displaystyle T} b {\displaystyle b}
a ≡ b 2 ( mod T ) {\displaystyle a\equiv b^{2}{\pmod {T}}} 。 それ以外の場合、それは二次非剰余数であると言います。 が素数の場合、慣例的に ルジャンドル記号 を 使用します。 T = p {\displaystyle T=p}
( a p ) = { 1 if a is a quadratic residue modulo p and a ≢ 0 ( mod p ) , − 1 if a is a quadratic non-residue modulo p , 0 if a ≡ 0 ( mod p ) . {\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{ if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{ if }}a{\text{ is a quadratic non-residue modulo }}p,\\0&{\text{ if }}a\equiv 0{\pmod {p}}.\end{cases}}} これは、 値の ちょうど に対して 、 残りに対して で
あること を意味する 乗法文字です。 ( a p ) = 1 {\displaystyle {\big (}{\tfrac {a}{p}}{\big )}=1} ( p − 1 ) / 2 {\displaystyle (p-1)/2} 1 , … , p − 1 {\displaystyle 1,\ldots ,p-1} − 1 {\displaystyle -1}
ユークリッドの互除法 に似た方法で 二次の相互法則 を使用して計算するのは簡単です 。 ルジャンドル記号を 参照してください。
ここで 、 と が異なる未知の素数である、 いくつかの与えられた素数について考えます 。 が を法とする 平方剰余である 場合、 かつが と と の 両方を法とする平方剰余である場合に限ります 。 N = p 1 p 2 {\displaystyle N=p_{1}p_{2}} p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} a {\displaystyle a} N {\displaystyle N} a {\displaystyle a} p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} gcd ( a , N ) = 1 {\displaystyle \gcd(a,N)=1}
または がわからないため 、 とを計算することはできません 。しかし、それらの積は簡単に計算できます。これは ヤコビ記号 として知られています。 p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} ( a p 1 ) {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}} ( a p 2 ) {\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}
( a N ) = ( a p 1 ) ( a p 2 ) {\displaystyle \left({\frac {a}{N}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)} これも、ヤコビ記号の 二次相互法則 を使用して 効率的に計算できます 。
しかし、 は、 を法とする平方剰余かどうか を常に判断できるわけではありません。 より正確に言うと、 の場合、 は必ず またはを法とする 平方剰余ではないため 、その場合は処理は完了です。しかし、 の場合、 は と の 両方を法とする平方剰余 であるか、 と の両方を法とする平方剰余ではないため、どちらかに なり ます 。 であることを知っているだけでは、これらの場合を区別することはできません 。 ( a N ) {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}} a {\displaystyle a} N {\displaystyle N} ( a N ) = − 1 {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=-1} a {\displaystyle a} p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} ( a N ) = 1 {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1} a {\displaystyle a} p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} ( a N ) = 1 {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1}
これにより、平方剰余問題の正確な定式化が導かれます。
問題: 整数 およびが与えられ 、 および が 異なる未知の素数である場合、 が 法として平方剰余であるかどうか を判断します 。 a {\displaystyle a} N = p 1 p 2 {\displaystyle N=p_{1}p_{2}} p 1 {\displaystyle p_{1}} p 2 {\displaystyle p_{2}} ( a N ) = 1 {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1} a {\displaystyle a} N {\displaystyle N}
残留物の分布 が となる 整数から 一様にランダムに 抽出される 場合 、は を法 とする平方剰余か平方非剰余であることが多いでしょうか ? a {\displaystyle a} 0 , … , N − 1 {\displaystyle 0,\ldots ,N-1} ( a N ) = 1 {\displaystyle {\big (}{\tfrac {a}{N}}{\big )}=1} a {\displaystyle a} N {\displaystyle N}
前述のように、 の選択肢のちょうど半分に対して が成り立ち 、 残りに対して が成り立ちます 。拡張により、 の選択肢の半分に対してもこれが成り立ちます 。 についても同様です。基本的な代数から、 と の符号に応じて、 これが等しい大きさの 4 つの部分に分割されることがわかります 。 a ∈ { 1 , … , p 1 − 1 } {\displaystyle a\in \{1,\ldots ,p_{1}-1\}} ( a p 1 ) = 1 {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=1} ( a p 1 ) = − 1 {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}=-1} a ∈ { 1 , … , N − 1 } ∖ p 1 Z {\displaystyle a\in \{1,\ldots ,N-1\}\setminus p_{1}\mathbb {Z} } p 2 {\displaystyle p_{2}} ( Z / N Z ) × {\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{\times }} ( a p 1 ) {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}} ( a p 2 ) {\displaystyle {\big (}{\tfrac {a}{p_{2}}}{\big )}}
上で示した平方剰余問題で許容される は、まさに と の 場合に対応する2つの部分から構成されます 。したがって、可能性のある のちょうど半分は 平方剰余であり、残りは平方剰余ではありません。 a {\displaystyle a} ( a p 1 ) = ( a p 2 ) = 1 {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=1} ( a p 1 ) = ( a p 2 ) = − 1 {\displaystyle {\big (}{\tfrac {a}{p_{1}}}{\big )}={\big (}{\tfrac {a}{p_{2}}}{\big )}=-1} a {\displaystyle a}
アプリケーション 二次剰余問題の扱いにくさは、 Blum Blum Shub 擬似乱数生成器 の安全性の基盤となっている 。また、この性質は 公開鍵 ゴールドワッサー・ミカリ暗号システム [3] [4] や、 恒等式に基づく コックス方式 にも応用されている 。
参照
参考文献 ^ カリスキ、バート (2011). 「二次残差問題」. 暗号とセキュリティ百科事典 . p. 1003. doi : 10.1007/978-1-4419-5906-5_429 . ISBN 978-1-4419-5905-8 。 ^ Adleman, L. (1980). 「素数と合成数の区別について」. 第21回IEEEコンピュータサイエンス基礎シンポジウム (FOCS) 議事録, シラキュース, ニューヨーク州 . pp. 387– 408. doi :10.1109/SFCS.1980.28. ISSN 0272-5428. ^ S. Goldwasser, S. Micali (1982). 「確率的暗号化と、部分的な情報を秘密に保ちながらメンタルポーカーをプレイする方法」 第14回ACMコンピューティング理論シンポジウム - STOC '82 議事録 . pp. 365– 377. doi :10.1145/800070.802212. ISBN 0897910702 . S2CID 10316867。 ^ S. Goldwasser, S. Micali (1984). 「確率的暗号化」. Journal of Computer and System Sciences . 28 (2): 270– 299. doi : 10.1016/0022-0000(84)90070-9 .
