第41話 量子計算とRSA暗号と素因数分解

これまでの話
第1話 量子の夜明け
...
第36話 量子ビット(ビットについて)
第37話 量子ビット(量子状態をコンピュータに使う)
第38話 量子ビット(N個のビット（N量子ビット）を構成する)
第39話 量子計算と基本量子ゲート
第40話 量子フーリエ変換と量子ゲート

二つの素数p, q　二つの整数e, d

※modに関しては本記事にメモを置いておきました。

(e, n)を公開鍵、dを秘密鍵といいます。
nが因数分解出来てしまうと秘密鍵も判ってしまいます。本当に安全なのでしょうか？

nをNビットの整数とするとき効率の良い素因数分解アルゴリズムを使った場合の計算回数は概ね

となることが知られています。αはNに依存しない定数です。

1CPU辺り理論上Flops値は概ね「浮動小数点演算ユニットの数×クロック周波数」ですがもっと高速処理可能なスーパーコンピュータを使ったとすると、10310GFlopsで計算してもおよそ

もかかる事になります。

つまり、128ビットのRSA暗号を解読するのは事実上不可能と言えます。

ただし、これは大きな数の素因数分解が困難だという現状の話で、つまりアルゴリズムに依存しています。正確には「今のところ安全」というべきかも知れません。将来この素因数分解をいとも簡単に解くアルゴリズムが見つからないとは言えません。

しかし、量子計算が使われるとこの安全性は無いに等しいようです。それは何故なんでしょうか？量子計算はそれほど万能なのでしょうか？それとも巷で囁かれるように本当に早いのでしょうか？
次回からいよいよ量子計算の研究が加速されるきっかけになったとも言えるShorのアルゴリズムを見ながらこの疑問に迫ってみたいと思います。
※今のところRSA暗号や整数論等はここではこの程度で良いと思います。気になる方はネット上にも多くの情報もあるようなのでそちらをご覧下さい。

●メモ

基本性質