アカウント名:
パスワード:
サイモン・シンの『暗号解読』読んでたら、「量子コンピュータが実用化されたら巨大な素数の素因数分解が超簡単にできるようになるので今使われてる暗号は軒並み解読されまくり。まあ量子コンピュータを使った暗号化なら破られないけど、過渡期はヤバイよねえ」みたいなこと書いてあったけど、これってドレくらいホントなの?ホントに量子コンピュータで今使われてるRSA暗号とかが解読されちゃう?
最近の多くの暗号(全部ではない)は巨大な数の素因数分解がめんどくさいと言う事実に基づいています。知られているアルゴリズムの範囲では、2進数でn桁の数字の因数分解にはおおよそ2n^1/3程度のオーダーの計算時間が必要で、これは桁数が増えるとあっという間に発散していくために大きな桁数の数字を使えば事実上逆演算が出来ません。
一方、量子計算の分野でよく知られたShorのアルゴリズムの場合、因数分解に必要な時間はおおよそn(だったかn2だったか)に比例する程度でしか無く、桁数nが膨大なものになってもそれほど必要な時間は増えません。このため実用的な時間で素因数分解を行う(=復号のための鍵を探し出す)ことが可能になります。
ただ、そのような演算を可能にするためには・十分なqubit数を持つ量子コンピュータの実現・計算時間の間コヒーレンスを保てる素子の実現が必要になりますので、今日明日にでもすぐどうにかなってしまう、というものではありません。というか実用的なqubit数の量子コンピュータが(技術的な問題として)作れるのかどうかも今のところよくわかっていません。現在のところ、10-qubitあたりが世界記録だと言っているレベルですので。これは言ってみれば演算器兼メモリが7 bitです、とか言うようなもので数の大きさ的にはお話になりません。
ただまあ、固体素子で長距離のコヒーレンス&相関を保つ方法を誰かが見つければ、一気にqubit数がふくれあがるかもしれませんが……
P≠NP予想を否定的に解くというアプローチもありますね。(P=NPだったらどうしようもありませんが)
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
あと、僕は馬鹿なことをするのは嫌いですよ (わざとやるとき以外は)。-- Larry Wall
暗号解読 (スコア:0)
サイモン・シンの『暗号解読』読んでたら、「量子コンピュータが実用化されたら巨大な素数の素因数分解が超簡単にできるようになるので今使われてる暗号は軒並み解読されまくり。まあ量子コンピュータを使った暗号化なら破られないけど、過渡期はヤバイよねえ」みたいなこと書いてあったけど、これってドレくらいホントなの?ホントに量子コンピュータで今使われてるRSA暗号とかが解読されちゃう?
Re:暗号解読 (スコア:2, 参考になる)
最近の多くの暗号(全部ではない)は巨大な数の素因数分解がめんどくさいと言う事実に基づいています。
知られているアルゴリズムの範囲では、2進数でn桁の数字の因数分解にはおおよそ2n^1/3程度のオーダーの計算時間が必要で、これは桁数が増えるとあっという間に発散していくために大きな桁数の数字を使えば事実上逆演算が出来ません。
一方、量子計算の分野でよく知られたShorのアルゴリズムの場合、因数分解に必要な時間はおおよそn(だったかn2だったか)に比例する程度でしか無く、桁数nが膨大なものになってもそれほど必要な時間は増えません。このため実用的な時間で素因数分解を行う(=復号のための鍵を探し出す)ことが可能になります。
ただ、そのような演算を可能にするためには
・十分なqubit数を持つ量子コンピュータの実現
・計算時間の間コヒーレンスを保てる素子の実現
が必要になりますので、今日明日にでもすぐどうにかなってしまう、というものではありません。というか実用的なqubit数の量子コンピュータが(技術的な問題として)作れるのかどうかも今のところよくわかっていません。現在のところ、10-qubitあたりが世界記録だと言っているレベルですので。
これは言ってみれば演算器兼メモリが7 bitです、とか言うようなもので数の大きさ的にはお話になりません。
ただまあ、固体素子で長距離のコヒーレンス&相関を保つ方法を誰かが見つければ、一気にqubit数がふくれあがるかもしれませんが……
Re: (スコア:0)
P≠NP予想を否定的に解くというアプローチもありますね。
(P=NPだったらどうしようもありませんが)