量子コンピュータの話:RSA暗号は破れるか?

Document technical information

Format pptx
Size 1.4 MB
First found May 22, 2018

Document content analysis

Category Also themed
Language
Japanese
Type
not defined
Concepts
no text concepts found

Persons

Organizations

Places

Transcript

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のマシ
ンを作って,「それが動作する」という論文が
『ネイチャー』や『サイエンス』のような一流誌
に掲載される.
• 『投資家から資金を調達するために大口を叩
く』ベンチャー企業の常套手段という評価か
ら・・・ひょっとして・・・

Similar documents

×

Report this document