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

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

実際、p=64としたとき、高速フーリエ変換では1.18×10^21になるが、量子フーリエ変換では2080になる。現在のパソコンのレベルである1ステップを1nsで実行すると考えたとき、高速フーリエ変換では1万年、量子フーリエ変換では2μsとなる(!)。量子コンピュータが因数分解問題に対して極めて強力であることがわかる。

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

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

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

上記URLから抜粋

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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