はじめに：暗号技術と量子コンピュータの交差点
現代のインターネット社会において、通信の秘密を守るための基盤となっているのが「公開鍵暗号」です。その中でも代表的なものが、1977年にRon Rivest、Adi Shamir、Leonard Adlemanの3氏によって開発された「RSA暗号」です。私たちが毎日利用しているオンラインショッピングの決済、ウェブサイトの閲覧（HTTPS）、メールの送受信に至るまで、RSA暗号はインターネットインフラの心臓部として機能しています。
しかし、「量子コンピュータ」の登場によって、この安全性が根底から覆される可能性が指摘されています。メディアでは「量子コンピュータが完成すれば、世界中のパスワードや暗号が数秒で解読されてしまう」といったセンセーショナルな見出しが躍ることもあります。果たして、それは本当なのでしょうか？
本記事では、古典的な暗号解読手法であるGNFS（一般数体ふるい法）と、量子コンピュータを用いた暗号解読アルゴリズムの決定版である「ショアのアルゴリズム（Shor’s Algorithm）」の仕組みを深く掘り下げます。量子フーリエ変換や周期発見といった高度な概念を分かりやすく解説し、現在のNISQ（Noisy Intermediate-Scale Quantum）時代における量子ハードウェアの現状と、実際にRSA-2048を破るために必要なハードルについて詳細に検証していきます。
RSA暗号の根幹：素因数分解の困難性
RSA暗号の安全性は、数学における極めてシンプルな非対称性に依存しています。それは、「2つの巨大な素数を掛け合わせることは簡単だが、その掛け合わせた結果（合成数）から元の2つの素数を見つけ出す（素因数分解する）ことは極めて難しい」という事実です。
例えば、 $ p = 61 $、 $ q = 53 $ という2つの素数があったとします。この掛け算 $ N = p \times q = 3233 $ を計算するのは一瞬です。しかし、「3233」という数字だけを与えられて、「これはどの素数とどの素数の掛け算か？」を解くのは、数字が大きくなればなるほど計算量が爆発的に増加します。
現在主流となっているRSA-2048では、鍵長が2048ビット、つまり10進数にして約617桁にも及ぶ巨大な合成数 $ N $ が使われています。この $ N $ を素因数分解できれば、暗号は解読されたも同然となります。
古典コンピュータによる挑戦：GNFS（一般数体ふるい法）
素因数分解問題を解くために、数学者や暗号学者は長年にわたり様々なアルゴリズムを開発してきました。その中で、古典コンピュータにおいて現在最も高速とされているのが 一般数体ふるい法（GNFS: General Number Field Sieve） です。
GNFSは、巨大な数 $ N $ を素因数分解するために、整数環における計算をより抽象的な代数体（Number Field）に拡張して解析する手法です。大まかな流れとしては以下のようになります。
- 多項式の選択 : $ N $ を根として持つような、適切な次数と係数を持つ多項式 $ f(x) $ を見つけます。
- データ収集（ふるい分け） : 有理数体および代数体の上で、小さな素数（滑らかな数、Smooth numbers）に分解できるような数のペアを大量に探索します。このプロセスが「ふるい分け」と呼ばれ、最も時間を要する部分です。
- 行列の生成と簡約 : 収集した関係式を元に巨大な疎行列（成分のほとんどが0の行列）を生成し、線形代数的な手法（ブロック・ランチョス法など）を用いて解を求めます。
- 平方根の計算 : 最後に代数体上での平方根を計算し、$ N $ の因数（素因数）を導き出します。
GNFSの計算量は、非漸近的に $ O(\exp((\sqrt[3]{\frac{64}{9}} + o(1)) (\log N)^{\frac{1}{3}} (\log \log N)^{\frac{2}{3}})) $ と評価されます。これは「準指数関数的（Sub-exponential）」な時間計算量と呼ばれます。指数関数時間よりは速いものの、多項式時間（Polynomial time）よりは遥かに遅い計算量です。
実際に、2020年には国際的な研究チームがGNFSを用いてRSA-250（829ビット、250桁の合成数）の素因数分解に成功しました。この計算には、世界中の計算機リソースをかき集めて約2700 CPUコア年という膨大な計算時間を費やしています。しかし、これが2048ビットとなると、必要な計算量は宇宙の寿命の数兆倍にも膨れ上がると言及されており、現在のスーパーコンピュータをどれだけ並列稼働させても、古典的な手法では現実的な時間内で解読することは不可能です。
量子コンピュータの切り札：ショアのアルゴリズム
ここで登場するのが、1994年にピーター・ショア（Peter Shor）によって発表された「ショアのアルゴリズム」です。このアルゴリズムは、素因数分解問題を量子コンピュータ上で 多項式時間 （ $ O((\log N)^3) $ ）で解くことができるという画期的なものでした。準指数関数時間と多項式時間の差は決定的なものであり、理論上、量子コンピュータを使えばRSA暗号は完全に破壊されることを意味します。
ショアのアルゴリズムの全体フロー
mermaid graph TD A[素因数分解したい数 N を入力] --> B[ランダムな整数 a を選択] B --> C{a と N の<br>最大公約数} C -->|1より大きい| D[幸運にも素因数を発見！] C -->|1 互いに素| E[量子コンピュータの出番] E --> F[関数 f_x = a^x mod N の<br>周期 r を量子フーリエ変換で求める] F --> G{周期 r が偶数 かつ<br>a^r/2 ≢ -1 mod N} G -->|Yes| H[最大公約数 gcd_a^r/2 ± 1, N を計算] H --> I((素因数分解 成功！)) G -->|No| B
ショアのアルゴリズムは、素因数分解という問題を直接解くのではなく、数論の定理を用いて「周期発見問題（Period Finding Problem）」という別の問題に変換し、それを量子コンピュータの特性を活かして高速に解くというアプローチをとります。
ステップ1：素因数分解から周期発見問題への還元（古典的処理）
アルゴリズムの最初のステップは古典コンピュータで行われます。 素因数分解したい数 $ N $ に対して、$ N $ と互いに素な（最大公約数が1の）ランダムな整数 $ a $ （ $ 1 < a < N $ ）を選びます。もし偶然にも最大公約数が1でなければ、その時点で見つかった公約数が $ N $ の素因数なので解読完了ですが、確率は極めて低いです。
次に、以下のモジュロ方程式の列を考えます。 $ f(x) = a^x \pmod N $
この関数 $ f(x) $ に $ x = 1, 2, 3, \dots $ と代入していくと、値はランダムなように見えますが、有限の範囲内で計算しているため、必ずどこかで元の値に戻り、同じ数列を繰り返します。この繰り返しの周期を $ r $ と呼びます。つまり、 $ a^r \equiv 1 \pmod N $ となる最小の正の整数 $ r $ を見つける問題、これが「周期発見問題」です。
もしこの周期 $ r $ が見つかり、かつ $ r $ が偶数であれば、$ a^r - 1 \equiv 0 \pmod N $ となり、因数分解の公式を用いて $ (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod N $ と変形できます。ここから、ユークリッドの互除法を使って $ N $ と $ a^{r/2} \pm 1 $ の最大公約数を計算することで、$ N $ の素因数が極めて高い確率で得られます。
古典コンピュータで周期 $ r $ を見つけるためには、結局のところ指数関数的なステップが必要となり高速化できません。しかし、量子コンピュータならばこの周期 $ r $ を一瞬で（多項式時間で）見つけることができるのです。
ステップ2：量子状態の準備と重ね合わせ
ここからが量子コンピュータの出番です。 量子コンピュータは、「0」と「1」の状態を同時に持つことができる「量子ビット（Qubit）」を使用します。ショアのアルゴリズムでは、入力を格納するレジスタ（第1レジスタ）と、計算結果を格納するレジスタ（第2レジスタ）の2つを用意します。
まず、アダマールゲート（Hadamard gate）と呼ばれる量子ゲート操作を第1レジスタの全ての量子ビットに適用します。これにより、第1レジスタは考え得るすべての $ x $ の値（ $ 0 $ から $ 2^n-1 $ まで。$ n $ は十分大きなビット数）の 均等な重ね合わせ状態 になります。
つまり、量子コンピュータの内部には、$ x=0, 1, 2, 3, \dots $ という無数の入力値が同時に並行して存在している状態が作られます。
ステップ3：量子モジュロべき乗算（Quantum Modular Exponentiation）
次に、第1レジスタの重ね合わせ状態を入力として、$ f(x) = a^x \pmod N $ を計算し、その結果を第2レジスタに格納します。 この計算は量子回路上のユニタリ変換として実行されるため、重ね合わせが保たれたまま、すべての $ x $ に対する $ f(x) $ の計算が「同時並行的に（量子並列性）」行われます。
この時点での量子システム全体の空間は、 $ |x, a^x \bmod N\rangle $ という状態の膨大な重ね合わせになっています。
しかし、ここで単純に第2レジスタを測定（観測）してしまうと、ランダムな $ a^x \bmod N $ の値が一つだけ確率的に選ばれ、それに連動して第1レジスタの $ x $ も一つに確定してしまいます。これでは古典コンピュータで一回計算したのと同じことで、周期 $ r $ を見つけることはできません。
量子力学のルールでは、重ね合わせ状態の中身を直接覗き見ることはできないのです。では、どうやって全体の「周期」というグローバルな情報を抽出するのでしょうか？
ステップ4：量子フーリエ変換（QFT: Quantum Fourier Transform）
この壁を突破するショアのアルゴリズムの真骨頂が、第1レジスタに対する 量子フーリエ変換（QFT） の適用です。
測定を行う前に、関数 $ f(x) $ の波の性質を解析します。第2レジスタを観測したと仮定しましょう。ある値 $ y $ が得られたとします。すると、第1レジスタの状態は「 $ a^x \pmod N = y $ となるような全ての $ x $ の重ね合わせ」に収縮します。 この $ x $ の値は、$ x_0, x_0 + r, x_0 + 2r, x_0 + 3r, \dots $ のように、周期 $ r $ の間隔で離散的に並んだ状態（一種の櫛状の確率振幅分布）になります。
この状態に対して量子フーリエ変換（QFT）を適用します。古典的な離散フーリエ変換が時間領域の信号を周波数領域に変換するように、QFTは量子状態の確率振幅に干渉を起こさせます。
QFTをかけると、量子干渉効果によって、周期 $ r $ と共鳴しない（位相が揃わない）誤った答えの確率は互いに打ち消し合ってゼロに近づき（破壊的干渉）、周期 $ r $ の情報を持つ正しい答えの確率だけが増幅されます（建設的干渉）。
ステップ5：測定と連分数展開（古典的後処理）
QFT適用後に第1レジスタを測定すると、非常に高い確率で $ c \approx \frac{j \cdot 2^n}{r} $ という形に近い整数 $ c $ が得られます（ $ j $ は未知の整数、$ 2^n $ はレジスタのサイズ）。
この測定結果 $ c $ を古典コンピュータに戻し、$ \frac{c}{2^n} \approx \frac{j}{r} $ という分数を作ります。そして、数学的手法である「連分数展開（Continued fraction expansion）」を用いて近似値を計算することで、分母である周期 $ r $ を見事にあぶり出すことができます。
$ r $ が分かれば、あとはステップ1の公式を使って $ N $ の素因数を計算し、RSA暗号は完全に解読されます。
現状の量子コンピュータ（NISQ）の実力と課題
理論的には完璧なショアのアルゴリズムですが、「明日にもRSA暗号が破られるのか？」と問われれば、答えは明確に「ノー」です。その理由は、現在の量子コンピュータのハードウェア技術の限界にあります。
NISQ（Noisy Intermediate-Scale Quantum）時代
現在我々が存在しているのは、「NISQ」と呼ばれる時代です。NISQデバイスは、数十から数百の物理量子ビットを持ちますが、ノイズに対して極めて脆弱です。
量子ビットは、熱や電磁波などの外部環境の影響を受けやすく、量子状態が壊れてしまう「デコヒーレンス（量子もつれ喪失）」や、ゲート操作時の「ゲートエラー」が頻繁に発生します。ショアのアルゴリズムのような非常に深い（演算ステップ数が膨大な）量子回路を実行しようとすると、計算の途中でエラーが蓄積し、最終的な出力は意味を持たない完全なノイズになってしまいます。
物理量子ビットと論理量子ビット
このエラー問題を解決するために不可欠なのが「量子誤り訂正（Quantum Error Correction）」です。 古典コンピュータでも誤り訂正コードは使われていますが、量子状態の複製を禁じる「量子複製不可能定理」があるため、量子誤り訂正は非常に複雑です。
量子誤り訂正では、「表面符号（Surface Code）」などの技術を用いて、多数のノイズだらけの「物理量子ビット」を組み合わせることで、エラーのない理想的な1つの「論理量子ビット」を作り出します。
現在のエラー率を前提とすると、1つの論理量子ビットを作るためには、およそ1,000〜10,000個の物理量子ビットが必要になると試算されています。これを「誤り訂正のオーバーヘッド」と呼びます。
RSA-2048を破壊するために必要なリソースとは？
では、実際にRSA-2048を解読するために、ショアのアルゴリズムを走らせるにはどれくらいのリソースが必要なのでしょうか？
Craig Gidney (Google) と Martin Ekerå による2021年の論文による画期的なリソース推定では、最適化されたショアのアルゴリズムを使用し、表面符号による誤り訂正を行った場合、以下のリソースが必要になるとされています。
- 論理量子ビット数 : 約 4,096 個
- 物理量子ビット数 ** : ** 約 2000万個 （エラー率 $10^{-3}$ 程度を仮定）
- 計算時間 : 約 8時間（物理ゲート操作が数百万〜数十億回必要）
これに対して、現在の量子ハードウェアの到達点はどうでしょうか。 2023年末にIBMが発表した超伝導量子プロセッサ「Condor（コンドル）」は 1,121 量子ビットです。また、論理量子ビットの生成に関する画期的な研究（ハーバード大学やQuEra社などによる中性原子量子コンピュータを用いた48個の論理量子ビットの生成など）も登場していますが、まだ「ノイズのない完璧な演算」を長時間連続して実行できる段階にはありません。
数千の物理量子ビットから、 2000万個 の実用的な物理量子ビット（かつ相互結線され、極低温で安定動作し、超高速で制御信号を処理できるシステム）へのスケールアップは、工学的にとてつもない壁（配線問題、冷却能力の限界、制御エレクトロニクスの肥大化）が存在します。多くの専門家は、RSA-2048を解読可能な「フォールトトレラント（誤り耐性）量子コンピュータ（FTQC）」が実現するには、少なくとも10年から30年、あるいはそれ以上の年月が必要だと予測しています。
忍び寄る「Store Now, Decrypt Later」の脅威とPQCの夜明け
「まだ10年以上かかるなら安心だ」と考えるのは早計です。現在、国家の機密情報や医療データ、長期的なインフラ設計など、数十年先まで秘密を担保しなければならないデータが存在します。
ここで懸念されているのが、 「Store Now, Decrypt Later（今保存して、後で解読する）」 という攻撃手法です。悪意のある国家や組織が、現在のRSAやECC（楕円曲線暗号）で暗号化された通信データをすべて傍受し、ストレージに保存しておくのです。そして10年後、20年後に強力な量子コンピュータが完成した瞬間に、ショアのアルゴリズムを用いて過去のデータをすべて解読し、秘密を暴露するという手法です。
このタイムラグの脅威に対抗するため、NIST（米国国立標準技術研究所）を中心に、 「耐量子計算機暗号（PQC: Post-Quantum Cryptography）」 の標準化プロセスが急ピッチで進められてきました。
PQCは、量子コンピュータを用いても解読が困難（つまり、ショアのアルゴリズムが適用できない）な数学的問題をベースにした新しい暗号アルゴリズムです。主なアプローチとして以下のようなものがあります。
- 格子暗号（Lattice-based cryptography） : LWE（Learning with Errors）問題などを基礎とする。NISTの標準化で主流（Kyber、Dilithiumなど）。
- 符号ベース暗号（Code-based cryptography） : 誤り訂正符号の復号問題の困難性に依存。
- 多変数多項式暗号（Multivariate cryptography） : 多変数の連立二次方程式を解く困難性に依存。
- ハッシュベース署名（Hash-based signatures） : ハッシュ関数の安全性のみに依存するデジタル署名。
すでにGoogle ChromeやAppleのiMessageなど、主要なソフトウェアやプラットフォームではPQCの導入テストやハイブリッド実装が開始されています。
おわりに
量子コンピュータは、SFの世界の夢物語から現実の工学的挑戦へと移行しています。ショアのアルゴリズムは、数学と量子力学が融合した人類の偉大な知的成果ですが、同時に我々のデジタル社会の基盤を揺るがす「破壊的な力」を秘めています。
RSA暗号が明日すぐに使えなくなるわけではありません。しかし、量子技術の進化と「Store Now, Decrypt Later」のリスクを鑑みれば、PQCへの移行という暗号史に残る大規模なマイグレーションはすでに始まっています。我々は今、情報セキュリティにおけるパラダイムシフトの最前線を目撃しているのです。