- ベストアンサー
ゼロ知識証明の勉強をしているのですが…
ゼロ知識証明の勉強をしているのですが… 途中で 1.m が合成数の時、m を素因数分解できれば任意の y の mod m での平方根を簡単に求めることができる。逆に任意の y に対する mod m での平方根が求まるならば、m を簡単に素因数分解できる。 2.m を素因数分解できれば、任意の y に対し mod m での平方剰余性を簡単に判定できる。 とあったのですが、計算方法が解らないので、納得が出来ません。 具体的な計算方法が解る方がいらっしゃいましたら、ご教授願います。
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
関連するQ&A
- 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が導き出せたのかわかりません。 二乗の表記の仕方がわからず、とても見難くなってしまいました。すみません。 乱文になってしまいましたが、どなたかわかる方教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 高木初等整数論 ｐ８５
初等整数論で (n/m）は平方剰余のルジャンドルの記号、もしくは,Jacobiの記号とします。水平の-が書けないため。 （記号の説明） φ(m):オイラー関数：ｍと素である整数の数 Legendreの記号 x^2≡a (mod.p）が解をゆうするときにａをｐの平方剰余、そうでないとき平方非剰余という。 not（a≡0） (mod.p）でないとき、ａが平方剰余であるか、非剰余であるかに従って （ａ/p）＝+１または-１ (m/n）の定義 ｎ＞１が奇数で,n=ｐｐ'p''---が、ｎの素因数分解でｓるとき,(m,n)=1なる整数ｍに関して （m/n）＝（m/ｐ）（m/ｐ'）（m/ｐ''）---とする。 右辺は、Legendreの記号 ｊａｃｏｂｉの記号 （定理） ｍが平方数でないならば、ｍを法とするφ(m)個の既約類のうち、半数に属するｎに対しては(n/m）＝+１、他の半数に対しては、(n/m）＝-１ (証明）と続きますが。 mを法とする同一既約類に属するｎに対しては(n/m）の値は一定. いまφ(m)個の既約類の代表を(n/m）の値によって+の組と-の組とに分けて、 （+） a1、―――，aｎ （a／ｍ）＝+１ （-） ｂ1、―――，bｎ （b／ｍ）＝-１ とする。 ａ≡１(mod ｍ）であるａなどは+の組に属するが、仮定でｍは平方数でないから、-の組も空虚でない。 (質問）ｍは平方数なら、-の組は空虚は明らかですが、ｍは平方数でないから、-の組も空虚でないはどうしていえるのでしょうか。わかりやすく説明ください。
- 締切済み
- 数学・算数
- 法が合成数の時の平方剰余
法が合成数の時の平方剰余 法が素数であれば平方剰余の相互法則等を用いて、 簡単に平方剰余の判定ができます。 http://ja.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E5%89%B0%E4%BD%99%E3%81%AE%E7%9B%B8%E4%BA%92%E6%B3%95%E5%89%87 では、法が合成数だった場合、簡単な計算方法はあるのでしょうか？
- ベストアンサー
- 数学・算数
- すばやく素因数分解する方法は？
「暗号解読」（サイモン・シン（著）青木薫（訳） 新潮社）という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数（合成数）を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法（素因数分解）を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法（アルゴリズム）を知りたいです。
- ベストアンサー
- 数学・算数
- 素因数分解の証明問題
素因数分解の証明問題 証明方法がわかりません。 自然数の素因数分解をn=(P_1)^e_1(p_2)^e_2・・・(p_r)^e_rとする。このとき、 φ(n)=n｛1-(1/p_1)｝｛1-(1/p_2)｝・・・｛1-(1/p_r)｝となることを示せ。 ただし、自然数m,nに対して、gcd(m,n)=1ならば、φ(mn)=φ(m)φ(n)であることを用いよ。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- RSA暗号が破れる素因数分解についてです。
自然数 N を、√N （＝ Nの平方根）未満の自然数であって、末位の数字が１，３，７，９のもののうち、小さいもの順のものどもで以て、割ってゆき、N を素因数分解する計算の、時間計算量のオーダーは、 どれ位のものでしょうか。
- ベストアンサー
- その他([技術者向] コンピューター)
- RSA暗号解読の素因数分解による方法について。
下記の通りで正しいでしょうか。： Microsoft Bing AI （＝ Bing Chat）生成人工知能の回答を、まとめ、且つ、補足しますと、次の通りです。 自然数 N を、√N （＝ Nの平方根）未満の自然数であって末位の数字が１，３，７，９のもので以て、割ってゆき、N を素因数分解する、という計算の、時間計算量は、O(Nの４乗根）です。 実際には、RSA暗号による暗号文の暗号は、巨大素数を２つ掛け合わせて作りますので、Nの平方根未満の自然数で、末位が１，３，７，９のもので、しかも、大きいもの順に取ったもので順に割っていけば、N の素因数分解は、時間計算量を、それよりも遥かに小さくして済ませらせます。 上記の様に、問題サイズ N に対する、N の４乗根のオーダーの時間を上界（この場合は、自然数の計算ですので上限）とする、普通の割り算の単純作業だけで、つまり、ごくごく短時間に、N の素因数分解が出来てしまいますので、RSA暗号も、いとも簡単に解けてしまう、ということです。
- ベストアンサー
- セキュリティ対策
- 平方根を理解できません
中一男子です。数検を受けようと思って勉強をしているのですが、平方根が全く理解できません。長文になってもいいので教えてください。(できれば因数分解、素因数分解もお願いします)
- ベストアンサー
- 数学・算数
- 任意の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-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のすべてで割り切れる。 間違いがあったら指摘ください。
- ベストアンサー
- 数学・算数
お礼
お返事が遅くなり申し訳ありませんでした。 理解するのに時間がかかってしまいまして… でもようやく納得することが出来ました。 ありがとうございました。