こんにちは、みっちゃんです。

以前の記事で、暗号化技術である「共通鍵暗号方式」「公開鍵暗号方式」について紹介しました。

今回の記事では、暗号化の際にやっていることを、中学校で習う「因数分解」を使って解説したいと思います。

目次（まとめ）
- 因数分解は、古典コンピュータが苦手にする問題の１つ
- 暗号化のアイデアは因数分解から生まれた
- 因数分解は、量子コンピュータが得意にする問題の１つ
- 参考文献

因数分解は、古典コンピュータが苦手にする問題の１つ

古典コンピュータとは、現在主流のコンピュータである、古典力学に従うノイマン型コンピュータのことです。

古典コンピュータは、とても便利な機械であることは、みなさんご存知だと思いますが、苦手にしている問題がいくつかあります。

その１つが、私たちが中学校で習う「因数分解」です。

例えば「91を因数分解しなさい」といった問題です。

この場合、答えは「7×13」になるのですが、桁数が増えるほど、難しくなることが予想できます。

「6059を因数分解しなさい」
「11928311を因数分解しなさい」

こうなると、私たちはもちろん、コンピュータでも難しい問題となります。

暗号化のアイデアは因数分解から生まれた

上に示した問題も、以下のように少しヒントが与えられるだけで、簡単な問題に早変わりします。

「6059を因数分解しなさい。因数の１つは73です。」
「11928311を因数分解しなさい。因数の１つは3331です。」

暗号化のアイデアは「11928311を因数分解できなければ、情報を読み取ることはできない」ということから生まれています。

ただし、情報の受け取り手と送り手が「73」という１つの因数を知っていれば、情報を読み取ることは簡単です。

実際の暗号化には、桁数が多い数が使用されていて、「桁数が大きい数の因数分解は事実上不可能」という前提があります。

因数分解は、量子コンピュータが得意にする問題の１つ

古典コンピュータが苦手にしている「因数分解」ですが、量子コンピュータは得意にしています。

古典コンピュータは1000桁の数字の因数分解は不可能とされていますが、量子コンピュータは数分で解いてしまうそうです。

つまり、「桁数が大きい数の因数分解は、古典コンピュータでは事実上不可能」という前提にたった現在の暗号化技術が、量子コンピュータの登場で破綻してしまうということを意味しています。

ただし、量子コンピュータがまだ実用段階にはないので、喫緊の問題というわけではありません。

量子コンピュータの登場で、いろいろな技術が発展していくのは間違いないですね。

参考文献

竹内繁樹「量子コンピュータ」講談社ブルーバックス