SIP第3期量子技術課題「教育プログラムの開発と実践」教育コースプログラム「量子技術入門コース」の第七講に参加してきました。

https://skillup-next.co.jp/sip_3period_01

今回は量子コンピュータのアルゴリズムを扱う内容でした。以下ではその代表格であるショアのアルゴリズムについてご紹介します。数式を追うだけでなく、実際に Mathematica で検証しました。

「計算量に立つ安全性」の正体

前回と前々回の2回にわたって、量子通信を扱ってきました。従来の暗号の安全性は「計算量の仮定」に立っており、量子鍵配送の安全性は「物理法則」に立っています。

では、その「計算量の仮定」とは具体的に何なのでしょうか。

RSA 暗号の場合、それは簡単で——2つの素数を掛けるのは一瞬だが、積から元の2つを復元するのは絶望的に大変——ということです。この非対称性だけが、私たちの通信を守っています。

どれくらい大変なのか、測ってみます。Mathematica の FactorInteger に、同じ桁数の素数2つの積を与えて時間を測りました。

グラフは対数軸に対して線形なので、指数関数的（厳密には準指数関数的）に素因数分解にかかる時間は増加します。

過去には RSA Factoring Challenge という2つの巨大な素数の積から元となった素数を特定するコンテストが開催されており、2020年に RSA-250（250桁、829ビット）^*が分解されたときに投入された計算資源は約2700コア年でした[1]。また、つい先日（2026年9月3日）、RSA-260（260桁、862ビット）の素因数のひとつが公開されました[2]。

^* ビット数と桁数のどちらも示すことがある

現在広く使われている RSA-2048（617桁、2048ビット）を現代のアルゴリズムで解くには、非常に長い時間がかかります。RSA-250 の実記録を基準に、素因数分解の理論的なコスト関数で外挿すると、10¹⁴コア年というオーダーになります。

これが「計算量に立つ安全性」です。物理法則が禁じているわけではありません。ただ、誰も速い方法を見つけていないというだけです。

ただ、その「速い方法」は、1994年にピーター・ショアが見つけています[3]。実現していないのは量子コンピュータの上で動くからです。

ショアのアルゴリズム：素因数分解を「周期を測る問題」に読み替える

ショアのアルゴリズムの本質は、問題の読み替えです。位数というものに着目します。

位数とは何か

\(N\) と共通の素因数を持たない整数 \(a\) を取り、\(a\) を掛けては \(N\) で割った余りに直す、という操作を繰り返します。

\[a^0 = 1,\quad a^1,\quad a^2,\quad a^3,\quad \ldots \pmod N\]

余りの種類は有限個しかないので、この列はいつか元の値に戻ります。しかも \(a\) と \(N\) は共通の素因数を持たないので、戻る先は出発点の 1 です。初めて \(a^r \equiv 1 \pmod N\) となる \(r\) を、\(a\) の位数と呼びます。

\(N = 15\)、\(a = 7\) でやってみます。

\[1,\quad 7,\quad 7^2 = 49 \equiv 4,\quad 7^3 \equiv 28 \equiv 13,\quad 7^4 \equiv 91 \equiv 1 \pmod{15}\]

4回で1に戻りました。位数は \(r = 4\) です。つまり \(1, 7, 4, 13, 1, 7, 4, 13, \ldots\) と周期4で繰り返す列になっています。

ちなみにこれは、循環小数と同じ話です。\(1/7 = 0.142857142857\ldots\) が6桁で循環するのは、筆算の余りが \(3, 2, 6, 4, 5, 1\) と進んで6回目に 1 へ戻るからです。この余りの列は \(10^k\) を 7 で割った余りそのもので、つまり「\(10\) の位数が 6」ということです。

いま見た \(N = 15\)、\(a = 7\) も同じ構造です。余りの列 \(1, 7, 4, 13\) は \(1/15\) を7進法で筆算したときの余りで、

\[\frac{1}{15} = 0.\overline{0316}_{(7)}\]

と周期4で循環します。位数とは、\(1/N\) を \(a\) 進法で書いたときの循環節の長さなのです。

なぜ位数がわかると因数が出るのか

ここが手品の種です。位数の定義から \(a^r\) を \(N\) で割った余りは 1、つまり \(a^r – 1\) は \(N\) の倍数です。

\(r\) が偶数なら、この数は因数分解できます。\(x = a^{r/2}\) と置くと、

\[a^r – 1 = (x-1)(x+1)\]

\(N\) の倍数が、2つの数の積として書けました。 \(N=15\)、\(a=7\) なら \(r=4\) で、

\[7^4 – 1 = 2400 = 48 \times 50 \qquad (2400 = 160 \times 15)\]

では 15 の素因数 3 と 5 は、どちらに入ったのでしょうか。

RSA で使う \(N = p \times q\)（\(p\)、\(q\) は素数）で考えます。\((x-1)\) と \((x+1)\) は別々の2つの数なので、\(p\) と \(q\) はどちらかに入るしかありません。分かれ方は3通りです。ここで、\(\gcd\) は最大公約数を意味します。

\(p\) と \(q\) の行き先	\(\gcd(x-1,N) \times \gcd(x+1,N)\)
両方とも \(x-1\) 側	\(N \times 1\)
両方とも \(x+1\) 側	\(1 \times N\)
片方ずつに分かれる	\(\mathbf{p \times q}\)

上2つは、自明な分解です。 どのような条件で起こるかを順に見ていきましょう。

まず \(x-1\) の方。\(N\) が \(x-1\) を割り切るというのは、\(x = a^{r/2}\) を \(N\) で割った余りが 1 だということです。しかしそれは起こりません。余りが 1 になる指数は \(0, r, 2r, 3r, \ldots\) と \(r\) おきだけで、\(r/2\) はその隙間——0 と \(r\) のちょうど真ん中——にあるからです。

次に \(x+1\) の方。こちらは余りが \(N-1\) のときに割り切れてしまいます。これは自動では防げないので、毎回確かめて、駄目なら \(a\) を選び直します。

これで、残るのは3行目だけになりました。

\(N=15\), \(a=7\) で確かめます。\(r=4\) なので \(x = 7^2 = 49\)。

\[\gcd(49-1,\ 15) = \gcd(48, 15) = 3, \qquad \gcd(49+1,\ 15) = \gcd(50, 15) = 5\]

\(15 = 3 \times 5\)。素因数分解が、割り算を一度もせずに出てきました。

必要な条件は2つだけです。\(r\) が偶数であること、そして \(x+1\) が \(N\) の倍数でないこと。前者は \(x\) が作れるための条件、後者は表の2行目（両方とも \(x+1\) 側）を避けるための条件です。どちらかが破れたら \(a\) を選び直します。

ただし、古典ではメリットが無い

古典計算機では、位数発見は素因数分解と同じ難しさです。Mathematica の MultiplicativeOrder は位数を一発で返しますが、160ビットの素数積で 2.75 秒——FactorInteger の 2.26 秒とほぼ同じでした。位数を求めるために、内部でまず \(N\) を素因数分解しているからです。ショアの読み替えは、それ自体では計算時間の短縮に寄与しません。

量子でメリットがあるのは、量子コンピュータだけが「周期を直接読む」手段を持っているからです。

量子はどうやって周期を読むのか

全部の \(y\) について一度に計算する

2つのレジスタを用意します。

• 作業レジスタ（\(n\) 量子ビット）——計算結果 \(a^y \bmod N\) を置く場所です。値は \(0\) から \(N-1\) までなので、\(N\) のビット長だけ必要です。
• 計数レジスタ（\(t\) 量子ビット）——指数 \(y\) を置く場所です。最後に測定するのはこちらで、ここから周期を読み取ります。\(t\) が大きいほど周期を細かく読めます。\(y/2^t\) から \(r\) を復元するには \(2^t > N^2\)、つまり \(t \ge 2n\) 程度が必要です（本記事のシミュレーションでは、次元を抑えるため \(t\) を 8 で頭打ちにしています）。

以下、ケットの中にはビット列ではなく、それが表す数を書きます。たとえば3量子ビットなら、

\[|000\rangle = |0\rangle, \quad |001\rangle = |1\rangle, \quad |010\rangle = |2\rangle, \quad \ldots, \quad |111\rangle = |7\rangle\]

という具合です。計数レジスタが表す数を \(y\)、作業レジスタが表す数を \(z\) と書くことにします。

\[|\,y = 0\,\rangle \otimes |\,z = 1\,\rangle\]

計数レジスタの各ビットにアダマール変換をかけると、\(0\) から \(2^t-1\) までの \(y\) が一様に重ね合わさります。

\[\frac{1}{\sqrt{2^t}}\sum_{y=0}^{2^t-1} |y\rangle \otimes |1\rangle\]

ここに「作業レジスタに \(a\) を掛け、\(N\) で割った余りにする」操作 \(U\) を計数レジスタ \(y\) の回数だけ作用します。

\[U = \sum_{z=0}^{N-1} \bigl|\,a z \bmod N\,\bigr\rangle \bigl\langle\, z\,\bigr| \;+\; \sum_{z=N}^{2^{n}-1} \bigl|\,z\,\bigr\rangle \bigl\langle\, z\,\bigr|\]

\[V = \sum_{y=0}^{2^t-1} |y\rangle\langle y| \otimes U^{y}\]

これを先ほどの重ね合わせに作用させます。\(\langle y | y’ \rangle\) は \(y = y’\) のときだけ 1 になるので、各項がそのまま振り分けられて、

\[V \cdot \frac{1}{\sqrt{2^t}}\sum_{y=0}^{2^t-1} |y\rangle \otimes |z=1\rangle \;=\; \frac{1}{\sqrt{2^t}}\sum_{y=0}^{2^t-1} |y\rangle \otimes |a^y \bmod N\rangle\]

\(2^t\) 通りの \(a^y\) が、一度に並びました。

ここが肝心です。計数レジスタが特定の \(y\) に決まっていたら、得られる \(a^y\) はたった1つ——ただの古典計算になってしまいます。重ね合わせだからこそ \(2^t\) 本の枝が同時に残り、しかも枝ごとに作業レジスタの中身が違う。これが2つのレジスタを結びつけます。

ただし、こうして作った状態を測っても、出てくるのは1個だけです。重ね合わせは「全部計算した」ことにはなっても「全部読める」ことにはなりません。前回までに見てきた、測ると壊れるという性質そのものです。

周期は「間隔」として残っている

しかし、この状態には周期が刻まれています。\(a^y\) は \(y\) について周期 \(r\) で繰り返すので、作業レジスタの中身が同じになる \(y\) たちは、\(r\) おきに等間隔で並んでいます。

\[y_0,\quad y_0 + r,\quad y_0 + 2r,\quad y_0 + 3r,\ \ldots\]

そこに逆量子フーリエ変換をかけます。測定すると、

\[y \approx k \cdot \frac{2^t}{r} \qquad (k = 0, 1, 2, \ldots)\]

の位置にピークが立ちます。\(y\) そのものには意味がなく、ピークの間隔に \(r\) が入っている——ここがショアのアルゴリズムの心臓部です。

実際に計算してみる

Mathematica の Wolfram Quantum Framework で、この回路をそのまま組んで動かしました。

測定分布はこうなりました。

測定値 \(y\)	確率
0	0.25
16	0.25
32	0.25
48	0.25

他の60通りはすべて確率ゼロ。間隔は16です。\(2^t / 16 = 64/16 = 4\)。位数 \(r = 4\) が読めました。先ほど手計算で出した値と一致します。

実際には \(y/2^t\) は \(k/r\) にぴったり一致するとは限らず、近い値になるだけです。そこで連分数展開を使って、\(y/2^t\) に最も近い分母の小さい分数を探し、その分母を \(r\) の候補とします。この後処理は完全に古典計算で、一瞬で終わります。

Mathematica で実際に分解してみた

位数発見に、\(a\) の選び直しと最大公約数の計算を足せば、ショアのアルゴリズムの完成です。13個の合成数で試しました。

\(N\)	因数	使った量子ビット	シミュレータの次元
15	3 × 5	12	4,096
35	5 × 7	14	16,384
77	7 × 11	15	32,768
143	11 × 13	16	65,536
209	11 × 19	16	65,536
247	13 × 19	16	65,536

全部成功しました。247 = 13 × 19 を、16量子ビットの量子回路が解いたわけです。

……ところで、247 を試し割りで分解すると7ステップで終わります。2, 3, 5, 7, 9, 11, 13 と割ってみるだけです。

小さい \(N\) では、古典が圧勝です。 \(N=15\) を量子コンピュータで分解した実験[4]は「量子が速い」ことの証明ではなく、「動く」ことの証明でした。

もうひとつ。上の表の「シミュレータの次元」が、量子コンピュータが必要な理由をそのまま語っています。\(n\) ビットの \(N\) を扱うには約 \(3n\) 量子ビットが必要で、古典計算機でそれをシミュレートするには \(2^{3n}\) 個の複素数を並べなければなりません。8ビットの 247 で、すでに65,536次元です。シミュレータで RSA は絶対に破れません。 だからこそ本物の量子計算機が要るのです。

どこで逆転するのか

古典側の最速アルゴリズムは一般数体ふるい法（GNFS）で、そのコストは準指数関数と呼ばれる形になります。ショアのアルゴリズムは \(O(n^3 \log n)\) 程度、つまり多項式です。並べるとこうなります。

RSA-2048 で、10³⁵ 演算 対 10¹² ゲート。23桁の差です。

古典側の数字は、実際の記録から見ても妥当です。先ほどの RSA-260 を基準にすると、RSA-2048 はおよそ 170億倍（2³⁴倍）の手間になると見積もられています[2]。7000コア年の170億倍——これが、いま RSA を守っているものの正体です。

そして逆転が起きるのは、意外に小さいところでした。ゲート数だけを比べれば79ビット付近、実測時間で較正して比べても290ビット付近です。つまり512ビット（155桁）の RSA なら、量子計算機は原理的にもう勝っています。

注目してほしいのは、表の縦の伸び方です。ビット長を2048から4096へ倍にすると、GNFS の手間は 10¹² 倍になりますが、ショアは 9倍にしかなりません。鍵長を伸ばして守るという従来の防御が、ショアに対しては効かない——曲線の形が違うとは、こういうことです。

まとめ：「多項式時間」は「実現できる」という意味ではない

ここまで読むと RSA は明日にも終わりそうですが、そうではありません。

RSA-2048 を破るには 4,099個の論理量子ビットが要ります[5]。ここでいう「論理」は、誤り訂正によって守られた理想的な量子ビットのことです。実際のハードウェアはノイズだらけなので、論理量子ビット1個を作るのに物理量子ビットが何千個も要ります。

現在最も詳しい見積もりでは、RSA-2048 の分解に必要なのは 約2000万個の物理量子ビットと8時間とされています[6]。いま世界で動いている最先端の実機は、物理量子ビットで数百から千のオーダーです。4〜5桁足りません。

だから「ショアのアルゴリズムがあるから RSA はもう危ない」という言い方は、正確ではありません。正確に言うとこうなります。

素因数分解の難しさは、もはや物理法則ではなく、工学の進捗に守られている。

計算量の壁は、1994年に理論上は崩れました。いま残っているのは、誤り訂正という工学の壁だけです。そして工学の壁は、いつか越えられます。

だから暗号の世界で問われているのは「いつ壊れるか」ではなく「今日盗まれた通信が、10年後に解読されて困るか」です。暗号文を今のうちに集めておいて、量子計算機ができてから解読する——harvest now, decrypt later と呼ばれる考え方です。この観点では、猶予は量子計算機の完成までではなく、もう尽きています。

対策は2つの方向に分かれます。ひとつは、ショアが効かない別の数学的問題に暗号を載せ替える耐量子暗号。もうひとつが、前回・前々回で見てきた、安全性の根拠そのものを計算量から物理法則へ移す量子鍵配送です。

第五講から続いてきた「観測すると壊れる」「コピーできない」という話が、なぜ暗号の文脈で語られるのか。その答えが、今回のショアのアルゴリズムでした。量子力学は、暗号を壊す側と守る側の両方に、同時に現れます。

参考文献

[1] RSA-250 の素因数分解
F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, P. Zimmermann, “Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment,” CRYPTO 2020, LNCS 12171, 62–91.
https://eprint.iacr.org/2020/697

[2] RSA-260 の素因数分解（2026年）
E. Lu, 素因数の公開（2026年9月3日）。解説は John D. Cook, “New RSA number factored” (2026).
https://www.johndcook.com/blog/2026/09/03/new-rsa-number-factored/

[3] ショアの原論文
P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing 26, 1484–1509 (1997).
https://epubs.siam.org/doi/10.1137/S0097539795293172

[4] \(N=15\) の実験的実証
L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, I. L. Chuang, “Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance,” Nature 414, 883–887 (2001).
https://www.nature.com/articles/414883a

[5] 最小構成の回路
S. Beauregard, “Circuit for Shor’s algorithm using 2n+3 qubits,” Quantum Information and Computation 3, 175–185 (2003).
https://arxiv.org/abs/quant-ph/0205095

[6] 現実的な資源見積もり
C. Gidney, M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433 (2021).
https://quantum-journal.org/papers/q-2021-04-15-433/