2014情報科学概論 第13回講義 量子計算機がRSA暗号を破れ るという話:Shorのアルゴリズム 2014.7.10 田中美栄子 RSA暗号方式は広く使われている • Rivest,Shamir, Adelman 3名はMITを辞 め,RSAという会社を作ってRSA暗号利用を 管理している。コンピュータの高速化や,アル ゴリズムの発見により簡単に破られないよう, 鍵の長さを管理している • 1994年,Peter Shor は量子アルゴリズム を使って因数分解を高速に行うアルゴリズム を発表し,世界の寵児となった • しかしこれを使うには量子コンピュータが必要 なため,今のところ実用化はされていない RSA暗号の弱み(前回の復習) • 公開鍵niは大きな2素数pとqの積として作り, 同時にpとqから秘密鍵diを作って使用する • 公開された鍵(e,ni)を因数分解できる人がい れば,原理的にdiを算出できるが,因数分解 に時間がかかるため安全性が保たれる • 非常に高速なコンピュータを用いて因数分解 するか,因数分解の高速なアルゴリズムがわ かればこの暗号は破られる(WAR GAMEと いう映画では因数分解で暗号解読を試みる) 高速な因数分解がRSA暗号を破る • 公開鍵nを高速に因数分解できれば破れる • Shorの因数分解アルゴリズムは次の通り 1) 鍵nより小さく,nとは互いに素な(つまり共 通の因数を持たない)整数yを選ぶ 2) yr =1 (mod n) となるような最小のrを 見つける(このrをオーダーという) 3) このrが偶数なら,x=yr/2を求め,x+1とx-1 が因数の候補となる 4)成功すれば終了。失敗すれば1)からやり直 す,つまり先程とは別のyを選んで繰り返す アルゴリズムの使用例 • 15を因数分解する場合, • y=2なら互いに素 • 2の2乗,3乗まではmod 15で1とはならない。 4乗なら16だから15で割れば1となるのでr=4 • このrは偶数であるのでr/2=2 • x=22=4なのでx+1=5またはx-1=3が因数の 候補となる • 15=3*5ができた! 量子コンピュータを使う場所 • Shorの因数分解アルゴリズム 1) 鍵nより小さく,nとは互いに素な(つまり共通 の因数を持たない)整数yを選ぶ 2) yr =1 (mod n) となるような最小のr (オーダー)を見つける ←この部分 3) このrが偶数なら,x=yr/2を求め,x+1とx-1 が因数の候補となる 4)成功すれば終了。失敗すれば1)からやり直 す,つまり先程とは別のyを選んで繰り返す 量子コンピュータはいつできるのか • • • • • 1~2ビット程度なら既にできている 数十ビットにするのは大変困難(らしい) 成功すれば新聞に大きく出る 成功しなくても新聞で騒がれている 今から20年くらいは無理と思われている そんなに困難な理由とは? ノイマン計算機とは原理的に異なる • 2値でない(0と1の状態の「重ね合わせ状態」 が単位となる) • 重ね合わせ状態とは0の状態と1の状態の一 次結合である:重ね合わせ状態=a*0+b*1 • ここで係数aとbは複素数 • 重ね合わせ状態には0が確率|a|2で1が確率 |b|2で含まれる。ここで|a|2+ |b|2=1を満たす • 重ね合わせ状態一つが量子ビット=q-bitとな る。 量子計算機はもともと超並列計算機 • 量子ビットをn個繋げるとn個のq-bitとなるが,n個そ れぞれが0と1の一次結合であるため,展開するとn 個全部0の状態からn個全部1の状態まで,全ての 状態が揃っている n-qbit:(a*0+b*1)((a*0+b*1)・・(a*0+b*1) = c1*0*0*・・*0+c2*1*0*・・*0+c3*0*1*・・*0+・・・ck *1*1*・・*1 つまりn個のq-bitは2n個の状態を同時に保持している のと同じであり,指数関数的に大量の計算ができる。 つまり同じ仕事なら超短時間でできる 量子計算機の問題点 • 何故簡単にできないのかは原理的な構造の 問題である • 計算単位であるq-bitはそれぞれが(電子や 原子1個とかの)量子力学的な状態であり, マクロな力によって簡単に壊れてしまう 最近の話題 • グーグルが2013年5月16日,量子コンピュータを駆使し てAI(人工知能)を研究する「量子AI研究所(Quantum Artificial Intelligence Lab)」を立ち上げた. 今後,米航空宇宙局 (NASA)などと協力 し,量子コンピュー ティングで機械学習 の技術などを研究開 発するという. 〔PHOTO〕gettyimages • 今回,Googleが採用した量子コンピュータは,カナダの 「D-Wave Systems」というベンチャー企業が開発したもの • 2012年2月にIBMの研究者は「量子コンピュータが実現さ れるのは早くても10~15年先」と語っている現状である. そんな中,あまり有名でないカナダのベンチャー企業がい きなり,AI開発に使えるような本格的な量子コンピュータを 製品化したと発表しても,科学者をはじめ専門家は俄かに は信じ難く,懐疑的な声も. http://www.dwavesys.com/en/dw_homepage.html はたしてD-Wave Systemsは 量子コンピュータを作ったのか? • 「最適化問題」と呼ばれる特殊な分野に限って,DWave Systemsの"量子コンピュータ"は従来型コン ピュータの3600倍の処理速度を達成したという. • 批判的な一部の専門家は,「ある種の温度現象( 恐らく超伝導のことを指している)を利用すれば, コンピュータの高速化は可能であり,D-Wave Systemsのやり方は,むしろそちらではないか」と 見ている. はたしてD-Wave Systemsは 量子コンピュータを作ったのか? • 「量子アニーリング」という、東京工業大学・教授の 西森秀稔氏と、門脇正史氏の二人が共同で提案し た理論を採用している. 量子ゲート 広く使われている汎用デジタル・コンピュータの基本素子である 論理ゲートを、量子力学の原理で再構成したもの. 量子アニーリング 一種のアナログ計算方式。汎用のデジタル計算方式に比べて 応用範囲が狭い。実用的な量子コンピュータを開発しようと する試みはほとんどなかった。 • いままでD-Wave Systemsはきちんと論文を 出していなかった。 • 2012年8月に(D-Waveが)128 qubitのマシ ンを作って,「それが動作する」という論文が 『ネイチャー』や『サイエンス』のような一流誌 に掲載される. • 『投資家から資金を調達するために大口を叩 く』ベンチャー企業の常套手段という評価か ら・・・ひょっとして・・・
© Copyright 2025 ExpyDoc