• ベストアンサー
  • すぐに回答を!

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

解き方が解からない問題があります。 どれだけ考えても解き方がわからないので、どなたかわかる方教えてください。 【解き方が解からない問題】 大きな素数の積n=pqが与えられた時、nを素因数分解するのは非常に難しい。 整数mと整数y(<m)が与えられた時y=x2(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が平方剰余で、各平方剰余には2個の平方根がある。 mが二つの素数の積の場合、4個の平方根がある。 ここまでが参考書に載ってる説明です。 ここから私がわからない問題です。 102(10の二乗) mod 77=23 n = 77 の素因数7と11から素因数の知識を利用してZのmod nでの平方根Sを計算する。 S2(Sの二乗) ≡ 23 mod 7 S2(Sの二乗) ≡ 23 mod 11 上の2つを解いて、mod 77での4つの平方根10、32、45、67を得る。 この2つの式から、何をどうやって計算して、4つの平方根10、32、45、67が導き出せたのかわかりません。 二乗の表記の仕方がわからず、とても見難くなってしまいました。すみません。 乱文になってしまいましたが、どなたかわかる方教えてください。 よろしくお願いします。

共感・応援の気持ちを伝えよう!

  • 回答数4
  • 閲覧数1230
  • ありがとう数2

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.1
noname#57316
noname#57316

Sの2乗を、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,… なのである。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

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

関連するQ&A

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

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

  • modに関する証明問題

    pをp≡3mod4を満たす素数として、a≡b^2mod pが解を持つとしたとき a^(p+1)/4 が a の mod p での平方根になる ことを示したいのですが、どうしてそうなるのか、さっぱりです。 どなたか教えていただけないでしょうか。

  • 数学、mod pのk乗

    xの2乗≡a(mod pのk乗)が整数解を持てばxの2乗≡a(mod pのk+1乗)も整数解を持つ pは素数、kは0以上の整数、aは整数 この証明についての質問です。 xの2乗≡a(mod pのk乗)の整数解をx1とすると x1の2乗-a=(pのk乗)s sは整数 x2=x1+(pのk乗)tとおくと x2の2乗-a=(x1+(pのk乗)t)の2乗-a =x1の2乗+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗)-a =(x1の2乗-a)+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗) =(pのk乗)s+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗) =(pのk乗)(s+2(x1)t+(pのk乗)(tの2乗)) ここまではいいのですが s+2(x1)t≡0(mod p)となるようにtを選ぶことができるというのがわかりません。 ここを通過すればpのk+1乗を約数にもつことになって証明が終わります。

その他の回答 (3)

  • 回答No.4

#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

少し合同式の復習から ある整数(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
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) …

共感・感謝の気持ちを伝えよう!

関連するQ&A

  •  高木初等整数論 p85 

    初等整数論で (n/m)は平方剰余のルジャンドルの記号、もしくは,Jacobiの記号とします。水平の-が書けないため。 (記号の説明) φ(m):オイラー関数:mと素である整数の数 Legendreの記号 x^2≡a  (mod.p)が解をゆうするときにaをpの平方剰余、そうでないとき平方非剰余という。 not(a≡0) (mod.p)でないとき、aが平方剰余であるか、非剰余であるかに従って (a/p)=+1または-1 (m/n)の定義 n>1が奇数で,n=pp'p''---が、nの素因数分解でsるとき,(m,n)=1なる整数mに関して (m/n)=(m/p)(m/p')(m/p'')---とする。 右辺は、Legendreの記号 jacobiの記号 (定理) mが平方数でないならば、mを法とするφ(m)個の既約類のうち、半数に属するnに対しては(n/m)=+1、他の半数に対しては、(n/m)=-1 (証明)と続きますが。 mを法とする同一既約類に属するnに対しては(n/m)の値は一定. いまφ(m)個の既約類の代表を(n/m)の値によって+の組と-の組とに分けて、 (+)  a1、―――,an    (a/m)=+1 (-) b1、―――,bn    (b/m)=-1 とする。 a≡1(mod m)であるaなどは+の組に属するが、仮定でmは平方数でないから、-の組も空虚でない。 (質問)mは平方数なら、-の組は空虚は明らかですが、mは平方数でないから、-の組も空虚でないはどうしていえるのでしょうか。わかりやすく説明ください。

  • EXCELの関数式(INT,MOD)で教えて下さい

    下図のようなEXCELの表があります。 金種計算で、1行目は1万円、5千円、千円・・・10円と入っており、 A2は計算したい金額(97810)を入れています。 B2セルの式=INT($A2/B1)、C2セルの式=INT(MOD($A2,B1)/C1)で、C2セルの式はD2~H2に複写しています。 EXCELで得た計算結果(2行目)は正しいと思うのですが、 D2,F2,H2の計算結果と、自分で計算した結果があいません。 ここを詳しく教えて頂けないでしょうか。 宜しくお願い致します! INT関数:整数部を返す MOD関数:剰余を返す  |  A  |  B |  C |  D |  E |  F |  G |  H | 1|   |10000| 5000| 1000| 500| 100|  50 |   10| 2|97810|   9|   1|   2|    1|   3|   0|   1| B2は、98710÷10000=9.7810→整数部を返すので「9」 C2は、97810÷10000=9.7810→剰余7810÷5000=1.562 →整数部を返すので「1」 D2は、97810÷5000=19.562→剰余562÷1000=0.562 →整数部を返すので「0」??? E2は、97810÷1000=97.810→剰余810÷500=1.62 →整数部を返すので「1」 F2は、97810÷500=195.62→剰余62÷100=0.62 →整数部を返すので「0」??? G2は、97810÷100=978.10→剰余10÷50=0.2 →整数部を返すので「0」 H2は、97810÷50=1956.2→剰余2÷10=0.2 →整数部を返すので「0」???

  • 任意のkに対し、f(m)がk個の素因数を持つ様なm

    f(x)を整数係数のmonic polynomialとしたとき 任意の整数kに対して、f(m)がk個の異なる素因数をもつような整数mは存在するか という問題なのですが、 素数を小さい順にp_1 ,p_2, p_3, ...とし、 f(m)の素因数がp_1, p_2, ... , p_kとなるようなmが存在することを示す。 f(x)は問題文の条件より f(x)=(x-a_1)(x-a_2)....(x-a_n)とおける (a_iは整数) p_iは素数なので互いに素 中国の剰余定理より y≡a_1 (mod p_1) y≡a_2 (mod p_2) y≡a_3 (mod p_3) ... y≡a_k (mod p_k) を満たすyが存在する。 y-a_1≡0 (mod p_1) y-a_2≡0 (mod p_2) y-a_3≡0(mod p_3) ... y-a_k≡0(mod p_k) となるためf(y)はp_1, p_2, ..., p_kのすべてで割り切れる。 間違いがあったら指摘ください。

  • 合同方程式の解

    整数論に関する問題です。 pを4|p-1 を満たす素数とする。 このとき x^4≡1(mod p) には法pで 4つの解があることを示せ。 4|p-1とは4がp-1を割り切るという ことです。 解の数とはpを法として互いに合同でないもの の個数のことです。 整数論が苦手で、どうしてもわかりません。 どなたかよろしくお願いします。

  • aが整数で、x^5-ax-1が整数を係数とする2つの

    aが整数で、x^5-ax-1が整数を係数とする2つの 整式の積に表されるとき、aの値を求めよ。 x^5-ax-1=0 とおいて、もし、解が整数をもつときは 剰余定理からa=0,2が分かるのですが、整数解を持たない場合 もあるので、どんな解法があるのか。よろしくお願いします。

  • 平方根 応用問題がわからず困っています

    次の2つの平方根についての問題がわからず困っています √40a の値が2桁の自然数になるような、自然数aの値をすべて求めなさい。 連続する3つの自然数a,b,cがある。√2+3+4 の値は、√9=3のように整数になるが、このように、√a+b+c の値が整数となるa,b,cの組の求め方を書きなさい。 解き方(考え方)がわかるように、途中式や説明もいただければ、幸いです。 よろしくお願い致します。

  • メビウス関数、どうしてそのように定義するの?

    自然数nにおいて、メビウス関数は次のように定義される(ただし 1 は 0 個の素因数を持つと考える): μ(n) = 0 (n が平方因子を持つ(平方数で割り切れる)とき) μ(n) = (-1)^k (n が相異なる k 個の素因数に分解されるとき) n が相異なる偶数個の素数の積ならば μ(n) = 1 n が相異なる奇数個の素数の積ならば μ(n) = -1 とのことですが、なんの理由、なんの目的があってそのような定義がされるのでしょうか? そう定義すると、メビウスの反転公式などうまくいくというのは分かるのですが、たとえば、メビウスの反転公式を成り立たせるようなμ(n)は、必然的に上述のようになることを示すことはできるのでしょうか?

  • 因数と素因数およびそれを用いた証明

    他の方の質問に回答しているやりとりの中でどうしても腑に落ちないことがあり、これ以上その方の回答欄に書くわけにもいかないと思い質問します。 「素因数」…ある整数の約数である素数のこと。 「因数」…一つの数または式がいくつかの数または式の積によって形成されている場合、その個々のその個々の数や式、因子。 (いずれも広辞苑より) とあります。 この説明を読む限りでは、素因数⊂因数だと思います。つまり、整数が因数の積で表される時、その因数が素数の時は特に素因数と呼ぶ、と。 ということは、証明においてある整数の因数全体で成り立つことが示せれば、その整数の素因数でも成り立つことは自明だと思うのですが、違うのでしょうか? また、ほとんどの参考書および教科書では、 「ある整数Aと1を除く自然数mにおいて、A^3がmの倍数⇔Aがmの倍数」であることを自明のこととして扱っています(mが素数かどうかに関わらず)。事実私もそうでした。しかし、自明ではないという意見もあるようです。どちらなのでしょうか? 自明であるという意見の方はその理由を、自明でないと言う方は反例をあげて下さい。 長文になりましたが、よろしくお願いします。

  • 平方根の連分数展開の周期

    何冊か数論の本を読んでみたのですが、見つけることができませんでした。 Dを平方数でない自然数とするとき、√Dの連分数展開は周期を持つ無限連分数になります。もちろんこの周期自体は実際に連分数展開してみないことにはわかりませんが、周期が偶数になるか奇数になるかは簡単に判定できるのではないか、と思いました。このことはx^2-Dy^2=-1が整数解を持つかどうかと同値で、また判別式が-1になることとも同値だと思います。しかしいずれにしても連分数展開を実行してみない以上わからないので不便です。 D=n^2-2と書けないこと、かつD=p_1^{r_1}…p_k^{r_k}と素因数分解したとき、p_iたちすべてがmod 4で3と合同でない、ということと、連分数展開の周期が奇数であることは同値だと予想したのですが、これは正しいですか?実二次体がらみの話なので、どこかに書いてあるとは思うのですが・・・

  • 最大公約数を求める

    一般に、a,bが2^nくらいの整数であれば、最大公約数を求めるには、割り算も含めてn^3に比例した計算量が必要であるといわれている。しかし、これを素因数分解して求めると、素因数分解するのに、その数の平方根までの割り算が必要になるので、(√2)^nに比例した計算量が必要になる。 という説明があったのですが、”素因数分解するのに、その数の平方根までの割り算が必要になる”というのがよく分かりません。何故平方根まで割り算しないとならないのでしょうか????