ＲＳＡを破るプログラムを作ろう

要は素因数分解プログラムです
10^200クラスの数字をいかにして素因数分解するか
ちなみにＲＳＡの数字は全て２つの素数を掛けたもので出来てますので
スーパーコンピューターで１秒で10^20くらいの総当り計算をしても生きてる間に解けません

ちなみに人類は、これまでに10^174の数字を素因数分解しました
さらに上のレベルのプログラムを作りたい！

２

ttp://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html
このサイトの10^193の数字を解けば賞金$20,000

そういや RC5-64 はどうなった？と思ったら
とっくに解読できてたんだな。

今思えば、もの凄い電気の無駄遣いだったよ…＿|￣|○

>>4
http://pc3.2ch.net/test/read.cgi/jisaku/1047274285/l50

プログラムっていうか
そんなアルゴリズム考えられりゃ苦労しない
というより一生金に苦労しないんじゃないか

１０年かかるプログラムを作ったとする
１０人で１年
１００人で１ヶ月
１０００人で３〜４日か
２ｃｈの総力を使えば出来るな

これはやってみたい

>>7
家庭用コンピュータで10年?

ていうか、賞金を取ったとしてどうするんだ？

1000人で分けるつもりじゃないか?
一人$20で口座とか晒すやついるのか

RC5-72は全てのキーをチェックするのにあと1500年ほどかかるらしい。

>ちなみに人類は、これまでに10^174の数字を素因数分解しました
おなじ方法を使うとして 10^200 を処理するには上記の作業の 10^26 倍の時間が
かかると思われます。
任意の 10^174 程度の数字を１秒で素因子分解できるとしても 10^26 秒かかります。
これは 317京 0979兆 1983億 7645万 8650年かかるということです。
短いですね。

>任意の 10^174 程度の数字を１秒で素因子分解できるとしても 10^26 秒かかります
Why?
10^174程度と10^200はえらい違いだと思うんだが

>>13
違うよ。13 がナニを質問してるのかわからない。

>>10
いや、参加してたかどうかも確認できんから
どっかに寄付するのが一番

>>12
ちと違うな
10^200と言っても、二つの素数は10^100クラスの数字を２個掛け合わせたもの
そのどちらかを探すだけでいいので、10^13秒でいい

10^200 / 10^174 = 10^26
なんか計算間違ったかな？

>>16
あぁ勘違い。よく設問を読みましょう。
因子がわからないから因子を探しているんだから、10^200 を探さなきゃいけない。
ついでに。200桁とわかっているのだから199桁までは省略できると浅はかに考える人がいるかもしれないが
10^200 - 10^199 はほとんど 10^200 と大差がない。

>>18
エラトステネスの篩って知ってますか?
2つの素数をかけた合成数のもとになる素数を求めるのは
その合成数の平方根以下の素数で割れるか確認していくだけ十分ですが?
>>16
>二つの素数は10^100クラスの数字を２個掛け合わせたもの
揚げ足取るようですまないが
そのように範囲が限定されていればもっと短い時間で済むはず
(10^10クラスで割れても面白くないので実際そのくらいになるだろうが

10^87までに含まれる素数の個数と
10^100までに含まれる素数の個数の比は87:100ではない
個数の差はもっと少ないので10^13倍にも満たないと思われるかも知れないが

大きな数になればなるほどコンピュータの負担も大きくなるわけであるし、
そこまでの素数を列挙するのにかかる時間は指数的に増加していく
実際どの程度になるかは知らない

>>18
意味がわからん
>200桁とわかっているのだから199桁までは省略できる
何を省略するんだ？

脳みそとか？

途中変なとこあった。虫してくり。比のとこ

>>19
あなたがすごく賢い人に見える
ていうか、他が・・・

女陰吸うぶんかい？

一枚の紙（ディシュペーパでもいい）を面積が半分になるように１０回折ってみろ！

ディシュペーパ
翻訳
皿 林家
意訳
ハヤシライス

そのうち量子コンピュータができるんだから無駄な努力だ
紙と鉛筆で円周率の計算するようなもんだ

量子コンピューターが出てきても、必ずしも短い時間で
素因数分解できるようにはならないって誰かが言ってたよ。
今までのコンピューターと根本的に別物だから
単純じゃないって事なんだろうけど、さっぱり理解不能でした。
そこらへんのところ、詳しい人がいたら教えてちょんまげ。

>>27
良いアルゴリズムを作ろうという努力はないのか？
ひょっとしたら、今のパソコンでも一瞬で解ける方法があるかもしれないじゃないか

シャア風に言うなら
「今の環境でも簡単にＲＳＡを解ける方法もあるはずだ。それを探せ！」

>>29
その「あるかもしれないじゃないか」ってのが
まさに詭弁なんだが

そりゃまぁ、給料くれるなら幾らでも探しますけどね、少佐殿。

>>31
10^200クラスの素因数分解を高速に解くプログラムを作れたら
残りの人生は金に困らないのでは？

いや〜それよりは、近所の川で砂金取ったり、
沈没船とか、徳川埋蔵金を探した方が
期待値は大きいと思いますがね。

>>33
近所の川はともかく、沈没船や徳川埋蔵金はリスクがあるからな
投資金額がそうとうかかるだろう
その点、ＲＳＡは達成できなくても何も失わない

こういう方法もある
RSA=b^2-a^2（a,bは整数）
として考える方法
このbはRSAの平方根を少数以下ラウンドアップしたものより少しだけ多い数値になる事が多い
例えば10870974929で考えると
これの平方根を少数以下ラウンドアップすると104264
ここから探していく
ま、次の104265が正解なんだけど
正解がどうかはb^2-RSAが整数の２乗の数値になっていればいい
この場合、a=464
求める素数はb+aとb-aだから、103801,104729になるって感じ

まあ、この方法は２つの素数が近い数字であるほど早く見つかるんだけど
でも10^200クラスの数字になると、それでも10^70〜10^80回くらいの計算が必要になりそうだけどね
やっぱり総当り的な方法はダメかな

焼け石に水だけど
>>35の方法は
RSAに+1して4で割り切れる数字なら、bは奇数になる法則はある
これで計算時間は半減！！ｗ

間違った
4で割り切れる数字ならbは偶数
割り切れないならbは奇数

>>35の例だとRSAに１足しても４の倍数になってないからbは奇数

続き
さらに言うならRSAに１を足した数字が３の倍数なら、bも３の倍数になる法則もある
>>35の例だと、RSAに１を足すと３の倍数になってるから、bも３の倍数になる

これで計算速度は６倍・・・か？
まだまだやね

>>23
>>18に比べて>>19は一見まともっぽいこと書いてるけどてんででたらめだよ。
そもそもこんなデカイ数の素因数分解でエラトステネスの篩なんか使わないから
10^13とか10^26とかの議論はまったく意味がない。

新発見？
>>38の続き
bが奇数ならaは必ず偶数になる
しかも偶数でなんかの２乗になる数字は末尾がかならず０か４か６になる
末尾が２や８の数字はその時点でなんかの２乗ではない
だから、>>35の例だと、b^2の末尾が３か５か９にならにゃならん
でもなんかを２乗して末尾が３になる数字は無い
だからbの末尾は５か９だ

違った
b^2の末尾が５か９
だからbの末尾は３か５か７だね

>>3
アルゴリズムまで抑えられて2万ドル程度じゃ誰もやらないんじゃないの？

RSA-640の末尾は６６０９
b^2-a^2の末尾が６６０９

１を足しても４の倍数じゃないから、bは奇数
１を足すと３で割れるから、bは３の倍数

a^2の末尾が００と仮定すると、bの末尾は５３か０３
a^2の末尾が？４と仮定すると、b^2の末尾が？３になるのでこれは除外
a^2の末尾が？６と仮定すると、bは５の倍数

これでもまだまだ搾り足りないか・・・・

aの末尾は
04,96,00,20,40,60,80のどれかで間違いない

bの末尾は53,03,?5のどれかで３の倍数

もっと先に踏み込まないと無理か・・・

そうやって人生を無駄遣いしている暇があるのなら

コンピュータと素因子分解
ISBN4-7952-6889-4

でも読んでやり直しなさい。最新の技法ではないが、日本語だし、扱っている数学的記述も
けして高度ではない。高〜大３向け。

さらに搾った
aの末尾は004,204,304,504,704,804,196,296,496,696,796,996,00,20,40,60,80
のどれか

bの末尾は103,503,703,753,953,??5のどれかで３の倍数

まだまだ搾れそう

>>45
棒に振ってこそ人生　ｂｙ江田島平八

みんな頭いいな。

大学の講義で習ったにもかかわらず
「へぇ、すごいね。解けないんだ〜（´･∀･`）」
で済ましてた俺。
おまいらカッコイイぞ。

>>46
bの末尾353もあり
おそらく7353,2353の２通りだと思う
あと103のときは1103,6103だろう
この２つはaの末尾が00に対応

２ｃｈなら数で勝負できるだろ？

■暗号化スレ■
http://pc2.2ch.net/test/read.cgi/tech/1002736958/

暗号総崩れ-素数判定が多項式時間で可能
http://pc2.2ch.net/test/read.cgi/tech/1028877628/

>>52
意味ね
ＲＳＡ破られてないやん

結局沈む運命にあるスレか
上げておこう

ここじゃ無理

>>53
世界中の優秀な数学者が取り組んでも破られてないのに、
この板の人間ていどが破るのは土台無理ってこと。

物理的に破壊してみた
解読を目的にしなければ我がロイヤルハンマーの前に破れぬ物は無い

ハンマーなのに破れるのか

一ついい事を教えてやろう
末尾が９のＲＳＡは*****3 x *******3
もしくは******7 x ******7
の２通りしかない

末尾が１と９の組み合わせはあり得ない
だからってそれで解けるわけじゃないがな

11*19=209

東大生なら解けるんじゃないのか？
あるいは、河合模試全国１番とか、灘高生とか、ノーベルの野依教授とか。

ソニン数？

>>61
東大生に幻想を抱きすぎだよw

>>61
東大生なんて腐るほどいるじゃないか

まあ「東大卒」なんて毎年3000人以上いるわけで
珍しくとも何ともないわな。
ttp://www.u-tokyo.ac.jp/gaiyou/2223.html
ttp://www.u-tokyo.ac.jp/gaiyou/26.html

東大生全員の暗算でBrute Force Attackしても解けないだろうな、
それより公文式全会員導入のほうが可能性があるのではなかろうか。

人間の計算能力なんてそんなもんです。
つうか、計算機系の大学生ならRSAの理論くらい知ってるはずなんで、
なおかつ解かれてないのだから大学生は全員解けません、教授も解けません。
解く段階のスキルの無い高校生はそれ以前の問題ですよ。

人間の暗算は、20桁程度が限界らしいぞ。
パソコンの足元にも及ばない。

>>67
うちのパソコン20桁も計算できねーよ

>68
PCなら長大数使えや、
十露盤なら連結しろや。

>>69
人間でも同じ事だろ

560 デフォルトの名無しさん New! 04/03/03 00:56
東大生なら解けるんじゃないのか？
あるいは、河合模試全国１番とか、灘高生とか、ノーベルの野依教授とか、
ピーターフランクルとか。彼らはこのテーマを知らないだけで、やったら
解けると思うけど。。さすがに解くまで何億年とかジョークだろ。

>>71
学歴版のコピペか…
気に入った（・∀・）

>>70
人間の短期記憶ってそんなに覚えらんないから、
PCでいえば、メインメモリも仮想記憶も使い果たした状態にすぐなる、
外部記憶の十露盤使うか、筆算するかしかない。

短期記憶を増設するにはブラックジャック先生連れてこないと無理。

>>72
この板だった予感

睡眠不足。

>>75
　　　 ∧＿∧　 ／￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　　［（　・∀・）＜　F5は屁こいてさっさと寝ろ
|￣￣￣￣￣￣ ＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿
|　　|￣￣￣￣|　　|
|　　|　 ＠　 ＠|　　|
|　　|＠　 ＠　 |　　|
|　　|＿＿＿＿|　　|
|＿＿＿＿＿＿＿_|

>>74
まあわざわざ他板にこの板の名無しで書き込む人は稀だわな(削除依頼くらいか)。

世の中にはとっさに「2067年の8月17日は何曜日？」とか
「円周率の○○○桁目はいくつ？」とか聞かれて瞬時に
答えられる一種の天才もいるのだけど、そいつらがなぜ
瞬時に答えられるのかを追究してみるのも良さそう。

現在取られてるアプローチは、結局のところ指折り数えて
「時間かかるねぇ」とか「俺はより速く指を動かせる」って
言ってるだけの様に思える。

>>78
きっと何かの法則を見つけてるんだよな、前者は。
円周率はきっと覚えてるだけだ。だけっつってもすごいけど

>>78-79
ツェラーの公式
おいおい、このスレの奴らはこんな簡単な公式も知らないのかよ
さらしage

>>80
そういう問題じゃない。サヴァン症候群のやつ等はツェラーの公式に
基づいて算出している訳じゃない。

さらしあげたつもりが自分で自分をさらしあげてしまったｗ

分析的なものとして論じられている精神の諸作用は、
実は、ほとんど分析を許さぬものなのである。ただ結果から見て、
それらを感知するにすぎない。そのなかでもわかっていることは、
精神の諸作用を過分に身につけている人にとっては、
これこそなによりも生き生きとした楽しみの源泉である、ということだ。
だそうな、

イントロの一音聞いただけで曲名あてたり、
同じにしか見えない萌え絵の一部から作者わかったり、するヤツは
たまに会う程度にいるよな。

曜日を求める公式はツェラーの公式しかない訳じゃない。

dow(m,d,y){y-=m<3;return(y+y/4-y/100+y/400+"-bed=pen+mad."[m]+d)%7;}
みたいなトリッキーなソースもある。

結果どうすればｲｲの？
・アルゴリズムを作ればいい
・とにかく２つの素因数を求めればいい
どっちだ

> ・アルゴリズムを作ればいい
効率のいいアルゴリズムということなら、どっちでも好きなほうを
実現させておくれ。
どちらかというと前者のほうが簡単なのかもしれない。

>86
いや適当にその素因数を当てちゃった場合は賞金あるのかなと
思ってね。
「解きましたが方法は分かりません！！」・・・ある意味凄いがw

そういう時は「総当りで行きました」とだけ言うんだよ
アホ丸出し

>88
いやいや、今の総当りだと地球があるか太陽があるか分からんから・・・

Q.総当りのアルゴリズムを教えてくれ？
A, 脳内総当りです
~~~~~~~~~~~~~~~~~~~~~
以上でいいでつか？

かんぽき

地球シミュレータとか使えばいいんじゃないの？
それか、世界中のＰＣをネットでつなぐとか。ほら、子宮ガンの解析プロジェクト
を２ちゃんでやってるじゃん。

強制的に素因数分解に協力させるウイルスかけば、ばっちぐー。

>>91
むしろ暗号解読が先に行われていたかと。
以下のプロジェクトに参加よろ。

【分散処理】またーりdistributed.net【懸賞有】
http://pc3.2ch.net/test/read.cgi/jisaku/1076947927/l50
Distributed.net の２ｃｈチーム作ってみますた
http://pc3.2ch.net/test/read.cgi/jisaku/1047274285/l50
RC5 Cracking
http://pc.2ch.net/test/read.cgi/linux/1008690862/l50

age mahu

94 名前：デフォルトの名無しさん 投稿日：2004/03/15(月) 21:54
age mahu


95 名前：getsage 投稿日：2004/03/26(金) 11:41
藍


96 名前：デフォルトの名無しさん 投稿日：2004/03/26(金) 12:13
ニューラルネットワークに解かせるなんてどうよ？
板違いか。

保守

>>95
？？何が起こったんだ

>>97
3月下旬の鯖移転時に一部ログが消失した。>>95は、その補完。
当時は大騒ぎだったんだよ。

03/26 ログ消失事件
06/15 消えたログ補完 >>95
07/28 補完カキコにレス >>97

流石にRSAを破ろうって言う人たちの時間感覚は違うね。
このスレが1000行くまでには計算が終わるかもねw

>>中学の時授業中にひたすらやってましたが何か?

よーし、パパ(ry

age

hage

RSAを破りたいって時に素因数とか言ってる時点でもう破れないと思うが

>>104
どうして？

>>105:大原ゆき
どうして?

たぶんもうＡＲＰＡとかＮＳＡが破ってるよ。

10^200個の並列コンピュータがあればいちころ

素因数分解エンジン（多倍長整数演算をシングルクロックで可能なように
アキュムレータそのものを超拡張したカスタム数値プロセッサ）でも自作
すれば、あるいは・・・

>>109
じゃあとりあえずそいつの論理回路見せてくれ

並列コンピュータの応用問題で結構やられてると思うので、作ることが趣味という
ような人でなければ意味ないかもね。個別素子で組んでも今度は速度的に見合わん
だろうし・・・

所詮プログラマの分際で暗号を語るなど片腹痛いね

>>112
数学者ならいいでつか

>>113
所詮数学者の分際でプログラムを語るなど片腹痛いね。

所詮人間の分際で真理を語るなど片腹痛いね。

115のいう通りだぞ

神様ならいいでつか

>>92
＞強制的に素因数分解に協力させるウイルスかけば、ばっちぐー。
そういえば昔ググルさんに検索頼みまくるウイルスがあったなぁ。
ググルさんが沈没したのがただただ可笑しかったが。

つーか保守&age

人間の生き死にをどうこうしようなど、おこがましいとは思わんかね？

計算の途中の内部状態を出力して停止させることができるように
プログラムを作る。で、出力を読み込んで途中からまた計算できる
ように作っておく。

それをまずは現在のスーパーコンピュータで動かす。やがて技術が
進歩してもっと速いスーパーコンピュータが出てきたらプログラムを
停止させてそちらに持っていって動かす、というのを繰り返すと
意外と速く計算が終わるのではないか?

ああ、そうだ。CPUが暇になったときに裏でこっそり計算する
スクリーンセーバーを配布してやらせりゃいいんじゃないか?
って、もうとっくにこんな意見出てそうだな。

「量子コンピュータ」があれば「Ｓｈｏｒの素因数分解アルゴリズム」で実現出来る訳だが。

http://www.iftech.or.jp/center/kbes/dictonary/cnot_01.htm