modを使用した平方根の求め方

質問

解き方が解からない問題があります。
どれだけ考えても解き方がわからないので、どなたかわかる方教えてください。

【解き方が解からない問題】
大きな素数の積n=pqが与えられた時、nを素因数分解するのは非常に難しい。
整数ｍと整数ｙ(<ｍ)が与えられた時y=ｘ2(xの二乗) mod mなる整数解xが存在すれば、yは mod mで平方剰余であるという。
xを mod mでのyの平方根という。
mが素数7の時、
12(1の二乗の事です。二乗の書き方がわからなくて・・・)≡1 (mod 7) 、 22(2の二乗) ≡ 4 (mod 7)
32(3の二乗)≡2 (mod 7) 、 42(4の二乗) ≡ 2 (mod 7)
52(5の二乗)≡4 (mod 7) 、 62(6の二乗) ≡ 1 (mod 7)
となるので、1、2、4が平方剰余で、各平方剰余には２個の平方根がある。
mが二つの素数の積の場合、４個の平方根がある。

ここまでが参考書に載ってる説明です。
ここから私がわからない問題です。

102(10の二乗) mod 77＝23
n = 77 の素因数7と11から素因数の知識を利用してZのmod nでの平方根Sを計算する。
S2(Sの二乗) ≡ 23 mod 7
S2(Sの二乗) ≡ 23 mod 11
上の２つを解いて、mod 77での４つの平方根10、32、45、67を得る。

この２つの式から、何をどうやって計算して、４つの平方根10、32、45、67が導き出せたのかわかりません。

二乗の表記の仕方がわからず、とても見難くなってしまいました。すみません。
乱文になってしまいましたが、どなたかわかる方教えてください。
よろしくお願いします。

回答No.1

noname#57316 · ベストアンサー

Sの２乗を、S^2 などと書きます。

「mod nでの平方根」の定義から、
S^2 ≡ 23 (mod 7) ＝ 2 (mod 7)
は、p を整数として、7・p+2 がある数、S の平方数になっている、
7・p+2 ＝ S^2　　　　（1）
ということを意味しており、この S が同時に
S^2 ≡ 23 (mod 11) ＝ 1 (mod 11)
つまり、q を整数として、11・q+1 がある数、S の平方数になっている、
11・q+1 ＝ S^2　　　　（2）
ということを意味している。

このような数、S は、上の式を変形しても導けず、p、q を変えていき、満足する数を見つける
しかない。
（1）を満たす p、S の組は、(1,3)、(14,10)、(146,32) …
（2）を満たす q、S の組は、(9,10)、(93,32) …
であり、同時にこの条件を満たす S は、10,32,…　なのである。

お礼

ありがとうございます！！！
丁寧な回答、本当にありがとうございました！！

これらの式を変形していったり、なにかの定理を使用して導き出せたりするものではなかったんですね。
追加で回答もしていただき、すごくみやすく解かりやすい回答で本当に助かりました。
ありがとうございます！！

回答No.4

age_momo

#3です。

>S ≡ ±3 (mod 7)は、どの様にして導かれたのでしょうか？？

あまり深くは考えていません。ご自分で(参考書に）書いてある通り、
---------------------------------------------------------------------------------
12(1の二乗の事です。二乗の書き方がわからなくて・・・)≡1 (mod 7) 、 22(2の二乗) ≡ 4 (mod 7)
32(3の二乗)≡2 (mod 7) 、 42(4の二乗) ≡ 2 (mod 7)
---------------------------------------------------------------------------------
3^2≡2 (mod 7)
から
S≡±3 (mod 7)です。(3が見つかれば当然、-3≡4 mod 7もOKです)
先に書いた通り、あらゆる整数の2乗はその整数の7における剰余の2乗と合同に
なりますから7の剰余の2乗を調べれば
S^2≡2≡3^2 (mod 7)からS≡3or4 (mod 7)が言えます。
S≡±1 (mod 11)はもっと簡単ですね。明らかに1^2=1 (mod 11)ですから。

p,qが互いに素なら
mp+nq=1
となる整数の組(m,n)が必ず(無数に)存在します。
書き方を変えれば
mp-(-n)q=1
11,7の場合は
11*2-7*3=1　　・・・・・・・(1)
があります。(当然、9,18や-5,-8でも成立します)
とにかくこれを1つ見つければ
11m-7k=2
を作るには(1)の両辺を2倍して
11*4-7*6=2
二つの式を見比べれば
m=4,k=6
元の式に代入すれば
S=7k+3=42+3=11m+1=44+1=45
です。

お礼

丁寧な回答ありがとうございました。

理解できました！！！
本当にありがとうございました。

回答No.3

age_momo

少し合同式の復習から

ある整数(7m+n)の2乗の7を法とする剰余系は

(7m+n)^2=49m^2+14mn+m^2≡m^2 (mod 7)

要はどんな整数を2乗しても7の剰余系の2乗と同じになります。
これを踏まえて

S^2 ≡ 23 ≡ 2 (mod 7)
S^2 ≡ 23 ≡ 1 (mod 11)

ならば

S ≡ ±3 (mod 7)
S ≡ ±1 (mod 11)

となります。
S = 7k+3 = 11m+1　とおくと(0≦k<11,0≦m<7)
11m=7k+2
11m-7k=2
今、11*2-7*3=1 なのでm=4,S=45と分かります。
同様にして
S = 7k+3 = 11m-1
11m-7k=4
11*8-7*12=11*1-7*1=4 (両方からそれぞれ7,11を引いても等号が成り立ちます)
よってm=1,S=10
S = 7k-3 = 11m+1
11m-7k=-4
11*(-1)-7*(-1)=11*6-7*10=-4
m=6,S=67
S = 7k-3 = 11m-1
11m-7k=-2
11*(-4)-7*(-6)=11*3-7*5=-2
m=3,S=32

補足

丁寧な回答ありがとうございます！

S^2 ≡ 23 ≡ 1 (mod 11) が S ≡ ±1 (mod 11)になるということはなんとなく理解できた気がしたのですが、理解できたと思った方法(ミラーラビン法を使うと思ったのですが・・・)で、

S^2 ≡ 23 ≡ 2 (mod 7)　から　S ≡ ±3 (mod 7)　を導こうと思っても導くことができませんでした。

S ≡ ±3 (mod 7)は、どの様にして導かれたのでしょうか？？

また、
>S = 7k+3 = 11m+1　とおくと(0≦k<11,0≦m<7)
>11m=7k+2
>11m-7k=2
>今、11*2-7*3=1 なのでm=4,S=45と分かります。
この上から三行目までは解かるのですが、mの値とkの値はどこの値をあてはめているのですか？？

よろしくおねがいします。

本当に理解できていなくてすみません・・・
みなさんが書いてくださった回答も全く理解できない事が恥ずかしく思います。
頑張って勉強して、みなさんのようになりたいです！！！

回答No.2

noname#57316

細かいことですが、p、S の組、q、S の組は多数あります。
（同時に二つの式を満たす S は、10、32、45、67 に限られますが）
（1）を満たす p、S の組は、(1,3)、(2,4)、(17,11)、(14,10) …(146,32) …
（2）を満たす q、S の組は、(9,10)、(13,12)、(40,21)、(48,23) …(93,32) …