はじめに
この記事は、RSA の安全性・Shor の原理・Qiskit による因数分解ハンズオンを日本語で一気通貫に学べる教材の紹介です。
「量子コンピュータが完成すれば RSA 暗号は破られる」——このフレーズを聞いたことがない人はいないだろう、というくらい、量子コンピュータと RSA の話題は定着してきました。2019年の Google の「量子超越性」発表は、量子コンピューティングへの注目を押し上げた象徴的な出来事であり、その後も研究進展、投資拡大、ポスト量子暗号（PQC）への移行議論を背景に、検索関心や企業・政策面での関心は高い水準で推移しています。そして、量子コンピュータの最もインパクトのある応用先として、RSA 暗号を破ることが注目されています。
しかし量子系の話題は、ときに過度に誇張され、量子コンピュータがあたかも魔法のように語られることがあります。センセーショナルな見出しではなく、内容を正しく理解したうえで、いま何ができて、何ができないのかを自分の手で確認できる状態を目指したい
上記のように思って、「なぜ今 RSA 暗号は安全か？ 量子コンピュータでどうやって破るのか」という日本語教材を公開しました。
本記事では、その教材とハンズオンで何が手に入るのか、どう使えば何が腹落ちするのかを紹介します。
本記事に含まれる数値・標準化状況・ロードマップは、データカットオフ 2026年4月 時点のものです。量子コンピューティングは急速に進展する分野なので、最新状況は各一次情報をご確認ください。
1. この教材で得られるもの
この教材とハンズオンを一通り通すと、以下の問いが腹落ちする状態になります。
- RSA 暗号はどのような仕組みで動いているのか
- なぜ古典コンピュータでは破れないのか
- 量子コンピュータはどのような手順で RSA を破るのか
- 古典と比べてどれくらい速いのか
- なぜ今の量子コンピュータではまだ破れないのか
教材は 「読み物としての PDF」 と 「手を動かす Qiskit ハンズオン」 の2本立てで、どちらからでも読んで進められる構成にしています。
2. PDF 教材の中身
RSA 暗号は、HTTPS、デジタル署名、コード署名、S/MIME、KMS/HSM など、現代インターネットの屋台骨を広く支えています。だからこそ RSA が破られると、中間者攻撃、コード署名の偽造、過去メールの復号、鍵管理システムの突破と、影響はインフラ全体に及びます。さらに Harvest Now, Decrypt Laterのように、今の通信が将来復号されるリスクまで考えると、「量子コンピュータが RSA を破る」は遠い未来の話ではなくなります。
この規模感を入り口に、なぜ RSA が今は安全とされているのか、Shor はそれをどう破るのか、そしてなぜ今の量子コンピュータではまだ動かないのかを一本の線で扱うのが本教材です。
PDF は 3 部構成です。
-
第1部：RSA の安全性と RSA 暗号の原理
RSA の仕組みと、その安全性が「素因数分解の計算量的困難さ」に乗っていることを示す。高校数学の範囲で読める。 -
第2部：Shor のアルゴリズム
位数発見への帰着、量子位相推定（QPE）、Shor の全手順、実用性の分析（NISQ／FTQC、PQC 移行）まで。 -
第3部：ハンズオン
$N=15$ を題材に、Qiskit で加算器から段階的に量子回路を組み上げて、シミュレータで因数分解を完了。
特に意識したのは次の3点です。
-
数式を省略しない
式や導出を極力省略せず、各ステップで何が起きているかを追えるように書いています。 -
アルゴリズムの解説で終わらせず、一本のストーリーで理解する
RSA はなぜ現代社会を支えているのか → Shor はそれをどう破るのか → なぜ今の量子コンピュータではまだ動かないのか → それでもなぜ各国政府は 2030 年からの移行を求めているのか ——この一連の流れを、繋がった物語として追えます。 -
汎用回路ベースのハンズオン
よくある「$n=15$ 専用にハードコードされた簡略回路」ではなく、他の数にも拡張できる汎用回路の実装を採用しました。Beauregard (2003) の量子モジュラー算術回路をベースにしています。
↑ PDF の一例。
3. ハンズオンで体験できること
3-1. Shor の量子回路を一から組み上げる
Colab で開いて上から実行すると、$N=15 = 3 \times 5$ の素因数分解が 18 qubit の量子回路 で完走します。構築の順序は以下の通りです。
Draper 加算器（QFT 空間での位相加算）
↓
モジュラー加算（符号判定 ancilla 付き）
↓
モジュラー乗算（Beauregard の SWAP + 逆元による uncompute）
↓
制御モジュラー累乗（a^(2^k) mod n を各制御ビットに配置）
↓
IQFT → 測定 → 連分数展開 → 素因数
加算器から順にレイヤを積み上げるので、各段階で何が起きているか を確認しながら進められます。
実行すると、$r = 4$ に対応する 4 本の鋭いピーク（$z = 0, 256, 512, 768$）が立ちます。
↑ 理想的な場合の測定ヒストグラム。
測定値から古典計算で位数 $r$ を復元し、素因数 ${3, 5}$ に到達します。
測定値は $z = 256$ です。
\frac{z}{2^M} = \frac{256}{1024} = 0.25 \to [0;4] \to \frac{1}{4} \to r = 4
位数が$4$であることをチェックします。
7^4 \bmod 15 = 2401 \bmod 15 = 1
素因数は以下のように求められます (詳しくは本編参照)。
\gcd(7^2 + 1, 15) = \gcd(50, 15) = 5
\gcd(7^2 - 1, 15) = \gcd(48, 15) = 3
したがって、以下の素因数分解ができました。
15 = 3 \times 5
3-2. ノイズを入れて、FTQC がなぜ必要かを実感する
Shor のアルゴリズムを実現する回路を理想的なシミュレータで動かして中身を理解したあと、あえて Qiskit のノイズモデルを差し込んで同じ回路を実行します。
現在主流の量子コンピュータは誤り訂正を備えない NISQ であり、ノイズのある中でも意味のある結果を引き出せるように、比較的浅い回路や限定的な用途で使われることが多いです。
本ハンズオンでは、NISQ デバイスをそのまま Shor のような大規模で深い回路に利用するとどのような限界があるのかを体感し、安定した実行に FTQC が必要であるということを改めて理解します。
以下の図は、量子回路を何度も実行したときに、最後にどの値がどれくらいの頻度で出たかをまとめたヒストグラムです。
横軸は観測された値、縦軸はその値の出現回数を表します。
理想的には特定の値に山が立ちますが、ノイズが増えると山が崩れて値がばらけ、そこから周期（位数）を読み取るのが難しくなります。
4. この教材を作った動機
Shor のアルゴリズムに触れた資料は存在します。英語なら Nielsen & Chuang、日本語でも Shor を一章として扱う教科書や入門記事があります。
ただ、RSA がなぜ重要なのかという現実の文脈から、Shor の数式の丁寧な導出、動く汎用回路のハンズオン、さらにノイズと FTQC、PQC 移行までを日本語で一本の線として辿れる資料は、少なくとも私が調べた範囲では見つけられませんでした。
そもそも量子コンピュータがここまで注目されているのは RSA を破ることが大きな要因で、RSA は現代インターネットの屋台骨です。これだけ重要な話題を、日本語で一歩一歩辿れる資料は、必ず必要だろうという思いで、読み物 ＋ ハンズオンとして一歩を踏み出しました。
独力で書いたので見落としがあるかもしれません。気づいたことがあれば、GitHub の Issue で教えていただけると嬉しいです。
5. リンク
-
教材の公開ページ
QUBOOK Research / rsa-shor — PDF と Notebook の最新版はこちら -
公開リポジトリ（GitHub）
rsa-shor-article — Issue での補足・誤り報告はこちら