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

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2005/04/26 17:12:06
  • 終了:--

回答(6件)

id:chipmunk1984 No.1

chipmunk1984回答回数790ベストアンサー獲得回数72005/04/26 17:19:54

ポイント25pt

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

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

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

id:countdown

いいですね。

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

2005/04/26 17:36:21
id:NetVista No.2

NetVista回答回数843ベストアンサー獲得回数02005/04/26 17:34:58

ポイント20pt

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となる(!)。量子コンピュータが因数分解問題に対して極めて強力であることがわかる。


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

id:countdown

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

2005/04/26 23:45:53
id:Seacolor No.3

Seacolor回答回数34ベストアンサー獲得回数12005/04/26 17:47:22

ポイント18pt

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

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

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

id:countdown

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

2005/04/26 23:49:17
id:tc96 No.4

T回答回数3ベストアンサー獲得回数02005/04/26 21:33:55

ポイント18pt

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


上記URLから抜粋

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

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

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

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

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

id:countdown

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

2005/04/26 23:56:34
id:quantum No.5

quantum回答回数2ベストアンサー獲得回数02005/04/26 22:28:29

ポイント25pt

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


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

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

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

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

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

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

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


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


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

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

id:Kumappus No.6

くまっぷす回答回数3784ベストアンサー獲得回数1852005/04/26 22:34:38

ポイント18pt

http://www.labs.nec.co.jp/innovative/E3/top.html

蔡 兆申, 中村 泰信, NEC Laboratories Innovative Engine: 量子コンピュータ: 会社概要 | NEC

「量子の重ね合わせ状態」を利用してひとつの量子で膨大な数の組み合わせの状態を表現することができるため、RSAなどの「総当り計算でいつかは解くことができるけど、今のノイマン型コンピュータでは計算量が膨大になるので解き終わるまでに時間がかかりすぎる」ような問題に適用できると言われています。

http://www.keyman.or.jp/search/30000190_1.html

量子暗号/キーマンズネット

というわけで通常の暗号はかなり強度が下がっちゃうので同時にこういう量子暗号というものも考えられています。

id:countdown

なんとなくイメージはつかめました。

回答してくださった皆さん、ありがとうございます。

2005/04/27 22:07:58

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません