越境するコンピューター

越境するコンピューター ~日記~

新しいコンピューターとの付き合い方 〜コンピューターと意思決定と人間〜

コンピューターは因数分解が苦手

コンピューターは因数分解が苦手です。正確に言うと、どんな高速なコンピューターでも「適当な時間内に桁数の多い数の因数分解を完了することが出来ません」
どうして?

(1)しらみ潰し
(2)倍々ゲーム

しらみ潰し
因数分解をやる効率的な方法は無くて一つ一つの候補を試していく、いわゆる「しらみ潰し的なやり方」をする必要があります。

倍々ゲーム
でも高速なコンピューターならしらみ潰しを高速にやってくれるのでは?と思いますが例えば
30桁の因数分解だと毎秒1兆回の演算をするコンピューターでも300億年かかってしまいます[1]
1桁増える毎に指数的にしらみ潰しの数が増えていく、こういう処理はさすがにコンピューターでも適切な時間内に処理を完了することが出来ないのです。

桁数の多い数の因数分解をするのには膨大な時間がかかりますが、いったん答えが分かればそれが正しいかどうかはすぐに計算出来ます。

コンピューターで使われている暗号化この性質を利用しています。

今話題になっている量子コンピューター因数分解を適切な時間で出来る可能性があります。
これが実現する頃にはコンピューターの暗号化方法も新しいものに変わっているでしょう。