人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

量子コンピュータが出来るとRSAなどの素数暗号が簡単に解けてしまい、時代遅れになると聞きました。その理由について教えてください。

●質問者: countdown
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:時代遅れ 暗号 素数 量子コンピュータ
○ 状態 :終了
└ 回答数 : 6/6件

▽最新の回答へ

1 ● chipmunk1984
●25ポイント

http://www.nanoelectronics.jp/kaitai/quantumcom/3.htm

?u??q?R???s???[?^?v-?i?m?G???N?g???j?N?X

こちらの解説はいかがですか?

◎質問者からの返答

いいですね。

観測→収縮というのがどういう挙動なのか正直あまり分かりませんが、離散フーリエ変換がキーワードらしいということは分かりました。


2 ● NetVista
●20ポイント

http://pcweb.mycom.co.jp/news/2003/01/01/05.html

【レポート】量子コンピュータとは(1) - 暗号を短時間で破る超高速性能の秘密 (MYCOMジャーナル)

実際、p=64としたとき、高速フーリエ変換では1.18×10^21になるが、量子フーリエ変換では2080になる。現在のパソコンのレベルである1ステップを1nsで実行すると考えたとき、高速フーリエ変換では1万年、量子フーリエ変換では2μsとなる(!)。量子コンピュータが因数分解問題に対して極めて強力であることがわかる。


結論としては、けた違いに速いからなのです。

◎質問者からの返答

10^18位ですか。約100兆倍のスピードですね。とりあえず、原理が全く違うという感じでしょうか。


3 ● Seacolor
●18ポイント

http://www.itmedia.co.jp/news/0302/20/nj00_quantumcom.html

News:量子コンピュータとは?

こちらの記事が詳しいかと。

◎質問者からの返答

量子重ね合いと量子絡み合いがキーワード?


4 ● T
●18ポイント

http://www.f5.dion.ne.jp/~mirage/hypams04/quantum_2.html

量子暗号通信

質問の意図をはずしているような気がしますが一応…。


上記URLから抜粋

・量子コンピューターが開発された暁には、現在のスーパーコンピューターで数億年から

数十億年かかるRSA暗号の素因数分解問題を僅か数秒から数分で解読してしまう。

http://encyclopaedicnet.com/japan/e_/e_a_a_a_a_a_a_a__7.html

日本百科事典 - 量子コンピュータ

従来のコンピュータでは大きな計算量が必要であった素因数分解を、より少ない計算量で解くアルゴリズム(Shorのアルゴリズム)が知られている。そのため、量子コンピュータが実現されれば、素因数分解の困難性を利用したRSA暗号は安全性が崩れることになる。

◎質問者からの返答

とりあえず今日の分を全部あけます。


5 ● quantum
●25ポイント

http://jp.arxiv.org/pdf/quant-ph/9508027

PDF for quant-ph/9508027

リンクはP.Shorによる元論文です.


この論文を読むのが一番なのですが,なかなかに難しい論文なので,さらっと読みこなすのは辛いです.

chipmunk1984さんが挙げられているURLの記事はまぁまぁ良く書けているので参考になるでしょう.

ただ残念ながら,この解説は不十分で,これだけでは周期が求められていません.

「連分数展開」という手法を用いて周期を求める必要があります.

時々は正しくない周期が求められてしまうのですが,十分いい確率で正しい周期を求めることができます.

時々は最初からやり直さないといけませんが,そのおおよそのやり直し回数も含めて,

「多項式時間(「簡単に解ける」という事を数学的に言う用語です)」で因数を得ることができるということになります.


で,肝心な量子コンピュータの実現可能性ですが,予想では数十年後といわれています.


このShorのアルゴリズムをNMRで実行したという研究チームもあるのですが,ちょっと怪しいです.(そもそもレジスタの数が足りていないはずなので)

しばらくはRSA暗号は安泰です.もし時代遅れになったとしても量子暗号がありますし.


1-5件表示/6件
4.前の5件|次5件6.
関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ