この記事は Fujitsu Advent Calendar 2024 の 1日目の記事です。

はじめに

素因数分解と古典計算機

素因数分解とは、合成数の整数を素数の積に変形することです。
$15$ や $21$ のような小さい合成数ならば
暗算でも素因数分解できますが (ちなみに $15=3 \times 5$, $21 = 3 \times 7$)、これが $241201$ のように大きくなってくると暗算では厳しくなり、さらにお大きくなってくると通常の計算機をでも素因数分解は難しくなります。つまり「巨大な合成数の素因数分解は難しい」という性質があり、
この性質を利用して RSA 暗号や RSA 署名などの公開鍵暗号・デジタル署名が開発され、インターネットの安全性を支えるために世界中で広く使用されています。

なお通常の計算機を使った具体的な素因数分解アルゴリズムや素因数分解の記録については、私が以前に書いた「素因数分解の現状 (古典計算編)」という記事を参照ください。

素因数分解と量子計算機

ところが量子計算機が登場すると話ががらっと変わります。計算機科学者である Peter Shor が開発した「Shor のアルゴリズム」という量子計算機用のアルゴリズムを用いると、素因数分解を簡単に解けることが知られています。

ここで「簡単」とは「素因数分解に必要な計算リソースが合成数の多項式関数となる」という意味で、「一瞬」を意味するわけではありません。さまざまな研究によって巨大な合成数(例えば2048ビット合成数)を Shor のアルゴリズムによって素因数分解に必要な量子計算機のリソース量が見積もられていますが、文字通りケタ違いに莫大なリソースが必要であることがわかっており、巨大な合成数を素因数分解できるような量子計算機の登場はまだまだ未来の話と考えられています。

しかし量子計算機を使って素因数分解するには別の方法も考えられるわけで、最近は Shor のアルゴリズム以外の素因数分解法の研究が進んでいます。本稿ではその試みの一つとして、Schnorr の素因数分解法を量子計算機用に変形した素因数分解法 (本稿ではまとめて「Schorr型の素因数分解法」と呼びます) を紹介します。

Schnorr 型の素因数分解法

Schnorr の素因数分解法

暗号学者である Claus Schnorr は 2013 年に古典計算機による新しい素因数分解法を提案しました。この素因数分解法の特徴は解きたい素因数分解問題を関連する格子上の最近ベクトル問題 (CVP; Closest Vector Problem) に変換し、CVP 問題を解くことで素因数分解を実現するという点です。

素因数分解したい合成数を $N$ とするとき、Schnorr の素因数分解法の目標は $x^2 \equiv y^2 \pmod{N}$ となる整数 $x, y$ を見つけることです。ここで $\equiv$ は $N$ で割った余りが等しいことを表す記号です。このとき $x^2-y^2$ を $N$ で割った余りは $0$ になる、つまり $x^2-y^2=(x-y)(x+y)$ は $N$ の倍数となるので、運が良ければ $\gcd(x-y,N)$ から $N$ の素因数分解を求められます (運が悪ければ別の $x,y$ を求めることになります)。

このような $x,y$ を直接求めるのは大変なので、代わりに
$p_1^{e_1} \cdot ... \cdot p_s^{e_s} \equiv \pm q_1^{f_1} \cdot ... q_t^{f_t} \pmod{N}$
をとなる式を求めることにします ($p_1,...p_s, q_1,...q_t$ は異なる素数)。このような式を関係式と呼びます。

Schnorr の素因数分解では、最初の $s$ 個の素数を $p_i$ と定め, 以下のような基底ベクトルで生成される格子を考えます (成分 $*$ の設定法は説明を割愛します):

\mathbb{b}_1=\begin{pmatrix} * \\ * \\ \log{p_1} \end{pmatrix},
...,
\mathbb{b}_s=\begin{pmatrix} * \\ * \\ \log{p_s} \end{pmatrix}.

このとき

\mathbb{t}=\begin{pmatrix} * \\ * \\ \log{N} \end{pmatrix}

というベクトルをターゲットベクトルとする CVP を考えることで

 \mathbb{t} \approx e_1 \mathbb{b}_1+...+e_s \mathbb{b}_s

となる整数 $e_1,...,e_s$ を求めることができます.
特に最終行に着目することで $\log{N} \approx e_1 \log{p_1} + ... + e_s \log{p_s}$
つまり $N \approx p_1^{e_1} \cdot ... \cdot p_s^{e_s}$ という式が得られます.
係数 $e_i$ は負の可能性があるため、$u=\prod_{e_i>0} p_i^{e_i}$, $v=\prod_{e_i<0} p_i^{-e_i}$ と定めると、$N \approx u/v$ つまり $u \approx vN$ とあらわすことできます.このとき $u-vN$ は小さい整数なので容易に素因数分解できるでしょうから、その素因数分解を $\pm q_1^{f_1} \cdot ... \cdot q_t^{f_t}$ とかくことで、$\prod_{e_i>0} p_i^{e_i} = u \equiv u-vN = \pm q_1^{f_1} \cdot ... \cdot q_t^{f_t}$ となり、最初と最後から関係式が得られます。

このように Schnorr の素因数分解法は格子上の CVP を解くことで素因数分解を実現しています。Schnorr は Enumeration 法という手法で CVP を解くことで47ビット合成数の素因数分解に成功しています。また佐藤等は別の格子の生成法を用いることで90ビット合成数の素因数分解に成功しています。

QAOA の利用

2022 年 12 月に Yan 等は Schnorr の素因数分解法に QAOA (Quantum Approximation Optimization Algorithm) を適用する手法を提案しました。
これは、CVP をさらに組み合わせ最適化問題に変換し、その最適化問題を QAOA という量子アルゴリズムによって解くというものでした。
提案者等が量子計算機上で実験したところ、三種類の合成数の素因数分解に必要な関係式をいくつか算出することに成功しました (11ビット, 26ビット, 48ビット)。また提案者等の見積りによると、2048 ビット合成数を素因数分解するには 372 量子ビットで十分で、既に開発されている量子計算機でも可能であることが主張されており、この見積りには大きな注目が集まりました。

しかし 2023 年 5 月に発表された山口等の報告によると、Yan 等の手法でより大きな合成数を素因数分解すると計算量が見積りよりも大きな割合で増大するため、巨大合成数に対しては Shor アルゴリズムよりも効率が悪い可能性が高いことが指摘された。また山口等は Yan 等の手法をシミュレーティッドアニーリング計算機と呼ばれる古典計算機に実装して 55 ビット合成数の素因数分解に成功することで、Yan 等の手法において量子計算は必須ではないことを指摘した。

量子アニーリング計算機の利用

2024 年 1 月に Wang 等は Schnorr の素因数分解法に量子アニーリング計算を適用する手法を提案し、D-Wave という量子アニーリング計算機上に実装したところ 50 ビット合成数の素因数分解に必要な関係式をいくつか算出することに成功しました。しかし提案手法は QAOA の代わりに量子アニーリング計算を利用するというシンプルなアイディアであるため、山口等の 55 ビット合成数の素因数分解実験よりも小規模に留まっており、量子アニーリング計算機とシミュレーティッドアニーリング計算機の性能差がそのまま現れる結果になったと見ることができます。

まとめ

Schnorr の素因数分解法と、QAOA を使った改良、および量子アニーリング計算機を使った改良について紹介しました。何かの参考になれば幸いです。