今暗号について勉強しています。その中に素因数分解が困難であることを利用してつくられた暗号がいくつかありますが、なぜ素因数分解が困難であるのかがわかりません。それを証明する方法などがありましたらなんでもいいので教えてください。

このQ&Aに関連する最新のQ&A

A 回答 (2件)

素因数分解は結局可能性のある素数でつぎつぎと割ってみて、割り切れるかどうかで調べるしか手段なないこと。


この方法だと,桁数が増えたときに計算量が爆発的に増えることによります。

ただし、証明はまだされていないと思います。
ですから数学的には未解決の問題です。

証明は出来ませんが、ある桁数の数をある方法で素因数分解するための平均的な計算量などは計算できますから、
現在の最速の計算機で何億年もかかるとなると、
事実上解読不能ということになります。
もちろん、桁数が多くても2の倍数なんてつかったら、
あっという間に解かれますね(^^;

将来簡単な計算法が見付かる可能性も0ではありませんが、
過去の例からするとこういう問題はできないことが証明されるのがほとんどのようです。
    • good
    • 0
この回答へのお礼

 そうですか・・今現在最良の素因数分解のアルゴリズムの計算量を計算してみて納得したいと思います。
ありがとうございました。

お礼日時:2002/01/30 23:46

以下のサイトが参考になるでしょうか。


http://www.maitou.gr.jp/rsa/rsa14.html

この回答への補足

ありがとうございます。なんとなく困難であるということはわかりましたが、はっきり困難であるとういう数学的証明はできないのでしょうか?

補足日時:2002/01/30 22:45
    • good
    • 0

このQ&Aに関連する人気のQ&A

RSA とは」に関するQ&A: アルミは錆びるの?

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q「A地点とB地点にいる二人が同時に出発して接近した」この問題の解き方を教えてください

「A地点とB地点にいる二人が同時に出発して接近した」この問題の解き方を教えてください

問題
A地点にいるA君と、B地点にいるB君が同時に出発して接近した。
A君は時速4キロ、B君は時速8キロで移動した
A地点とB地点は10キロ離れている
さて二人が接触する地点の位置はどこで、出発時刻から何分後か?
道中は平坦な直線であり途中に坂や障害などはないとする

さてこの問題の解き方を教えてください

小学校算数での解き方、
中学校数学での解き方、
高校数学での解き方、
それぞれ教えてください

Aベストアンサー

A君は時速4キロ、B君は時速8キロで近づいているので、
合わせて時速12キロで近付いています。
2人が接触するのは10/12=50/60時間=50分です。

t分後に接触したとして、
A君は時速4キロで、4*t/60キロ移動しています。
B君は時速8キロで、8*t/60キロ移動しています。
二人は合計で10キロ移動したので、
4*t/60+8*t/60=10
12t=600
t=50分後です。

A君は時速4キロでxキロ、
B君は時速8キロでyキロ、
走った時に接触したとして、
x+y=10
x/4=y/8
なので、
x=2y
3y=10
y=10/3
10/3÷4=10/12時間=50分後です。

Q自然数nを素因数分解すると、素因数は2と3であり、それ以外の素因数はない。また、nの正の約数の個数は

自然数nを素因数分解すると、素因数は2と3であり、それ以外の素因数はない。また、nの正の約数の個数はちょうど12である。このような自然数nをすべて求めよ。
わかる方教えてください!

Aベストアンサー

n=2^a×3^bと表せます。^aはa乗を示します。
abはそれぞれ自然数です。
ここで約数の数は(a+1)×(b+1)=12と表せます。
これは(a=1,b=5)(a=2,b=3)(a=3,b=2)(a=5,b=1)の4通りです。
それぞれnを求めると、486,108,72,96となります。

Q問題の解き方をHPにのせるときの著作権について

はじめまして。
HPに学習ページをつくろうと思っています。
教科書の章末問題などでは、問題と答えだけしかのってないものがありますよね。
自分流に問題をといて、解き方をHP上にのせるのは
著作権の侵害になるのでしょうか?
「~~という本のP32の問1の解き方」とか書いたら侵害になるのでしょうか?
こういうタイトルをかかないで、問題と解き方だけを書いたほうがいいのでしょか?

Aベストアンサー

> 自分流に問題をといて、解き方をHP上にのせるのは
著作権の侵害になるのでしょうか?

なりません。

> 「~~という本のP32の問1の解き方」とか書いたら侵害になるのでしょうか?

もし、このURLに書いてみる内容と合致すれば、
問題ないのかも。
http://www.cric.or.jp/qa/sodan/sodan6_qa.html

私も法律家ではないので詳しくはないですが、
こちらを参考にされてみてはいかが?
http://www.cric.or.jp/

Q素因数分解の答え方について

この前数学技能検定(数検)を受けてきたのですが、2009を素因数分解しろという問題が出て、私は、7×7×41という答え方をしてしまったと思うのですが、やはり7の二乗×41と書かないとバツになってしまいますかね?
どう思いますか?回答よろしくお願いします。

Aベストアンサー

数検を受けたことがないのですが、普通累乗を用いますね。バツかどうかはわかりませんが、5aと答えるところをa×5と書いているようなものでしょうね。

Q指数関数の解き方

a2x=3の時

  a3x-a-x
-----  この解き方が解らないので
   ax+a-x
         解き方のヒント教えて

Aベストアンサー

分子と分母に a^x をかけましょう。

分子は a^{4x}-1 = (a^{2x})^2-1 = 3^2 - 1
分母は a^{2x}+1 = 3 + 1

となります。

Q素因数分解でわからない問題があります。教えていただ

けますでしょうか。
勉強していて、下記の問題がどうしてもわかりません。
解答はついているのですが、考え方がわかりません。
教えていただけないでしょうか?
問い
56にできるだけ小さい自然数をかけて、ある整数の二乗にしたい。どんな数をかければよいか?

素因数分解はできるのですが(2の3乗X7)、その後の考え方がわかりません。
ちなみに答えは2X7=14 です。
解説に、56=2の3乗x7=2の2乗x(2x7) よって、2x7=14とありますが、
この解説がまったく理解できません。 2x7=14が何を意味するのかがわかりません。
どう考えればよいのでしょうか?

同じく
360を自然数でわって、ある整数の2乗にしたい。どんな数でわればよいか?
という問いも、素因数分解から先の考え方がわからず、解けません。
(答え10,40,90,360)。

どなたか 解き方(考え方)を教えていただけますでしょうか。

Aベストアンサー

56×14=784ですね・・・
そして、784=28^2

取り敢えず、56を素因数分解すると、
56=2^3×7。これは、いいですね?
この段階で、2×2は2の2乗になってるので、残りの2×7も2乗になるように2×7=14をかけたワケです。
もっと分かりやすく、問題から、
56×○○=X^2とします。
そこで、X^2=2^3×7×○○です。
ここで、X^2=A^2×B^2としたらどうでしょう?
A^2×B^2=(AB)^2=X^2であることは分かりますよね?
つまり問題から、56に自然数をかけてX^2にすることは、(AB)^2にすることと同義なのです。
なのでまず始めに、56=2^2×2×7より、2の2乗の形になってるので、2^2を省きます。
そして、2×7を2乗の形にするにはどうするか?そう、2×7をかけるのです。
こうすることで、
56×○○=2^2×(2×7)^2=(2×2×7)^2となり、
求める自然数○○は、2×7=14となります。

これに限らず、2乗が増えるようなら、
○○×□□=2^2×3^2×・・・・
○○×□□=(ABC・・・)^2
といったように、2乗する文字を増やしていかなければなりません。

次に、360について、
360=2^3×3^2×5
これより、360を△△で割って、X^2にするんです。
この△△は、右辺から推測します。
(A)360=2^2×3^2×2×5にして、
両辺を2×5で割れば、左辺は2^2×3^2=(2×3)^2になります。
よって、割る数は2×5=10
(B)360=3^2×2^3×5にして、
両辺を2^3×5で割れば、左辺は3^2になります。
よって、割る数は2^3×5=40
(C)360=2^2×2×3^2×5にして、
両辺を2×3^2×5で割れば、左辺は2^2になります。
よって、割る数は2×3^2×5=90
(D)360=2^3×3^2×5より、
両辺を2^3×3^2×5で割ると、左辺は1=1^2
よって、割る数は2^3×3^2×5=360

となり、回答を満たします。
考え方さえ理解できれば、問題式を分解して、回答の推測、証明で済みます。

参考までに、

56×14=784ですね・・・
そして、784=28^2

取り敢えず、56を素因数分解すると、
56=2^3×7。これは、いいですね?
この段階で、2×2は2の2乗になってるので、残りの2×7も2乗になるように2×7=14をかけたワケです。
もっと分かりやすく、問題から、
56×○○=X^2とします。
そこで、X^2=2^3×7×○○です。
ここで、X^2=A^2×B^2としたらどうでしょう?
A^2×B^2=(AB)^2=X^2であることは分かりますよね?
つまり問題から、56に自然数をかけてX^2にするこ...続きを読む

Q因数分解の解き方について

因数分解の解き方について
質問です。

3x2 -7x+2

たすき掛けをつかわない
因数分解の解き方を
教えてください。

たしか、海外の学生の解き方で、
まず数字をかけるやり方だったと思います。

分数などにはせず、
最後は見事に解答が出る方法です。

思い出せず、モヤモヤしています。
よろしくお願いします。

Aベストアンサー

>>>たしか、海外の学生の解き方で、まず数字をかけるやり方だったと思います。

ありましたね。

>>>思い出せず、モヤモヤしています。

私もサイトをお気に入りに入れていなかったので、もやもやしています。^^

たぶん、x^2 につく係数を整数の2乗にするんじゃなかったかと思います。

これでうまくいっているのかわかりませんが、3をかけて
9x^2 - 3×7x + 6 = (3x+a)(3x+b)
 = 9x^2 + 3(a+b)x + ab
としてみると、
a+b = -7
ab = 6
なので、
a=-1、b=-6

わりと楽に行きました。
最後の仕上げに、3で割って元に戻しましょう。

ただし、これが思い出せないやり方と同じなのかわかりませんが・・・

Q素因数分解の問題について

高校の数学の問題なのですが、
3^240-1を素因数分解したとき2は何回現れるか、という問題があって
どうしても解き方が分かりません。
皆さんの力をお貸しください。よろしくお願いします。

Aベストアンサー

とりあえず、
3^240-1=(3^120+1)(3^120-1)=(3^120+1)(3^60+1)(3^60-1)
=・・・=(3^120+1)(3^60+1)(3^30+1)(3^15+1)(3^15-1)
と分解する。
ここで、3のべき乗に関し、3の奇数乗は4で割ると3余り、3の偶数乗
は4で割ると1余る、ということを使う。(これは帰納的に簡単に
分かるでしょう。)
これより、3の偶数乗+1は4で割ると2余る。つまり、3の偶数乗+1は
2では割り切れるが、4では割り切れず、したがって、素因数2を一つ
だけ持つ。
よって、3^240+1、3^60+1、3^30+1はそれぞれ、素因数2を一つだけ
もつ。
また、3の15乗については、公式、
x^3+1=(x+1)(x^2-x+1)
x^3-1=(x-1)(x^2+x+1)
を使って分解するとよい。
そして、同じように、4で割ったときの余りを考えるとよい。
割り切れなければ、2では1回しか割り切れない・・・

Q不等式の解き方教えてください!

不等式の解き方教えてください!
(100+z)-(100+z)×0.2≧100
↑↑の解き方を教えてください!

Aベストアンサー

(100+z)-(100+z)×0.2≧100

わかりやすく、ばらばらにしましょう。

100+Z-0.2×100-0.2×z≧100

つぎにまとめましょう。

(1-0.2)×z+(1-0.2)×100 ≧100

けいさんをすすめましょう

0.8×z+0.8×100≧100

さらにすすめましょう

0.8×z+80≧100

つぎに、りょうほうのしきから80をひいてみましょう

0.8×z+80-80 ≧100-80

ぱずるといっしょですね。

0.8×z ≧20

こんどはりょうほうのしきを0.8でわってみましょう

0.8÷0.8×z ≧20÷0.8

z≧20÷0.8=200÷8=100÷4=50÷2=25

だから・・・

z≧25

となりますね

Q素因数分解!?

xは自然数でx^2=736164のときxを求めよ。という問題なのですが、素因数分解してくと2、2、3、3の順で分解できるのはすぐ気づきます。しかし20449でとまってしまいます・・。なんとか143で分解できると気づいてx=858と答え出せたのですが、もっと上手い解き方ありますか?あるいは、2~3桁の素数の積を一瞬で見分ける方法はありますか?わかる方いましたらお願いします。

Aベストアンサー

基本は元の数の√の値ぐらいまでの素数を順に試していくしかありません。
ただし
2の倍数・・・1の位が偶数
3の倍数・・・すべての桁の数を足すと3の倍数
5の倍数・・・1の位が0か5
は見分けやすいです。

736164の場合
→2×368082
→2×2×184041
→2×2×3×61347(一番小さい素数の2では割れないのでその次に小さい3で割ってみる)
→2×2×3×3×20449
ここで20449を小さい素数から順に割ってみると3無理、5無理、7無理、11で割れるので
→2×2×3×3×11×1859
→2×2×3×3×11×11×169
169=13×13より
→2×2×3×3×11×11×13×13

とにかく2から素数で順に割って割れるかどうか確認してみるのが一番早いです。コンピューターも現在のところこの方法しか無理みたい立ったと思いますので王道ですがこの方法が一番いいです。


人気Q&Aランキング

おすすめ情報