RSA暗号で巨大な素数(10^100とかのオーダー)を使うのですが、
そんな巨大な素数はどうやって見つけるのですか?

超簡単な方法がありそうですけど。

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

A 回答 (4件)

超簡単な方法はないですが、、、


素数を生成するというよりは、
適当に数字を決めて、それが素数かどうか判定します。
100%素数であることを証明するには、
それより小さい数すべてで割ってみる、なのですが、
これでは時間がいくらあっても足りません。
そこで、合格したらその数は「ほぼ間違い無く」素数であるといわれるようなテストが用意されています。
手元の書籍「暗号・ゼロ知識証明・数論、共立出版、
情報処理学会監修、岡本龍明・太田和夫共編」に
詳しくかかれています。
これによると、Fermatテスト、SoLovay-Strassenテスト、
Miller-Rabbinテストに合格したらそれは素数とみなすと。
他にもAdleman-Rumely法、Jacobi和テスト・Cohen-Lenstra法、楕円曲線法、、、などあるようです。
私もちゃんと理解しているわけではなく、詳細は説明できませんので、
上記の名前で検索or書籍を参照してください。
    • good
    • 0
この回答へのお礼

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

自分でも調べてみたのですが、素数を見つける公式は見つかってないそうですね。
RSA暗号では鍵を作る上で巨大な素数を必要とするのですけど、
その素数を見つけるには、暗号を解読するコストの^(1/2)かかるので、
そりゃたいへんだなあ、と。

素数テーブルみたいなものがあるのでしょうか?

お礼日時:2001/11/29 12:35

ブルーバックスの暗号の数理って本にいくらか公開鍵暗号の解説があります。



素数の生成ですが、エラトステネスのふるいは、計算量とか使用メモリ量とか考えると,巨大な素数の生成は無理でしょう。

ところで、nが素数の判定ですが、・n 以下の整数まで調べれば十分です。
もし、・nより大きい因数があるなら、もう一方はかならず・nより小さい数になるからです。


dumdummyさんはほぼ間違いなく・・とかかれていますが、ほぼでなく、確実に素数かどうかの判定を高速にする方法はあります。

フェルマーテストは素数でない数を判定する方法なので、これだけでは不十分なのは確かですが。

また、こういう整数計算は一般的に面倒な部類にはいります。
たかだか、64bit程度の数字を使うなら速いでしょうが。
    • good
    • 0
この回答へのお礼

フェルマーテストは「素数でない」ことを判定するので、素数を見つけるには
大変になっちゃいますね。nが素数の積の場合は、
素数になってしまう場合もあるそうで。

とここまで書いて、以下のサイトをみつけました。

http://hanran.tripod.com/crypt/faq/appendix2.html

やっぱり「適当な数字が素数かどうか?」で素数を見つけるのですね。

自己解決見たくなってしまいましたが、ありがとうございmした。

お礼日時:2001/11/30 11:40

結局は、オーソドックスに「エラトステネスのふるい」でやるんだ、と聞いた事がありますが・・・。

    • good
    • 0
この回答へのお礼

ご回答ありがとうございます。

ちょう時間かかっちゃいますね。

お礼日時:2001/11/30 11:19

 私は、門外漢(専門分野といえるようなものはありませんが)ですが、多少の興味がありまして、書き込みをさせていただきます。



 下記URLにあるような仮想分散サービスが、本格稼働することを期待したいと思います。公開鍵・秘密鍵などのセキュリティに関することですので、生産性は十分に見込まれると思いますので、うまく実用化すればサービスとして提供されると思います。

 いくら、整数計算とはいえこれくらいのオーダーになると、分散処理でないと無理だと思うのですが。素数計算に関しては「エラトステネスのふるい」意外に知識はありません。考えてみればだれでも簡単に、しかも短時間に扱えれば鍵としての安全性は低いことになりますしね。

参考URL:http://www.fri.fujitsu.com/hypertext/fri/ec/00_9 …
    • good
    • 0
この回答へのお礼

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

力技しかないのかなあ。

お礼日時:2001/11/29 12:08

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

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

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

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

Q素数の覚え方

素数を覚えたいのですが、どんな語呂合わせが良いでしょうか?100以下の物を覚えたいと思ってます。

2 3 5 7 11 13・・・・・

Aベストアンサー

ネット上にいくつかありました。
(11~103)
http://homepage2.nifty.com/takeshin/information/karan_koron.htm
(2~29)
http://www1.kcn.ne.jp/~zubat/seisuuseisitu/seisitu5.htm

ただちょっと分かりづらいような気がしたので、自分で作ってみました。

生き別れた母からの手紙は届かず、父親や兄弟とも死別し、妻も無く会社倒産のあおりで職も失った29歳男性の悲哀を頭に思い浮かべながら覚えてください。

文(ふみ)来ない(2,3,5,7,11)
父さんいない(13,17)
逝く兄さん(19,23)
29歳身無し人(29,31,37,41)
嫁は至難(43,47)
この身は困苦(53,59)
無為なろくでなし(61,67)
無い涙で泣く(71,73,79)
破産波及で(83,89)
苦難の日々(97,101)

素数を思い出すたびに暗~い気持ちになったらすみません。

Qx^x^x^x^x^x^・・・・・^x  の一般的な表し方

タイトル通りになってしまいますが、

x^x^x^x^x^x^・・・・・・^x (xはn個ある)

を一般的に表すことができる式というのはあるものなのでしょうか?

grapesで
y=x
y=x^x
y=x^x^x
y=x^x^x^x
 ・
 ・
 ・

のグラフを描いてみましたところ、どうやらnが偶数か奇数かによって2種類のグラフに近づいているように見えたのです。どなたか一般的な記述の仕方をご存知の方、宜しくお願いしますm(_ _)m

Aベストアンサー

x^x^xはx^(x^x)と表すべきです。同様にx^x^x^xではなく、x^(x^(x^x))です。
これは(x^x)^xとx^(x^x)が等しくないから区別する必要があるわけです。
たとえば(3^3)^3=729なのに対し、3^(3^3)=19683です。
一般に後者の方が圧倒的に大きくなります。

さて、話をx^(x^(x^(…)))に戻しましょう。
これは定義域を[0,1]に限れば、確かにおっしゃるとおり偶数と奇数で
関数の形状が分かれます。これはx^x→1(x→0)が関係しています。
x^(x^x)は不定形の極限ではなく、単に0^1=0に収束します。
偶数個のときは不定形の極限が現れるわけです。
数学的帰納法とたとえばlogを取って極限計算をされてみたらよいでしょう。

さて問題になっている、x^(x^x)などの表記ですが、
これにはクヌースのタワー表記(1976)というものが知られています。
たとえば
x^(x^x)=x↑↑3
x^(x^(x^(x^(x^x))))=x↑↑6
などと表示します。参考URL(wiki)などをごらんください。
wikiによるとx^^3や、x^^6などとも表示するようです。

参考URL:http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%8C%E3%83%BC%E3%82%B9%E3%81%AE%E7%9F%A2%E5%8D%B0%E8%A1%A8%E8%A8%98

x^x^xはx^(x^x)と表すべきです。同様にx^x^x^xではなく、x^(x^(x^x))です。
これは(x^x)^xとx^(x^x)が等しくないから区別する必要があるわけです。
たとえば(3^3)^3=729なのに対し、3^(3^3)=19683です。
一般に後者の方が圧倒的に大きくなります。

さて、話をx^(x^(x^(…)))に戻しましょう。
これは定義域を[0,1]に限れば、確かにおっしゃるとおり偶数と奇数で
関数の形状が分かれます。これはx^x→1(x→0)が関係しています。
x^(x^x)は不定形の極限ではなく、単に0^1=0に収束します。
偶数個のときは不定...続きを読む

QちょっとHな化学記号の覚え方

 質問の場所が ここでいいか わからなかったので ここで 質問します

 化学記号の 覚え方に 横の列は「すいへーりーべ ぼくのふね 」
って 水素 ヘリウムの 順序を 覚えるのは みなさん ご存じだと
思います

 ところが 今日 小耳にはさんだのに タテの列の覚え方は 少し
色っぽい 覚え方が あると 聴きましたが どういう 覚え方かは
知りません

  He Ne Ar Kr Xe Rn この元素の覚え方 で そういうの 知ってる方
おられたら 教えてください

Aベストアンサー

私はこんなのを教えてもらいました。

(縦第1列)
H Li Na K Rb Cs Fr
変な淋病何故かゆい、ラブしすぎてフラフラ
(縦第15列)
N P As Sb Bi
ニッポンの朝は酢豚にビール
(縦第16列)
O S Se Te Po
オスの性器はテッポウだ
(縦第17列)
F Cl Br I At
ふっくらブラジャー私もアタック

ご参考まで

QRSA暗号について

下記のRSA暗号を解読して下さい

M3H9K7T7E

Aベストアンサー

できるかっ! ☆\( ̄  ̄*)バシッ

Q干支の覚え方

月の異名(睦月、如月、弥生・・・)の語呂的な覚え方は教えて!gooであったのですが、干支の覚え方(子、丑、寅・・・)の語呂的な覚え方はありませんでした。
やはり「ね、うし、とら、う、たつ・・・」の王道(?)で覚えなくてはならないのでしょうか。
もし語呂的な覚え方があれば教えてください。お願いします。

Aベストアンサー

同じ悩みを抱えていた方々が、過去にいらっしゃいましたね。(笑)
http://oshiete1.goo.ne.jp/kotaeru.php3?q=2455736
http://oshiete1.goo.ne.jp/kotaeru.php3?q=147875

やはり、前半後半それぞれ6個1組で覚えるのがよいんでしょうね。


もうご存知の情報でしてたら、すみません。

QRSA暗号で「互いに素」というのは

タイトルどおりです。どうも意味がわかりません。「Lと互いに素」とは、Lと何を互いっていうのでしょう。
例を使って解説してくれると助かります。
しかも、「Lと互いに素な自然数で最小のもの」を求めないといけないのですが・・・。

Aベストアンサー

> 例えばp=3,q=11でLCM(p-1,q-1)をLとする場合

LCMは最大公約数の事だったと思いますから、
2(=3-1)と10(=11-1)の最大公約数でL=2となり、

> Lと互いに素な自然数で最小のものは3

でOKだと思います。

Q炎色反応の覚え方

質問のとおりですが炎色反応のいい覚え方教えてください。前から知りたいと想っていました。それと元素記号の覚え方も教えてください。

Aベストアンサー

 いくつか回答は出ているようですが,過去にも類似質問がありましたのでご紹介しておきます。

「QNo.138 「水兵リーベ僕の船・・・」の続きをおしえて。」
 http://www.okweb.ne.jp/kotaeru.php3?q=138

「QNo.66819 炎色反応」
 http://www.okweb.ne.jp/kotaeru.php3?q=66819

「QNo.66898 元素の周期表」
 http://www.okweb.ne.jp/kotaeru.php3?q=66898

「QNo.83835 水兵リーベ・・・続きは?」
 http://www.okweb.ne.jp/kotaeru.php3?q=83835

「QNo.291920 ちょっとHな化学記号の覚え方」
 http://www.okweb.ne.jp/kotaeru.php3?q=291920


 他にもあるかもしれません。トップページで「炎色反応」や「元素記号」,「化学記号」,「周期表」等で検索してみると良いですよ。

参考URL:http://www.okweb.ne.jp/index.php3

 いくつか回答は出ているようですが,過去にも類似質問がありましたのでご紹介しておきます。

「QNo.138 「水兵リーベ僕の船・・・」の続きをおしえて。」
 http://www.okweb.ne.jp/kotaeru.php3?q=138

「QNo.66819 炎色反応」
 http://www.okweb.ne.jp/kotaeru.php3?q=66819

「QNo.66898 元素の周期表」
 http://www.okweb.ne.jp/kotaeru.php3?q=66898

「QNo.83835 水兵リーベ・・・続きは?」
 http://www.okweb.ne.jp/kotaeru.php3?q=83835

「QNo.291920 ちょっとHな化学記号の覚...続きを読む

Qy=x^(x^(x^(x^(x^(x^…の定義域は

y=x^(x^(x^(x^(x^(x^…の定義域は
[e^-e,e^(1/e)]と書かれていた本を昔読んだことがあります。
(うろ覚えですが)

最大値がe^(1/e)であることは容易に示すことができたのですが、
最小値がe^-eであることはどうやって示せばよいのでしょうか。

ご存じの方がおられましたらご教授いただきたく、よろしくお願いいたします。

Aベストアンサー

y=x^(x^(x^(x^(x^(x^…^(x^x)…)))))≡x^^x (0<x) (xは無限に並ぶ)…(A)
この関数で注意しなければならないことは
---------------------------------------------------------------
y=x^(x^(x^(x^(x^(x^…^(x^x)…)))))) (0<x) (xはn個並ぶ)…(B)
x→0の時 y→0or1となること

0^0^…^(0^0)=1 (0が偶数個並ぶとき)
0^0^…^(0^0)=0 (0が奇数個並ぶとき)
からx<<1のとき
(B)は多価関数となると推察される。
しかも xの数の偶数、奇数で関数が分かれる。
---------------------------------------------------------------
したがって(A)を考えるとき、偶数個のxを固まりにして考えないと上の性質を表現できない。
なので
(A)式の右辺をyで置換する場合
y=x^(x^(y)) (0<x≦e^(1/e))…(C)
とすることで(B)式のxの数の偶数、奇数の場合の性質を含ませることが出来る。
この(C)の関数は0≦x≦e^(-e)で多価関数になるので,この変域を除けば
定義域は次のようになる。
e^(-e)≦x≦e^(1/e)
この定義域でyの値域は
1/e≦y≦e
となります。

(C)のグラフを添付しておきます。

定義域の最小値はグラフからもわかりますが、(C)の関数式が多価関数にならない下限値
(y=1/eの時のx)として求めることが出来ます。

y=x^(x^(x^(x^(x^(x^…^(x^x)…)))))≡x^^x (0<x) (xは無限に並ぶ)…(A)
この関数で注意しなければならないことは
---------------------------------------------------------------
y=x^(x^(x^(x^(x^(x^…^(x^x)…)))))) (0<x) (xはn個並ぶ)…(B)
x→0の時 y→0or1となること

0^0^…^(0^0)=1 (0が偶数個並ぶとき)
0^0^…^(0^0)=0 (0が奇数個並ぶとき)
からx<<1のとき
(B)は多価関数となると推察される。
しかも xの数の偶数、奇数で関数が分かれる。
---------------------------------------------------------------...続きを読む

Q周期表のHな覚え方

一般的な覚え方は「水平リーベ僕の船・・・」だと思いますが、Hな覚え方があると聞きました。
知っていたら教えてください。

Aベストアンサー

参考URLを見ましょう \(^o^)/

http://www.d2.dion.ne.jp/~hmurata/goro.html

参考URL:http://www.d2.dion.ne.jp/~hmurata/goro.html

Qa^4+b^4+c^4≧b^2c^2+c^2…

文字は正とする。
a^4+b^4+c^4≧b^2c^2+c^2a^2+a^2b^2≧abc(a+b+c)
の証明をどうか教えていただけますようお願いいたします。

Aベストアンサー

実数x、y、zについて 絶対不等式:x^2+y^2+z^2≧xy+yz+zx ‥‥(1)が成立する。
何故なら、左辺-右辺=(1/2)*{(x-y)^2+(y-z)^2+(z-x)^2}≧0だから。等号はx=y=z ‥‥(2)の時。

>a^4+b^4+c^4≧b^2c^2+c^2a^2+a^2b^2

(1)でx=a^2、y=b^2、z=c^2 とするだけ。等号は文字が全て正から(2)より、a=b=c の時。

>b^2c^2+c^2a^2+a^2b^2≧abc(a+b+c)

(1)でx=ab、y=bc、z=ca とするだけ。等号は文字が全て正から(2)より、a=b=c の時 


人気Q&Aランキング

おすすめ情報