暗号キー解析に必要な素因数分解

巨大な素数同士のかけ算は簡単でも、掛け合わした巨大な数を素因数分解するには膨大な時間がかかり現実的には不可能なので、掛け合わした数を公開鍵に、素因数分解した素数を秘密鍵にすることで、秘密鍵を持つものだけが暗号を解除できるというのが公開鍵暗号システムであり、現在の一般的な暗号システムとして、インターネットの世界の暗号化技術を支えています。

量子コンピュータの手にかかれば、暗号解読されてしまう。
そんな話を聞いたことがあるでしょうか。
その理由を簡単に説明します。

ただしすべてを量子コンピュータで行うというより、

（１）前準備（この処理は従来のコンピュータで行います）

$N$ を素因数分解したい値として

$x$ と $N$ の最大公約数が１（互いに素）である適当な $x$ < $N$ を選びます。
（この処理は従来のコンピュータで行います）

（２）本処理（量子コンピュータのおでまし）

この $x$ と $N$ を使って、 $N$ = $p$ $q$ なる素数 $p$ と $q$ を求めるには
以下のアルゴリズムを利用します。

$$ b = mod(x^a,N)$$

$$(a=0,\;1,\;\ldots\;\infty)$$

この結果の $b$ の値は $a$ の値に応じて一定の周期性を持つことがわかっています。
$a$ は量子ビットレジスタを初期化することで 0 ～ ∞ まですべての整数の可能性を持った状態にします。
$b$ は $a$ の可能性に応じた計算結果のすべての値を持つ状態になります。
そして、その状態はある周期性に従っています。
その周期性は $b$ を離散フーリエ変換することで得られます。

$$f(a)=x^a\;mod\;N$$

$$x<N$$

$7^a\;mod\;15$ を $(a\;=\;0,\;1,\;\ldots\;15)$で求めてみます。

周期性があります。周期は４です。

（３）後処理（この処理も従来のコンピュータで行います）

ここからは素因数分解のアルゴリズム最終段階、 $r $ を求めた周期として
従来のコンピュータで以下の処理を実行します。

$7^\frac{r}{2}-1=7^2-1=48$ と 15 の最大公約数を求め、3
$7^\frac{r}{2}+1=7^2+1=50$ と 15 の最大公約数を求め、5

めでたく15 = 3 × 5と素因数分解できました。

実際には求めた周期1回で素因数分解の解が求まるわけではなく、$x$ を変えて、数回繰り返すことで必ず解は求まる、と言われています。

IBMでは、15年ぐらい前に4ビットの量子レジスタを使って、15$(N)$ の素因数分解を行い、$x$ として 7 を使って 15 の素因数分解 3 × 5 を求めることに成功しました。
今は20ビットで成功しているようです。

量子コンピュータの真骨頂は、周期性を瞬時に求められるというところです。
スーパーコンピュータを使っても256ビットの場合、人の一生の期間では終わらないと言われている処理です。

処理（２）の量子コンピュータ的特徴を説明します。

特徴１

$$ b = mod(x^a,N)$$

$$(a=0,\;1,\;\ldots\;\infty)$$

この $a$ を格納する量子レジスタ
量子的操作を施すことで、$(a=0,\;1,\;\ldots\;\infty)$ すべての値の可能性を持つ状態になります。
こういう状態を作り出すところが量子コンピュータの真骨頂です。

特徴２

$$ b = mod(x^a,N)$$

$$(a=0,\;1,\;\ldots\;\infty)$$

結果 $b$ を格納する量子レジスタを先の $a$ と、量子的もつれ状態にします。
そして
$ mod(x^a,N)$ の演算を施した結果 $ b$ は

例えば先の例

下段のすべての可能性を持った状態になっているのです。たった1回の $mod(x^a,N)$ 演算で。これはレジスタ $b$ が、レジスタ $a$ と量子的もつれ状態にあるが故の出来事です。

256ビットの整数に対して、この計算結果を出すには、汎用コンピュータでは人の一生では足りない時間が必要です。

特徴３

最後にレジスタ $a$ で表すことが出来る全ての整数に対する $mod(x^a,N)$ の全ての結果を可能性として持つ $b$ の状態からその状態の周期性を求めるために、量子的離散フーリエ変換を施します。この演算装置をどうやって作るのかは難しすぎて説明できません。
離散的フーリエ変換を施されたレジスタ $b$ を観測することで、先の例に当てはめると、周期４が求まります。