ゼロ知識証明の勉強をしているのですが…

質問

ゼロ知識証明の勉強をしているのですが…
途中で
1.m が合成数の時、m を素因数分解できれば任意の y の mod m での平方根を簡単に求めることができる。逆に任意の y に対する mod m での平方根が求まるならば、m を簡単に素因数分解できる。
2.m を素因数分解できれば、任意の y に対し mod m での平方剰余性を簡単に判定できる。
とあったのですが、計算方法が解らないので、納得が出来ません。
具体的な計算方法が解る方がいらっしゃいましたら、ご教授願います。

回答No.1

yoikagari · ベストアンサー

「yはmod mでの平方剰余である」を「yはmod m で平方数であること」ということにする。

http://okwave.jp/qa/q6046417.html
1の「m が合成数の時、m を素因数分解できれば任意の y の mod m での平方根を簡単に求めることができる」と2は俺がかつてした回答とほぼ一緒かな。

「平方根」を整数解といったりとか、言葉がちょっと違うけど、要するに初等整数論の問題なんだよね

mが素数の場合の平方剰余の判定法については
http://aozoragakuen.sakura.ne.jp/suuron/node41.html
http://aozoragakuen.sakura.ne.jp/suuron/node44.html
を参考にしてほしい

mが合成数の場合は以下のようになる

mの任意の素因数pに対してx^2≡y (mod p)となるとき
つまり、yがmod pで平方数となるとき
http://aozoragakuen.sakura.ne.jp/suuron/node25.htmlの
定理15と定理16により、f(x)=x^2-yとすると、x^2≡y (mod m)が
整数解を持つことがいえるのでyはmod mで平方数となることがいえる。
つまりyが(mod p)での平方根が分かれば、定理15によりx^2≡y (mod p^k)
の平方根が構築できる、つまりyの(mod p^k)での平方根の存在がいえる。

mをm=(p_1)^(k_1)・...・(p_r)^(k_r)と素因数分解したとき
x^2≡y (mod (p_1)^(k_1) )，…，x^2≡y (mod (p_r)^(k_r) )が共に解をもつならば
定理16によりx^2≡y (mod m)の解を構築できる。
要するに、yがmod (p_1)^(k_1)、mod (p_2)^(k_2)、…、mod (p_r)^(k_r)での
平方根が求まれば、定理16によりyのmod mでの平方根が構築できる
つまりyのmod mでの平方根の存在がいえる。

定理16の証明で本質的な役割を果たす「中国剰余定理」については
http://aozoragakuen.sakura.ne.jp/suuron/node24.html
の定理13および定理13のガウスの別証明
http://aozoragakuen.sakura.ne.jp/suuron/node24.html#SECTION00312010000000000000
を見るとよい。

そうではないとき
つまり、yがmのある素因数qに対して平方数とはならないとき

yがmod mで平方数となると仮定する。
つまり整数nが存在して、n^2≡y (mod m)となる。
このとき整数k,hが存在してn^2-y=mk,m=qhと書ける。
n^2-y=qhkとなるから、n^2-yはqで割り切れる。
よってn^2≡y (mod q)となるから、yがmod qで平方数となってしまい
最初の仮定に反する。
したがって、このときyはmod mで平方数ではない。
つまりyの平方根は「存在しない」ことになる。

お礼

お返事が遅くなり申し訳ありませんでした。

理解するのに時間がかかってしまいまして…
でもようやく納得することが出来ました。

ありがとうございました。