a^{r} (a^{r /2} - 1) (a^{r /2} + 1) \equiv 1 (mod N) \equiv 0 (mod N)

ショアのアルゴリズム

Shor's algorithm

話したのは離散対数。うわさは「因数分解」になって届いた。

a を何乗すると N で割って 1 余るか。その周期 r を量子計算機で速く見つけ、最大公約数の計算で素因数を取り出す。RSA 暗号の前提を揺るがした。

年代: 1994年
人物: ピーター・ショア、ウメーシュ・ヴァジラーニ、ダニエル・サイモン、ロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマン、ゲイリー・ミラー、アレクセイ・キタエフ、アイザック・チャン

数学情報科学物理学工学

逸話

うわさは因数分解になって届いた

1994 年 4 月、ニュージャージー州の AT&T ベル研究所で、数学者ピーター・ショアは 1 つの問題を解いた。量子計算機を使えば、離散対数を速く求められる。素数 $p$ で割った余りの世界で、 $g^{x}$ の値から $x$ を求める問題である。望みの薄い挑戦だと思い、誰にも話していなかった。

きっかけは 2 つあった。1992 年、ウメーシュ・ヴァジラーニがベル研究所で、イーサン・バーンスタインとの量子チューリング機械の研究を話した。量子計算機のほうが速く解ける問題が示されたが、作り物の問題だった。ショアは、本物の問題で同じことができないかと考え始めた。次に、1994 年の国際会議 STOC のプログラム委員として、ダニエル・サイモンの論文を読んだ。論文は採録されなかった。サイモンは、0 と 1 を並べたベクトルの上のフーリエ変換で、関数の周期を見つけていた。フーリエ変換が周期を探す道具であることも、離散対数が周期と結びつくことも、ショアは知っていた。

解けたあと、上司のデイヴィッド・ジョンソンと、同僚のジェフ・ラガリアスに話した。確かめたラガリアスは小さな誤りを見つけたが、すぐに直せるものだった。ジョンソンに勧められて、ヘンリー・ランダウが毎週火曜日に開くセミナーで話した。聞き手が次々に質問をはさむ場で、2 枚目のスライドから先へ進めなかった話し手もいたという。発表は無事に済んだ。その週のうちに、ショアは素因数分解も解いた。

その週末、ひどい風邪で家にいたショアに、ヴァジラーニから電話がかかってきた。「量子計算機で素因数分解が速くできるそうだね」。火曜日のセミナーのうわさが、人づてにヴァジラーニまで届いていた。話したのは離散対数だったのに、うわさは素因数分解に変わっていた。ショアは 2022 年の回想で、これを伝言ゲームにたとえている。うわさは、もう本当になっていた。ショアは電話で、素因数分解の方法を説明した。

知らせは一気に広がった。4 月のうちにコロンビア大学の理論計算機科学の集まりで、チャールズ・ベネットらに方法を説明した。5 月の初めには、コーネル大学の計算数論のシンポジウムで、急に組まれた特別講演をした。ショアは 2020 年の聞き取りで、この結果は計算機科学の土台そのものを揺さぶった、と振り返っている。

起源

4 京年の暗号

1977 年、マサチューセッツ工科大学のロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンは、公開鍵暗号の方法を考えた。3 人の頭文字から RSA 暗号と呼ばれる。大きな素数 $p$ , $q$ を掛けた $N = pq$ は公開してよい。 $p$ と $q$ を知る人だけが、暗号を解く鍵を計算できる。安全の根拠は、大きな数の素因数分解が難しいことにある。

同じ年の 8 月、マーティン・ガードナーは『サイエンティフィック・アメリカン』の連載でこの方法を紹介した。当時の最良の方法と最速の計算機でも、63 桁の素数 2 つの積の分解には約 4 京年かかる、というリベストの見積もりも載せた。記事には 129 桁の数で暗号にした文が載り、最初に解いた人には 100 ドルが約束された。

この 129 桁の数は、1994 年 4 月に分解された。20 か国以上の約 600 人のボランティアが、8 か月かけて計算機を持ち寄った。デレク・アトキンス、マイケル・グラフ、アリエン・レンストラ、ポール・レイランドが発表した文は「THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE」だった。ショアがセミナーで話したのと同じ月である。ショアの論文によれば、いちばん速い数体ふるい法でも手間はおよそ $exp (c (lo g N)^{1/3} (lo g lo g N)^{2/3})$ で、桁数の多項式では収まらない。

素因数分解を周期探しに置き換える考えは、量子計算より古い。乱数を使えば、素因数分解は $a^{r} \equiv 1$ となる $r$ を求める問題に帰着できる。ショアはこれを 1976 年のゲイリー・ミラーの仕事として引いている。

ショアは 1994 年 11 月 20〜22 日、ニューメキシコ州サンタフェの国際会議 FOCS で論文を発表した。量子計算機の手順の数は $O ((lo g N)^{2} lo g lo g N lo g lo g lo g N)$ で、桁数の多項式で済む。くわしい版は 1997 年の『SIAM Journal on Computing』26 巻に、サイモンの論文と並んで載った。モスクワのアレクセイ・キタエフは、ショアの論文を手に入れられないまま 1995 年に別の証明を考え、いまは位相推定と呼ばれる方法を生んだ。ショアは 1998 年に国際数学者会議でネヴァンリンナ賞を受け、2023 年のブレイクスルー賞の基礎物理学部門をベネットらと分け合った。

証明

$N$ を 2 つの異なる奇素数の積 $N = pq$ とする。RSA 暗号の $N$ はこの形である。 $1 < a < N$ の整数 $a$ を 1 つ選ぶ。 $g cd (a, N) > 1$ なら、それがもう因数である。以下では $g cd (a, N) = 1$ とする。

$a, a^{2}, a^{3}, \dots$ を $N$ で割った余りがとれる値は有限なので、どこかで $a^{i} \equiv a^{j}$ ( $i < j$ )となる。 $a$ は $N$ と互いに素で、余りの世界で逆数を持つので、両辺を $a^{i}$ で割れる。
$a^{j - i} \equiv 1 (mod N)$
$a^{r} \equiv 1$ となる最小の正の整数 $r$ を、 $a$ の位数と呼ぶ。余りの列は $r$ ごとに同じ値をくり返す。 $r$ はこの列の周期である。
$a^{x + r} \equiv a^{x} (mod N)$
$r$ が偶数なら、 $a^{r} - 1$ は 2 つの因数に分かれ、その積を $N$ が割り切る。
$(a^{r /2} - 1) (a^{r /2} + 1) = a^{r} - 1 \equiv 0 (mod N)$
$r$ は最小なので $a^{r /2} \neq \equiv 1$ である。さらに $a^{r /2} \neq \equiv - 1$ なら、 $N$ はどちらの因数も割り切らない。
$N ∤ a^{r /2} - 1, N ∤ a^{r /2} + 1$
$d = g cd (a^{r /2} - 1, N)$ とする。 $d = 1$ なら、3 から $N$ が $a^{r /2} + 1$ を割り切ることになり、4 に反する。 $d = N$ も 4 に反する。よって $d$ は $p$ か $q$ である。
$1 < g cd (a^{r /2} - 1, N) < N$
最大公約数は、ユークリッドの互除法で速く求まる。割り算の回数は、小さいほうの数の桁数の 5 倍を超えない(1844 年のラメの定理)。
$g cd (m, n) = g cd (n, m mod n)$

うまくいかないのは、 $r$ が奇数のときと、 $a^{r /2} \equiv - 1$ のときだけである。その割合を、ショアの論文の第 5 節の筋で見積もる。

中国剰余定理により、 $a$ を無作為に選ぶことは、 $p$ で割った余りと $q$ で割った余りを別々に無作為に選ぶことと同じである。 $p$ , $q$ を法とする位数を $r_{p}$ , $r_{q}$ とすると
$r = lcm (r_{p}, r_{q})$
$r_{p}$ , $r_{q}$ を割り切る最大の 2 の累乗を $2^{s_{p}}$ , $2^{s_{q}}$ とする。 $s_{p} = s_{q} = 0$ なら $r$ は奇数である。 $s_{p} = s_{q} \geq 1$ なら $r /2$ は $r_{p} /2$ の奇数 $m$ 倍で、素数を法として 2 乗が 1 になる数は $\pm 1$ だけなので $a^{r_{p} /2} \equiv - 1$ 。 $q$ でも同じで、 $a^{r /2} \equiv - 1 (mod N)$ になる。
$a^{r /2} = (a^{r_{p} /2})^{m} \equiv (- 1)^{m} = - 1 (mod p)$
$s_{p} > s_{q}$ なら $r$ は偶数で、 $r /2$ は $r_{q}$ の倍数なので $a^{r /2} \equiv 1 (mod q)$ となり、 $- 1 (mod N)$ にはならない。 $s_{p} < s_{q}$ も同じである。失敗は $s_{p} = s_{q}$ のときに限る。
$a^{r /2} \equiv 1 (mod q) \Rightarrow a^{r /2} \neq \equiv - 1 (mod N)$
$p$ で割った 0 でない余りは、原始根 $g$ の累乗ですべて表せる。 $p - 1 = 2^{t} u$ ( $u$ は奇数)とすると、 $g^{k}$ の位数が $2^{t}$ で割り切れるのは $k$ が奇数のとき、つまりちょうど半分である。ほかの $s$ をとる割合も半分以下なので、 $s_{q}$ が何であっても
$P (s_{p} = s_{q}) \leq \frac{1}{2}$

$N = pq$ なら、無作為な $a$ で成功する確率は $1/2$ 以上である。ショアは、 $N$ が $k$ 個の異なる奇素数を含むとき $1 - 1/ 2^{k - 1}$ 以上になることを示した。

残るのは周期 $r$ を見つけることである。 $a^{x}$ を順に計算すると、 $r$ は $N$ に近い大きさになりうるので、手間は桁数の指数で増える。ショアは、ここだけを量子計算機に任せた。以下は考え方の道筋である。

$N^{2} \leq Q < 2 N^{2}$ となる 2 の累乗 $Q = 2^{L}$ を選ぶ。 $L$ 個の量子ビットに $0$ から $Q - 1$ までの $x$ を同じ重みで重ね合わせ、 $a^{x} mod N$ を別の量子ビットに計算する。
$\frac{1}{Q} x = 0 \sum Q - 1 ∣ x ⟩ ∣ a^{x} mod N ⟩$
2 つ目を測ると、値が 1 つ出る。1 つ目に残るのは、その値をとる $x$ だけで、 $x_{0}$ から $r$ おきに並ぶ。個数 $M$ は $Q / r$ に近い。
$\frac{1}{M} b = 0 \sum M - 1 ∣ x_{0} + b r ⟩$
量子フーリエ変換 $∣ x ⟩ \mapsto \frac{1}{Q} \sum_{c} e^{2 π i x c / Q} ∣ c ⟩$ をかける。 $c$ が出る確率は、単位円の上を一定の角度ずつ回る複素数の和で決まる(オイラーの公式)。
$P (c) = \frac{1}{M Q} b = 0 \sum M - 1 e^{2 π i b r c / Q}^{2}$
$r c / Q$ が整数に近いと、どの項も同じ向きを向いて強め合う。そうでなければ回りながら打ち消し合う。 $r$ が $Q$ を割り切るなら、和は $c$ が $Q / r$ の倍数のとき $M$ で、ほかは 1 の累乗根の和なので 0 になる。
$P (c = j \frac{Q}{r}) = \frac{1}{r}, j = 0, 1, \dots, r - 1$
一般の場合、ショアは、ある整数 $j$ で次の不等式が成り立つ $c$ について、 $c$ と 2 つ目の値の組が出る確率は $N$ が大きければ $1/ (3 r^{2})$ 以上だと示した。2 つ目の値は $r$ 通りあるので、 $c$ だけを見れば $1/ (3 r)$ 以上で、そうした $c$ は $j = 0, 1, \dots, r - 1$ のそれぞれにある。 $Q \geq N^{2}$ なので、不等式を満たす分母 $N$ 未満の分数はただ 1 つで、 $c / Q$ の連分数で見つかる。
$\frac{c}{Q} - \frac{j}{r} \leq \frac{1}{2 Q}$

$j$ と $r$ に共通の因数があると、分母は $r$ の約数になる。そのときは測り直すか、小さな倍数を試す。量子フーリエ変換は $L$ 個の量子ビットにおよそ $L^{2} /2$ 個の基本の操作で済む。 $Q$ 個の値の高速フーリエ変換(フーリエ級数)を古典の計算機で行えば、 $L$ の指数の手間がかかる。ただし量子計算機は $Q$ 個の答えを同時に読み出すわけではない。測って得られる $c$ は 1 つだけで、波の干渉によって、役に立つ $c$ が出やすくなっている。

難しいのは、重ね合わせを長い計算のあいだ崩さずに保つことである。1994 年 5 月、ロルフ・ランダウアーは、量子計算機は誤りに耐えられそうにないと指摘した。ショアの回想によれば、暗号の大きさの数には 10 億段ほどの計算が要り、各段を 10 億分の 1 の精度にするのは、実験の物理学者には無理だと見られていた。ショアは 1995 年、量子誤り訂正符号でこの見方を崩し始めた。量子部分の完全な説明は、ショアの 1997 年の論文の第 3〜5 節と、ニールセンとチャンの教科書の第 5 章にある。

応用

15 を分解する。 $N = 15$ 、 $a = 7$ とする。 $7^{2} = 49 \equiv 4$ 、 $7^{3} \equiv 28 \equiv 13$ 、 $7^{4} \equiv 91 \equiv 1$ なので、周期は $r = 4$ である。 $7^{2} \equiv 4$ から $g cd (3, 15) = 3$ 、 $g cd (5, 15) = 5$ が出て、 $15 = 3 \times 5$ となる。15 と互いに素な 8 個の $a$ のうち、失敗するのは $a = 1$ ( $r = 1$ )と $a = 14$ ( $14 \equiv - 1$ )だけで、成功の割合は $3/4$ である。量子の部分では $Q = 256$ で、 $r = 4$ が 256 を割り切るので、 $c$ は 0, 64, 128, 192 のどれかが $1/4$ ずつの確率で出る。 $c = 64$ なら $64/256 = 1/4$ で $r = 4$ 。 $c = 128$ なら $1/2$ で、候補の 2 は $7^{2} \neq \equiv 1$ なので、倍数の 4 を試す。

21 を分解する。 $N = 21$ 、 $a = 2$ では、余りは 2, 4, 8, 16, 11, 1 とくり返し、 $r = 6$ である。 $2^{3} = 8$ から $g cd (7, 21) = 7$ 、 $g cd (9, 21) = 3$ が出る。失敗するのは、 $r = 3$ が奇数の $a = 4, 16$ と、 $a^{r /2} \equiv - 1$ になる $a = 5, 17, 20$ と、 $a = 1$ である。12 個のうち 6 個で、成功はちょうど半分になり、証明の下限 $1/2$ と一致する。量子の部分では $Q = 512$ で、6 は 512 を割り切らない。確率の山は $512/6 \approx 85.3$ の倍数の近くに立つ。 $c = 85$ が出る確率は約 0.114 で、連分数 $85/512 = 1/ (6 + 1/ (42 + 1/2))$ の途中で止めた $1/6$ から、 $r = 6$ が分かる。

2001 年の実験。 IBM アルマデン研究所とスタンフォード大学のアイザック・チャンらは、フッ素 19 の原子核 5 個と炭素 13 の原子核 2 個を持つように合成した分子を、7 個の量子ビットとして使った。核磁気共鳴(NMR)の装置で約 300 回の電波のパルスを最長で約 0.72 秒かけて当て、 $a = 11$ で $r = 2$ 、 $a = 7$ で $r = 4$ を読み取って、15 の素因数 3 と 5 を導いた。論文は、NMR の方法で多くの量子ビットへ広げられることを、この実験が示すわけではないと断っている。

いまどこまで来たか。 2012 年には、光子を使った実験で 21 が分解された。回路を前もって縮めた「コンパイル版」である。ジョン・スモーリンらは 2013 年、そうした縮め方を使えば 2 個の量子ビットで大きな 2 素数の積でも「分解」できてしまうと示し、難しさは数の大きさでなく周期の長さで測るべきだと書いた。2025 年 5 月、クレイグ・ギドニーは、2048 ビットの RSA の数を分解するには、操作の誤り率が 0.1% の量子ビットが 100 万個弱、時間は 1 週間弱かかると見積もった。2019 年の見積もりでは 2000 万個だった。

暗号の切り替え。 2024 年 8 月 13 日、アメリカ国立標準技術研究所(NIST)は、量子計算機に耐える暗号の最初の標準 FIPS 203・204・205 を公表した。鍵を共有する ML-KEM と署名の ML-DSA は格子の問題を、予備の署名 SLH-DSA はハッシュ関数を土台にしていて、素因数分解にも離散対数にも頼らない。

図示

N = 15、a = 7 のときの、7ˣ を 15 で割った余り。1, 7, 4, 13 がくり返して周期 r = 4 が見え、半周期の 7² ≡ 4 の両隣の数 3 と 5 が 15 の素因数になる。

ショアの論文の図 5.1 と同じ Q = 256、r = 10(N = 33 で a = 5 のときの周期。見やすさのため Q は N² より小さい)で、量子フーリエ変換のあとに c を測る確率。山は三角の印の Q/r = 25.6 の倍数の近くに立つ。

ショアのアルゴリズムの受け持ち。量子計算機が受け持つのは網をかけた周期探しだけで、a を選ぶこと、測った c から連分数で r を読むこと、最大公約数を求めることは古典の計算機で行う。

シミュレーション

$N$ と $a$ を選ぶと、上の段に $a^{x} mod N$ の列が描かれ、1 に戻るところで周期 $r$ が区切られる。 $r$ が偶数で $a^{r /2} \neq \equiv - 1$ なら $g cd (a^{r /2} \pm 1, N)$ で素因数が出て、そうでなければ「別の a を選ぶ」と出る。下の段は、量子フーリエ変換のあとに $c$ を測る確率を古典の計算機で求めたもので、量子計算機を動かしているわけではない。下の段をたたくか「1 回測る」を押すと、この確率で $c$ を 1 つ引き、連分数で $r$ の候補を読む。

広がる学問

数学証明に使ったのは、中国剰余定理・原始根・連分数・ユークリッドの互除法という、古くからの数論の道具である。 $a^{φ (N)} \equiv 1$ (オイラーの定理)から、位数 $r$ は $φ (N)$ を割り切る。キタエフは、ショアの方法を、素因数分解と離散対数をまとめて扱うアーベル安定化群問題の解き方に広げた。RSA の鍵に使う素数の多さは素数定理で、尽きないことは素数が無限にあることで分かる。
情報科学 ショアの論文は、どんな物理的な計算機も多項式の遅れでチューリング機械にまねできる、という「量的なチャーチの提唱」を、量子力学が破るかもしれないと論じて始まる。同じ考えは楕円曲線暗号の離散対数にも使え、2003 年にジョン・プロースとクリストフ・ザルカは、160 ビットの楕円曲線の鍵がおよそ 1000 量子ビットで破れると見積もった。
物理学 量子フーリエ変換は、確率の振幅の干渉で役に立つ答えを強め、ほかを打ち消す。振幅の変化はシュレーディンガー方程式に従う。ショアの回想によれば、測れば状態が乱れる不確定性原理と、未知の量子状態を複製できないことから、誤りを直すのは無理だと見られていた。ショアは 1995 年、1 個の量子ビットを 9 個に広げて守る符号を示し、量子誤り訂正の研究を開いた。
工学 2048 ビットの RSA に要る 100 万個近い量子ビットと、2001 年の 7 個との隔たりを、誤り訂正の設計と部品の誤り率の改善で埋めることが、量子計算機を作る研究の目標の 1 つである。

参考文献

P. W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", Proc. 35th Annual Symposium on Foundations of Computer Science (1994), 124-134.
P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput. 26(5) (1997), 1484-1509. arXiv:quant-ph/9508027
P. W. Shor, "The Early Days of Quantum Computation", arXiv:2208.09964 (2022); D. Zierler (interview, 2020), Physics Today 78(4) (2025), 34-37.
R. L. Rivest, A. Shamir, L. Adleman, Commun. ACM 21(2) (1978), 120-126; M. Gardner, Scientific American 237(2) (1977), 120-124; D. Atkins, M. Graff, A. K. Lenstra, P. C. Leyland, ASIACRYPT '94, LNCS 917 (1995), 261-277.
D. R. Simon, SIAM J. Comput. 26(5) (1997), 1474-1483; G. L. Miller, J. Comput. System Sci. 13 (1976), 300-317; A. Yu. Kitaev, arXiv:quant-ph/9511026 (1995).
L. M. K. Vandersypen et al., Nature 414 (2001), 883-887; E. Martín-López et al., Nature Photonics 6 (2012), 773-776; J. A. Smolin, G. Smith, A. Vargo, Nature 499 (2013), 163-165.
NIST, FIPS 203・204・205(2024年8月13日); C. Gidney, arXiv:2505.15917 (2025); J. Proos, C. Zalka, Quantum Inf. Comput. 3 (2003), 317-344.