富士通、専用ハードによる素因数分解に世界で初成功 51
ストーリー by yosuke
量子計算機でなくても 部門より
量子計算機でなくても 部門より
anthema1曰く、"
ITmediaの記事によれば、情報通信研究機構(NICT)、富士通、
富士通研究所が世界で初めて専用ハードウェアによる素因数分解に成功したとのこと(NICTのプレスリリースと富士通のプレスリリース)。
素因数分解のアルゴリズムは一般数体ふるい法をベースとし、ふるい処理を専用ハードウェアで行い、線形代数処理と平方根計算処理をソフトで行うという構成。bn±1(b=2, 3, 5, 6, 7, 10, 11, 12)で表される整数を素因数分解するプロジェクト、Cunningham Projectから未分解の423ビット(10進法で128桁)の数を選び、システムを約1カ月間稼働させ、62桁と65桁の素因数への分解が完了したという。"
誤記？ (スコア:5, 参考になる)
＃NICT・富士通両方共に
手元で計算してみたところどうやら
24185630183133843753778789809606269235981954330361986407441038977
は
241856301831338437537787898096062692359819543303619864074410382977
の誤記のようです。
#多分プレスリリース用の資料をおこす際に誤記しただけだと思うのでID
// ＭＺＫ
Re:誤記？ (スコア:1, おもしろおかしい)
って思ったら、他方で割り算したのか。
びっくらこいた。
Re:誤記？ (スコア:3, すばらしい洞察)
Re:誤記？ (スコア:1)
初めて成功 (スコア:4, すばらしい洞察)
ビット数が少なくてもよいなら、専用ハードウェアを作ることくらい、誰にでも作ること自体は可能なのは自明でしょう。
非常に大きな数について成功したとか、高速な処理に成功したとか言うならわかるが。
これは単に「世界で初めてやってみました」と言うべきだ。
Re:初めて成功 (スコア:1, すばらしい洞察)
そういう評論家気取りが「誰にでも出来るだろ」って
いって手を出さないところに手をだしたのはエラいん
じゃないですかね。
理論的には誰にでも作れること自体は自明であっても、
実際に作るにはいろいろなノウハウが必要かもしれない。
それを実際に作って会得した分だけ、机の前でグダ
グダと理屈だけを捏ね繰り回して人を小ばかにしてい
る評論家気取りよりはよほど頑張っていて、褒めるに
値すると思うんだが。
Re:初めて成功 (スコア:1, すばらしい洞察)
「解かれていなかった素因数分解問題を専用ハードウェアを用いた方法で解くことに世界で初めて成功」なら妥当。
Re:初めて成功 (スコア:1)
要するに「発想」に対する保護概念が無く、技術的困難を伴わなければならないらしい。
きっとこの富士通の快挙に驚けない人は発想という人間の大事な「発想」や「行動」と言うスキルの価値を理解出来ない人なんだろうな。
#1年半後に発想の妙だけで何ら新規性もない論文を書こうとしているから頑張って擁護してみたけど微妙な気がする
ヽ(・Д . )ﾉ
Re:初めて成功 (スコア:0)
> いって手を出さないところに手をだしたのはエラいん
> じゃないですかね。
トリビアの種はそういうところありますよね.
というわけでトリビアの種と同等にえらいという感じだと思います.
Re:初めてやってみたってかんじ (スコア:1)
Re:初めて成功 (スコア:0)
Re:初めて成功 (スコア:0)
ついでに社員が働かないのも世界一ぃぃぃぃ
---
すみません。いろいろ言いたい事があったので
Re:初めて成功 (スコア:1)
工作員は書き込みできるサイトがあれば工作に走ってしまうのです。
影響力が実際あるかないかはこの際どうでもよい。
Re:初めて成功 (スコア:1)
あぁ、上るじゃなくて登るだぁ。
#自己指摘レスなのでAC Elbereth
Re:初めて成功 (スコア:0)
冒険を征服するのとは違うと思うのですが。
他に出来る人がいないくらい、実現するのが非常に難しい実験ってのは、追試も非常に困難でしょうから、実験としては事実上価値が無いような…
Re:初めて成功 (スコア:0)
やれ、「○○アルゴリズムをハードウェア化しました」だの、次は「○○’アルゴリズムをハードウェアかしました」だの、似たような論文を山ほど出してくる人とかいるじゃない。そういうのの査読がまわってくると、マジうんざりするよね。
ハードウェア化なんてきょうび流行らないっての。ハードウェア化するってのは、速いか速くないかに尽きるわけ。もちろん、本当にコストパフォーマンスが高ければビジネスとして成功する分野もあるよ。
ビジネスにのらない、対
Re:初めて成功 (スコア:0)
ところで、あんたハードウェアやったことないだろ
ハード化で得られる知見といえばネガティブなものばかりなんだけどさ、そこが大事なのよ
もっともFPGAやリコンフィギュアラブルでハードを作りましたというのはありえないというのは賛成
Re:初めて成功 (スコア:0)
データフローマシン第二部だな
量子コンピュータじゃないのね (スコア:2, 参考になる)
ちゃんと読むと，今回はTAOだった方のNiCTの成果，ですね。暗号強度と処理速度はトレードオフの関係にありますが，むやみと暗号強度を上げなくても「この暗号を解くのにはざっと n 億円必要だけど本当にそんな暗号が必要なんですか？」という指針が得られるのはかなり役立つと思います。
Shorのアルゴリズムについての一次資料はWikipedia:量子コンピュータ [wikipedia.org]に原論文へのリンクがありますのでそちらを読まれることをお勧めします。
Re:量子コンピュータじゃないのね (スコア:2, 参考になる)
Wikipediaにもありますが、たかだか15の因数分解が実現できた程度。
しかも、これは溶液系の話で、実用性が高いと見込まれる固体系では、
qubitの実現が精一杯。
馬鹿にでもわかるように (スコア:1)
なんとなくすごいんだろうということはわかるんだけど。
--- show mpls ldp neighbor
Re:馬鹿にでもわかるように (スコア:4, 参考になる)
「素因数分解は難しい」というのを安全性の根拠としています。
素因数分解が出来てしまう、というのはRSAが破られるかも、ということなのです。
# それがうれしいか悲しいかは分かりませんが・・・・
1を聞いて0を知れ!
Re:馬鹿にでもわかるように (スコア:2, おもしろおかしい)
よかった。
このあたりから、数学の偏差値が33を超えなくなりました。
コンピュータにも難しいなら、できなくてもよいや。
お母さん、そんな僕ですが、今はプログラマとして頑張ってます。
Re:馬鹿にでもわかるように (スコア:2, おもしろおかしい)
元コメントがジョークだと言うのは百も承知で、ツッコミするのをお許しを。
コンピュータにも簡単にできることしかできないのなら、遠からず職を失いますよ？
Re:馬鹿にでもわかるように (スコア:3, 参考になる)
素因数分解の困難さに依存した暗号方式（RSAなど）が
よりクラックされやすくなったといえるのではないでしょうか？
http://x68000.q-e-d.net/~68user/net/crypt-2.html [q-e-d.net]
Re:馬鹿にでもわかるように (スコア:3, 参考になる)
リリースから引っ張ると
423ビットってどんなもんじゃいと思ったら
http://www.math.okstate.edu/~wrightd/numthry/rsa129.html [okstate.edu]
1994年にPCクラスタで600台（以上）、8ヶ月で425bitが解かれてる。"5000 mips years"だそうです。
でも今時のCPUをぐぐってみたらCore2 Duoが2万mipsくらいだそうだから3ヶ月で解けちゃいそう。専用ハード使って高々3倍なのかあ。
DAPDNA-2は面白いことできます的な広告の意味なのかなコレ。
後疑問なのが「最大768ビットの数まで入力可能」って普通の1024ビットが通らないじゃんね。
Re:馬鹿にでもわかるように (スコア:5, 参考になる)
117桁のGNFSが大体40時間くらい、140桁のGNFSが(3台の2xXeon 2GHzで)延べ360時間くらいなので、128桁のGNFSはCore2Duoだと遅くても2週間くらいで完了するかもしれません。
あと、たとえ1024ビットが通ったとしても現在のアルゴリズムと実装では結果が出るまで途方もない時間とメモリを必要とするので、ビット数を増やせてもあまり嬉しくありません。
＞DAPDNA-2は面白いことできます的な広告の意味なのかなコレ。
のような気がします。
Re:馬鹿にでもわかるように (スコア:0)
元コメントは指数スケールが理解できてなくて、1024ビットの計算は768ビットの計算の4/3程度しか難しくないとか思ってたんじゃないでしょうか。
これを「馬鹿にでもわかるように」説明するのはかなり困難ですね。
# 1日で2つに分裂する蓮の葉を1枚池に入れたら15日で池の半分を覆っていた。池全体を覆うようになるのは何日後か
Re:馬鹿にでもわかるように (スコア:0)
Re:馬鹿にでもわかるように (スコア:0)
Re:馬鹿にでもわかるように (スコア:1)
しかし、この専用ハードってのはどれぐらいの
大きさなんでしょうね。
500台のクラスタとかよりは圧倒的にちいさい
んでしょうけど
--- show mpls ldp neighbor
Re:馬鹿にでもわかるように (スコア:1)
Re:馬鹿にでもわかるように (スコア:0)
Re:馬鹿にでもわかるように (スコア:0, おもしろおかしい)
ええー、そんなひとがスラドに出入りしてるんですか!?
アレゲなひとにとって数学は強敵（と書いて「とも」と読む）ですよ。
つまり、 (スコア:1)
それとも、より強力なセキュリティ・チップが開発されることに繋がる成果があったと言うことですか？
Re:つまり、 (スコア:3, 参考になる)
高校数学で遊ぶ公開鍵暗号RSA [faireal.net]
公開鍵(の一部)は、2つの素数の積から成り立っています。
公開鍵から元の素数を取り出すこと(因数分解)ができれば、暗号を解読することができます。
今回の研究は、これくらいの鍵にはこれくらいの期間が必要だから、鍵を交換する間隔はこれくらいにすればよいかも。。。という目安になることをねらっているらしいです。
Re:つまり、 (スコア:2, 興味深い)
いいえ。
10進200桁の因数分解が既に(ハード的にではなく)行なわれています。しかし、ソフト/ハードとも現在推奨されている1024bitにはまだ届いていません。
強度を下げることに繋がる成果、あたりですかね。
Re:つまり、 (スコア:1)
今回の話は，「素因数分解を現在の知識+技術で破ろうとしたらどれだけ時間・コストが掛かるか」を示し，それに基づいて「今後の高速化により，何時頃1024bitのRSAが現実的に破れるようになるか」を研究する，のを目的にしてるんじゃないですかね．
昔はDESのクラッキングコンテストなんかがあって，brute-forceな解析が現実的な時間・コストで可能なことが(Distributed.netやEFFのDES Crackerによって)示されましたが，発想としてはそれに近いのではないかと．
＃理論科学と実験科学と言い換えてもよいのかも
専用ハードウェアということは (スコア:1)
どのような回路か興味があるけど、なんとなく既存のチッフを使っただけの回路のような気もする。
Re:専用ハードウェアということは (スコア:1)
むしろこちら [srad.jp]で言われているようにコンフィギュアブルプロセッサのデモ用なら, 実例ということでユーザにはソース提供されるんじゃないですかね.
素数を数えて落ち着くんだ！ (スコア:0)
Re:素数を数えて落ち着くんだ！ (スコア:5, おもしろおかしい)
Re:素数を数えて落ち着くんだ！ (スコア:5, おもしろおかしい)
『完全数』とは、その数自身を除く正の約数の和が
その数自身と等しい自然数……
私に充足感を与えてくれる……
6……28……496……8128……33550336……8589869056……137438691328……
落ち着け……『友愛数』を数えて落ち着くんだ……
『友愛数』とは、異なる2つの自然数の自分自身を除いた約数の和が
互いに他方と等しくなるような数……
私に隣人愛を与えてくれる……
220、284……1,184、1,210……2,620、2,924……5,020、5,564……
6,232、6,368……10,744、10,856……12,285、14,595……17,296、18,416……
63,020、76,084……66,928、66,992……
Re:素数を数えて落ち着くんだ！ (スコア:2, おもしろおかしい)
ねむい、、、、ぐーすー。
新しい技術を研究し (スコア:0)
プラズマTVとかは何だったんだ