この記事は Fujitsu Advent Calendar 2023 13日目の記事です。
量子計算機シミュレータを用いて大規模な素因数分解実験を行ったので、改めて情報を整理したいと思います。
背景
素因数分解 vs 計算機
素因数分解とは、合成数を素数の積に変形することです。$15$ や $21$ のような小さい合成数ならば暗算でも素因数分解できますが (ちなみに $15=3 \times 5, 21=3 \times 7$)、これが $20231213$ や $2023121320231223$ のように大きくなってくると暗算では厳しくなってきます。それでも通常の計算機を使えばそれぞれ
$20231213=53 \times 89 \times 4289$
や
$2023121320231213=1229 \times 1646152416787$
のように素因数分解できます。しかしこれが $200$ 桁ともなると、通常の計算機を使っても素因数分解は難しくなってしまいます。このような「巨大な合成数の素因数分解は極めて難しい」という性質を利用して公開鍵暗号やデジタル署名が開発され、インターネットの安全性を支えるために世界中で広く使用されるに至っています。
なお通常の計算機を使った具体的な素因数分解アルゴリズムや素因数分解の記録については、私が以前に書いた「素因数分解の現状 (古典計算編)」という記事を参照ください。
素因数分解 vs 量子計算機
ところが量子計算機が登場すると状況が一変します。1994 年に Peter Shor が開発した Shor アルゴリズムを用いると、量子計算上で素因数分解を簡単に解けるようになるのです。合成数の大きさを大きくしたとしても、Shor アルゴリズムが必要とする量子計算のリソースはあまり増加しないため、現在使用されている公開鍵暗号やデジタル署名は Shor アルゴリズムによって解読されてしまうことを意味しています。