2014情報科学概論
第13回講義
量子計算機がRSA暗号を破れ
るという話：Shorのアルゴリズム
2014．7.10
田中美栄子
RSA暗号方式は広く使われている
• Rivest，Shamir, Adelman ３名はMITを辞
め，RSAという会社を作ってRSA暗号利用を
管理している。コンピュータの高速化や，アル
ゴリズムの発見により簡単に破られないよう，
鍵の長さを管理している
• 1994年，Peter Shor は量子アルゴリズム
を使って因数分解を高速に行うアルゴリズム
を発表し，世界の寵児となった
• しかしこれを使うには量子コンピュータが必要
なため，今のところ実用化はされていない
RSA暗号の弱み（前回の復習）
• 公開鍵niは大きな２素数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）成功すれば終了。失敗すれば１）からやり直
す，つまり先程とは別のyを選んで繰り返す
アルゴリズムの使用例
• 15を因数分解する場合，
• y=2なら互いに素
• 2の２乗，３乗まではmod 15で１とはならない。
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）成功すれば終了。失敗すれば１）からやり直
す，つまり先程とは別のyを選んで繰り返す
量子コンピュータはいつできるのか
•
•
•
•
•
１～２ビット程度なら既にできている
数十ビットにするのは大変困難（らしい）
成功すれば新聞に大きく出る
成功しなくても新聞で騒がれている
今から２０年くらいは無理と思われている
そんなに困難な理由とは？
ノイマン計算機とは原理的に異なる
• ２値でない(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はそれぞれが（電子や
原子１個とかの）量子力学的な状態であり，
マクロな力によって簡単に壊れてしまう
最近の話題
• グーグルが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のマシ
ンを作って，「それが動作する」という論文が
『ネイチャー』や『サイエンス』のような一流誌
に掲載される．
• 『投資家から資金を調達するために大口を叩
く』ベンチャー企業の常套手段という評価か
ら・・・ひょっとして・・・

ｽﾗｲﾄﾞ ﾀｲﾄﾙなし