1.はじめに
この記事の目的
量子コンピュータは「何でも高速に解けるスーパーコンピュータ」ではありません。
特定の種類の計算に限って、従来の計算機では“指数時間”かかる問題を、“現実的な時間”に短縮できてしまう可能性があるという性質をもちます。
（そのうち汎用量子コンピュータなるものが登場するかもしれませんが、少なくとも現時点では）
これは「CPUを強くした」「GPUを増やした」といった性能向上とは別の次元で、計算の仕組みそのものを変えてしまう点が重要です。ただしスパコンと同様、量子コンピュータのユースケースは日々の生活と直接結びつかないものも多く、ピンと来ないことが少なくありません。
本来、量子コンピュータはその可能性を活かせる分野でこそ輝くべきです。たとえば、創薬や医療といった領域です。一方で、負の側面として「現在の暗号方式が無力化され得る」というリスクから目を背けることもできません。結果として、「暗号が解読されてしまって、なんかヤバそう」という話が先行しがちです。
だからこそ、「量子コンピュータ、ヤバい」で思考を止めるのではなく、流れる数字やパケットに想いを馳せてみるのが大事です。何が前提になっていて、どこが崩れ得るのかをイメージできると、過度に怖がるのでも軽視するのでもなく、正しく恐れることができます。そして、その理解があってこそ、必要な対応（いつ、何を、どこまで）の判断につながります。
最終的に、実務としてできることが「設定項目のドロップダウンから“強い暗号”を選ぶ」だけだったとしても同じです。選ぶという行為は同じでも、何を守っていて、どのリスクに備えているのかが分かっているかどうかで、設計や運用の意思決定は大きく変わるはずです。
そんな問題意識から、特に「ヤバい」と言われがちな RSA を例に、何がどう「ヤバい」のかを整理してみます。
説明すること
- RSAを例にした暗号通信の計算の流れ
（RSA“っぽい”簡易TLSを題材に、暗号通信の仕組みを追います） - 仕組みが分かっても、なぜ従来の計算機では問題になりにくかったのか
- 量子コンピュータは何ができるから、RSAにとって脅威になり得るのか
- 実機の量子コンピュータが登場しているにもかかわらず、2025年現在「まだ安全」と言える理由
説明しないこと
- 実際に使われているTLSの解読方法
（この記事を読んでも、TLSを直接“復号”できるようにはなりません） - PQCアルゴリズムそのものの解説
2.暗号通信の雰囲気をざっくりおさらい
まずは、暗号化ってなんだっけ？を超ざっくりおさらいします。
文字列を計算してズラす、が暗号
たとえば "Hello" を送りたい（通信）したいとします。
コンピュータ上では文字を数字として扱います。（ASCIIやUTF-8 など）
便宜上、次のように表すとします。
H e l l o (伝えたい言葉)
↓
072 101 108 108 111 (Helloを数字に置き換える）
ここで、“+37 だけ足す” という 超単純な暗号化方式 を考えてみます。
平文: 072 101 108 108 111
↓ 暗号化: (72+37) (101+37) ...
暗号文: 109 138 145 145 148
受け取った側は、37 を引けば元に戻ります。
暗号文: 109 138 145 145 148
↓ 暗号化: (72+37) (101+37) ...
平文: 072 101 108 108 111
この「暗号化のルール」の元になっている値（ここでは 37）を“共有鍵” と呼びます。
もちろん実際の通信では「37文字ずらしただけ」よりも複雑な計算が行われます。
ポイントは、「37 だけ足す(だから37引けば戻る)というルールを秘密裏にどう共有するか？」です。
そのため、通信に先立ち、共有鍵を秘密裏に共有する"何かしらの方法"が必要になります。
その方法を鍵交換と呼びます。
暗号化はデータそのものを暗号化する共有鍵(結局は数字）と、暗号鍵を共有する方法（鍵交換）で成り立つ
TLSにおける鍵交換
先の例で、知り合い同士なら事前にまったく別の方法で、共有鍵(この例では37という数字)を共有しておけばよいかもしれません。
例えば、電話やメールもしくは直接会って話すなどです。
しかしインターネットの通信（TLS）、でクライアントとサーバがこれから通信をする…という場合、そのような方法はとれません。
- 共有鍵（例えば"37という数字"） を使って、通信を共通鍵暗号（AES など）で暗号化したい
- しかし共有鍵（"37という数字"） そのものは盗聴者に知られてはいけない！（だが、37と伝えたい）
そこで使われるのが、公開鍵暗号による鍵交換です。
その公開鍵暗号と呼ばれる方式の代表例が RSA です。
TLS やRSAの細かい仕様は一旦省いて、「決まり通りに計算して、共有鍵（ここでは “何文字ズラすか” の情報）を秘密裏に渡す」という構造だけに絞って見ていきます。
3. 雰囲気で理解する RSA 鍵交換
3.1 キーペア（秘密鍵と公開鍵）を作る流れ
TLSの説明では、よく聞く「サーバ証明書」と併せて、秘密鍵、公開鍵という言葉が出てきます。
RSA の秘密鍵／公開鍵ペア は、だいたい次のように作られています。
-
適当な2つの素数を選ぶ
- 例：
- (p = 59)
- (q = 47)
- 例：
-
掛け合わせてnを計算する
- 例：
- $n = 59 \times 47 = 2773$
- 例：
-
この2つの素数から1引いた数同士を掛け合わせる
- $\varphi(n) = (p-1)(q-1)$
- ※ $\varphi(n)\ トーシェント$関数 と呼ばれる
- 例：
- $\varphi(2773) = (59-1) \times (47 -1) = 58 \times 46 = 2668$
-
次の条件を満たす整数 $e$ を 1 つ選ぶ
- $1 < e < \varphi(n)$
- $e$と$\varphi(n)$の最大公約数が1 ※$\gcd(e, \varphi(n)) = 1$ と書き表す
（互いに素な数字を選ぶ） - 例：
- $(e = 17$ とすると $\gcd(17, 2668) = 1$（互いに素） なので条件を満たす
-
次を満たす整数 (d) を求める
- 式：
$[
e \times d \equiv 1 \pmod{\varphi(n)}
$]
※ mod x とは xで割った"余り"です。$7 \bmod 3$であれば$7÷3=2あまり1$なので$1$になります - 例：
- (d = 157) とすると
$17 \times 157 = 2669$
$2669 \bmod 2668 = 1$ （よって条件を満たす）
- (d = 157) とすると
- 式：
この結果、次の数字のペアが作れます。
-
公開鍵（みんなに見せてよい）
$ (e, n) = (17, 2773) $ -
秘密鍵（絶対に漏らしてはいけない）
$ (d, n) = (157, 2773) $
「あれ？長い文字列（数字）じゃないの？」と思うかもしれませんが、実際のopennssl で作られる鍵ファイルも、実は中には複数の数字が含まれています。"くっついているだけ"のようなイメージです。
ここまでのまとめ①
細かいことをさておくと、素数を2つ選んで($p$と$q$)、それを上の手順に従って計算すると公開鍵、秘密鍵と言われる数字の組み合わせが作れる！とざっくり理解して次に進みましょう
3.2 なんちゃって鍵交換シーケンス
TLS の本物のハンドシェイクを単純化して、
「あくまで RSA の “エッセンス” だけを抜き出したシーケンス」を考えます。
※ 実際には途中でサーバ側やクライアント側で作った乱数による計算が含まれるなど、もう少し手続きが複雑です。
クライアントは、共有鍵として “37 文字ずらす” という情報（$K=37$）を持っている
これを サーバの公開鍵 $(e, n)$ で暗号化して送る…というイメージです。
このとき、盗聴中の第三者（攻撃者） が見られる値と、見えない（見られてはいけない）値はこう整理できます。
| 種類 | 値 |
|---|---|
| 見える | $n$...適当に選んだ素数を掛け合わせた数 $e$ ...公開鍵の情報 $C$...eとnを使って暗号化した$K$ |
| 見えない | $p, q $...適当に選んだ素数 $d$...秘密鍵の情報 $K$...秘密の情報(共有鍵)) |
ここまでのまとめ②
- 最初に適当に選んだ2つの素数($p$と$q$)は秘密
- pとqを掛け合わせた数字nはネットワーク上を流れるため、盗聴中の第三者に見られる恐れがある
さて感覚でいえば、「秘密鍵 $(d, n)$ を知られてはいけない」というイメージを持ちますが、
もう一歩踏み込むと、
「$n$ を素因数分解して $p, q$ が分かると、$d$ が計算できる」
→ 結果として盗み見れた $n$ から $K$(共有鍵) も計算できてしまう。
という構造になっています。
つまり、RSAは『素因数分解は難しい』という仕組みに頼っているのです。
4. 因数分解の計算方法（周期 r が重要な理由）
次に「$n$ を素因数分解できてしまう」と何が起きるのかを、“周期 $r$” というキーワードで追います。
素因数分解の計算方法と、計算方法がわかっているけど難しいのはなぜか？を順を追って眺めていきます。
4.1 「ある数を何回も掛けて特定の数で割ると、必ず余り 1 に戻る周期がある」
まず、重要な法則があります。
ある数 $a$ を何回も掛けて $n$ で割り続けると、
ある回数 $r$ で余りが 1 になる。
その後は $r$ を周期として繰り返す。
これを、実際に 小さな数字で確かめてみます。
4.1.1 具体例その１: 2のk乗を31で割った余り
たとえば、「2 を何回も掛けて 31 で割った余り」を見てみます。
2 ÷ 31 = 0 あまり2
2×2 ÷ 31 = 0 あまり4
2×2×2 ÷ 31 = 0 あまり8
2×2×2×2 ÷ 31 = 0 あまり16
2×2×2×2×2 ÷ 31 = 1 あまり 1
これを繰り返していきます。
次のようなpythonのコードで確認できます。
import pandas as pd
a = 2 //2の0乗、1乗、2乗…と順にやっていく
mod = 31 //31で割った余りを出す
rows = []
# 表のカラム名
col_power = f"{a}^k"
col_remainder = f"{mod}で割った余り"
col_quotient = f"{a}^k÷{mod}の商"
for k in range(0, 200):
power = a ** k
quotient = power // mod
remainder = power % mod
rows.append({
"k": k,
col_power: power,
col_quotient: quotient,
col_remainder: remainder
})
df = pd.DataFrame(rows)
// 最初の15個だけ表示
df.head(15)
| k | 2^k | 2^k ÷ 31 の商 | 31で割った余り |
|---|---|---|---|
| 0 | 1 | 0 | 1 |
| 1 | 2 | 0 | 2 |
| 2 | 4 | 0 | 4 |
| 3 | 8 | 0 | 8 |
| 4 | 16 | 0 | 16 |
| 5 | 32 | 1 | 1 |
| 6 | 64 | 2 | 2 |
| 7 | 128 | 4 | 4 |
| 8 | 256 | 8 | 8 |
| 9 | 512 | 16 | 16 |
| 10 | 1024 | 33 | 1 |
| 11 | 2048 | 66 | 2 |
| 12 | 4096 | 132 | 4 |
| 13 | 8192 | 264 | 8 |
| 14 | 16384 | 528 | 16 |
割り算の「余り」の列だけを見ると
1 → 2 → 4 → 8 → 16 → 1 → 2 → 4 → 8 → 16 → 1 → …
と、5ステップごとに繰り返しになっていることが分かります。
この「戻ってくる回数」のことを、ここでは 周期 $r$ と呼びます。
この例では
$a = 2, n = 31$ のとき、周期 $r = 5$
になっているといえます。
4.1.2 具体例その2: 5のk乗を97で割った余り
ただの偶然ではありません。同じことを、もう少し大きな数でやってみます。
$5^k \bmod 97$ の余りをプロットしてみると、96 で周期になることが分かります。
(表で見れる範囲ではなくなってくるので、pythonで合わせてグラフにしてみます)
!pip install japanize-matplotlib #日本語フォントを表に出すため
import matplotlib.pyplot as plt # グラフを表示させるため
import japanize_matplotlib # 日本語をグラフに表示させるため
import pandas as pd
a = 5 #5の0乗、1乗、2乗…と順にやっていく
mod = 97 #97で割った余りを出す
rows = []
# 表のカラム名
col_power = f"{a}^k"
col_remainder = f"{mod}で割った余り"
col_quotient = f"{a}^k÷{mod}の商"
for k in range(0, 200):
power = a ** k
quotient = power // mod
remainder = power % mod
rows.append({
"k": k,
col_power: power,
col_quotient: quotient,
col_remainder: remainder
})
df = pd.DataFrame(rows)
col = col_remainder
plt.figure(figsize=(15,5))
plt.stem(df["k"], df[col])
plt.xlabel("k")
plt.ylabel(col)
plt.title(f"{col} の推移")
plt.tight_layout()
plt.show()
グラフを見ただけでも、パッと見解らないかと思いますが、96が周期です。
この図の矢印の区間を見比べると同じ形をしています。
（このPythonコードでdf.head(96)と96番目を表示させると1が出力されます）
偶然ではなく、余りが1に戻るまで繰り返すことが、周期の発見になります。
さて、全ての数の0乗は1であり、余りは必ず1になります。つまり0乗、1乗、2乗…と順にすすめるスタートは必ず1です。そこから先は同じ事が繰り返されます。
つまり、$a=5, n=97$ のときの周期 $r$ は 96 です。
この例では、確かめるために200までグラフにしていますが、余りが1になるところまでやり続けばそこで答えがでます。（この場合は96で決着がついていた）
5. 周期 r がわかると、なぜ因数分解できるのか？
いよいよ、本命の例です。
さきほど RSA で使った
$p = 59$
$q = 47$
$n = p \times q = 2773$
に対して、周期rを確認し、「$n$ を因数分解できるか？」を試みます。
5.1 2のk乗÷2773の「余り」をひたすら計算
さきほどと同じように、$2^k \bmod 2773$ をひたすら計算してみます。
import pandas as pd
mod = 2773
a = 2
rows = []
col_power = f"{a}^k"
col_remainder = f"{mod}で割った余り"
col_quotient = f"{a}^k÷{mod}の商"
for k in range(0, 1400):
power = a ** k
quotient = power // mod
remainder = power % mod
rows.append({
"k": k,
col_power: power,
col_quotient: quotient,
col_remainder: remainder
})
df = pd.DataFrame(rows)
df.head(1335)
このような結果が表示されるはずです。
Python で計算すると、
$2^{1334} \bmod 2773 = 1$
になることが分かります。
つまり、$a = 2, n = 2773$ のときの周期 $r$ は
$r = 1334$
です！
（※ 最初に 1 に戻るのが 1334 回目だから）。
ちなみに、2の1334乗は、次の数字になるそうです。
※上記のpythonの実行結果より
374985276428703810735456287859673818921846987112098509858540696486402339250994194813130173505541808775227745724548926240208515352260446333571082584861995365664331917769322592270044705130928796739644590232645932343679367573877163311985022600673898172538428442470135024151638941838672279333776785607267978048016009671733985254222395852694791808290363609146384953995959044219480327342312676656413025501184
上の数字を2773で割ったときの、商と余りは次の数だそうです。
135227290453914104123857298182356227523204827663937435938889540745186563018750160408629705555550598187965288757500514331124599838536042673483982179899745894577833363782662312394534693519988747471923761353280177549109039875181090267574836855634294328358611050295757311269974374986899487678967466861618455841332855994134145421645292409915179159138248687034397747564355948149830626520848422883668599171 … あまり 1
5.2 2の1334乗-1 は2773で割り切れる…ということは？
$2^{1334}$ を$2773$で割ると$1$余るとうことは、
$2^{1334}$ は「$2773$で割ると、ちょうど1だけ多い数」
ということですね。
言い換えると、
$2^{1334}=2773×K+1$
となる数$K$が存在するということです。
この両辺から$1$を引くと、次の形になります。
($2^{1334}- 1) = 2773 \times K$
ここで、$K$は重要ではなく、右辺は「$2773$の倍数」なので、左辺も「$2773$の倍数」というのがポイントです。
ここで、中学〜高校のときに習った公式を思い出します。
$(x^2 + 1)(x^2 - 1) = x^4 + x^2 - x^2 - 1 = (x^4 - 1)$
という、有名な（？）公式があったはずです。
これは、
$(x^r - 1) = (x^{\frac{r}{2}} + 1)(x^{\frac{r}{2}} - 1) $
と、表せます。
同じノリで、rを1334とすると、1334を2で割った数は667なので
$(x^{1334} - 1) = (x^{\frac{1334}{2}} + 1)(x^{\frac{1334}{2}} - 1) $
となります。
つまり、
$(x^{667} + 1)(x^{667} - 1) = 2773 の倍数 $
となります。
$n = 2773$ は 素数$p \times$と素数$q$ の形（ここでは $59 \times 47$）なので、
$2^{667} + 1$ の中にどちらかの素数（例えば $59$）が含まれていて、
もう片方の素数（$47$）は $2^{667} - 1$ のほうに含まれている
可能性があります。
ここで、$2^{667} \pm 1$ と $2773$ の最大公約数(gcd)を求めると、$p$ や $q$ を直接引きずり出せることが期待できます。
5.3 ユークリッドの互除法で最大公約数を求める
最大公約数 $\gcd(A, B)$ を求めるための計算方法として、ユークリッドの互除法が使えます。
ざっくり言うと、
1. 大きい方を小さい方で割る
2. 余りを次の「小さい方」として、また割る
3. 余りが 0 になったところの「割る側」が最大公約数
という手順です。
簡単な例として、$544$と$119$の最大公約数を求める場合を試してみます。
$544$ と $119$の最大公約数は$17$と割り出せます。
※ $17 \times 32 = 544$、$17 \times 7 = 119$ でどちらも17の倍数
さて、これをpythonにすると次のようになります。
import pandas as pd
# パラメータ
N = 2773
a = 2
# 2^667 を一発で計算（Python の pow は大きな整数もOK）
x = pow(a, 667) # 2^667
B1 = x - 1 # 2^667 - 1
B2 = x + 1 # 2^667 + 1
print("2^667 =", x)
print("----")
def euclid_steps(A, B):
"""
ユークリッドの互除法を途中経過ごとに記録する。
戻り値: (steps_df, gcd)
steps_df は A, B, quotient, remainder を並べた DataFrame
"""
steps = []
while B != 0:
q = A // B
r = A % B
steps.append({
"A": A,
"B": B,
"商 q": q,
"余り r": r,
})
A, B = B, r
gcd = A
df = pd.DataFrame(steps)
return df, gcd
# パターン1: gcd(2^667 - 1,2773)
df1, g1 = euclid_steps(B1,N)
print("gcd(2773, 2^667 - 1) =", g1)
display(df1) # Colab なら表として出ます
# パターン2: gcd(2^667 + 1,2773)
df2, g2 = euclid_steps(B2,N)
print("gcd(2773, 2^667 + 1) =", g2)
display(df2)
このコードを実行すると結果が、次のように表示されます。
無事に、$2773$が$47$と$59$に素因数分解できました。
この意味を確認するために、もう一度、先ほどの「なんちゃって鍵交換」登場した数字と共に振り返ってみましょう。
ここまでのまとめ（何が懸念されることなのか）
| 種類 | 値 |
|---|---|
| 見える | $n$...適当に選んだ素数を掛け合わせた数 $e$ ...公開鍵の情報 $C$...eとnを使って暗号化した$K$ |
| 見えない | $p, q $...適当に選んだ素数 $d$...秘密鍵の情報 $K$...秘密の情報(共有鍵)) |
知られたくない素数 $p, q$ は、本来は公開されているはずの $n = p \times q$ から逆算できてしまう。
ある数 $a$ に対して $a^k \bmod n$ を繰り返すと、必ず周期 $r$ が現れる。
この周期 $r$ が分かると、
$a^r - 1$ =$(a^{r/2} \pm 1)$ と $n$ の最大公約数を求めることで
$p, q$ を計算で取り出せてしまう
ここまでの例では、
最初に選んだ素数 $p = 59, q = 47$
鍵の生成自体は「少し算数が得意な小学生〜中学生」でも追えるレベル。
一方で逆算は周期 $r$ を使い、かなり大きな数の計算が必要。
(2桁の素数程度で、あの桁数にまで膨れ上がる計算量。
2を1334回掛けて割ってを順に繰り返し繰り返しやる必要がある！)
5.5. それでも RSA が「今はまだ」安全と言えている理由
実際の RSA では、$p, q$ は 何百桁もの巨大な素数が使われます。
代表的なものは 2048 ビット RSA などです。
同じことを素直にやろうとすると、
- $a^k \bmod n$ の周期 $r$ を見つけるまでの試行回数が 天文学的
- $\Rightarrow$ 古典コンピュータでは 現実的な時間で解けない
・・・という世界に突入します。
アルゴリズム（理屈や計算方法）は公開されていますが、総当り以外に速い方法がないので、実質的に解けない。
これが、「いまの RSA が安全」とされている理由です。
この計算方法が、あの有名なアニメ映画の暗号解読シーンのなりきり遊びができます！
6. 量子コンピュータはこの周期rを見つけるのが得意（Amazon Braket で “お遊び因数分解” の雰囲気を掴む）
いよいよ、量子コンピュータ側の話に触れます。
「周期 $r$ がわかると RSA が危ない」までを説明しました。
さて、量子コンピュータが得意とする計算の一つに、この周期$r$を割り出すというものがあります。
では、量子コンピュータはこの $r$ をどうやって高速に見つけるのか？
その代表的なアルゴリズムが Shor のアルゴリズムです。
この記事では、詳しい量子回路の内部までは踏み込みませんが、「Amazon Braket で Shor のアルゴリズムを動かすとこんな感じ」という雰囲気だけ掴んでおきます。
結論から先にいうと、現在ガチで使われているRSAの解読はここで紹介するやり方では遠く及びません。
さて、ここから紹介する入門はAWSにおいて、量子コンピュータを使って因数分解をする"雰囲気"をお伝えするものです。15の因数分解程度しかできません。
※ 『15の因数分解』は、ハンズオンでよく出てくるHello world的なものです。
●Amazon Braket
https://us-east-1.console.aws.amazon.com/braket/
6.1: 簡単な因数分解をやってみる流れ（前準備）
サービスアカウントとロールの作成
支出制限
量子コンピュータは1ショット(一回計算を投げ込む)のに対して、課金が発生します。
「うっかり、ものすごい計算量を投げ込んで、とんでもない請求額」という事が発生しないように支出制限をかけることができます。
（この記事の記載範囲だと、微々たるものしか発生しません）
Notebookの作成
Notebookを作成すると、そのジュピターノートブック上で量子コンピュータに計算を投げ込むことができます。
量子コンピュータを直接触るのは難しいので、APIを通じて計算を投入します。
LLMのAPIを扱ったことがある人なら、 OpenAIのAPIに投げ込むあの感じです。
pythonのコードでAPIに投げ込めば、結果が返ってくるあの感じです。
Notebook自体は以下のようなURLで開けるようになります。
そもそものURLに"sagemaker.aws"と入っていますし、SageMakerと同じものかもしれません。
https://amazon-braket-<個別の名前>.notebook.us-east-1.sagemaker.aws/lab
6.2: 簡単な因数分解をやってみる流れ（実行）
左側にサンプルやチュートリアルが用意されているので、ここから
Braket algorithms ⇒ textbook の順に辿っていきます。
すると、Shors_Algorithm.ipynb というものがあるのでこれを開きます（ダブルクリックで開きます）
このような画面が出てきます。
最初の説明書きに、がっつり「このノートブックでは、Amazon Braket SDK を使用して Shorのアルゴリズムをコードに実装し、15 を因数分解する簡単な例を実行します。」と書かれています。
In this notebook, you implement the Shor's algorithm in code using the Amazon Braket SDK and > run a simple example of factoring 15.
ついでにコードのコメントにも、「(currently 15, 21, 35 work)」と書かれています。15 を 3×5にしたり、21を3×7にするレベルの因数分解しかできないということですね。
コードの流れとしては
① この部分で、必要なライブラリを読み込んでいます。
from braket.devices import LocalSimulator
from braket.aws import AwsDevice
from braket.experimental.algorithms.shors.shors import (
shors_algorithm,
run_shors_algorithm,
get_factors_from_results,
)
LocalSimulatorはまんまですが、シミュレータです。
AwsDeviceは実際の量子コンピュータに投げ込むために必要なモジュールです。
三つめがShorのアルゴリズムを読み込む部分です。このShorのアルゴリズムというのが先ほど、周期rを計算して因数分解するという流れを示しています。これを量子コンピュータで実装したサンプルライブラリです。
① 続く、この部分が変数です。
N = 15 # Integer to factor (currently 15, 21, 35 work)
a = 7 # Any integer that satisfies 1 < a < N and gcd(a, N) = 1.
shors_circuit = shors_algorithm(N, a)
Nは因数分解したい対象です。aは2や7など適当な数です。
先ほどの例でいうとNに2773が入り、aに2を選ぶと、周期rが667で…因数分解すると47と59だ！
と出てくる…という雰囲気です。
ただし、前述のようにこのサンプルはさらに手前の35くらいしかできません。
なぜできないのか、の説明を後回しにして実際に動かしてみましょう。
③ まずはLocalSimuratorで動かします。
local_simulator = LocalSimulator()
output = run_shors_algorithm(shors_circuit, local_simulator)
guessed_factors = get_factors_from_results(output, N, a)
以下のような結果が出てきます。無事に3と5に因数分解できました。
| Number of Measured phases (s/r) : 4 For phase 0.75 :Estimate for r is : 4 Factors are : 3 and 5 For phase 0.25 : Estimate for r is : 4 Factors are : 3 and 5 For phase 0.5 : Estimate for r is : 2 Factors are : 3 and 1 For phase 0.0 : Estimate for r is : 1 Factors are : 15 and 1 Non-trivial factors found are : {3, 5} ← コレ |
|---|
このLocalSimulator() の箇所を本当のQPU(量子コンピュータ)に変更すると、実際にQPUで計算を行うことができます。
ですが、今回はそもそもの実装が15程度しかできない為、いったん雰囲気をつかむまでとしてここまでにしておきます。
6.3 なぜ 15 程度しか扱えないのか？（≒まだ量子コンピュータで簡単に暗号解読ができない理由）
「Shorのアルゴリズム」の実装コードは、GitHub で公開されています。
これも中身を見ると、15の総因数分解程度のことしかできないと書かれています。
ただ、じゃあどこかに書かれている変数を大きくすれば制限解除できるのか？というと、そういうレベルの話ではありません。
- 必要な量子ビット数が増えると、回路が爆発的に大きくなる
- 実機の QPU も、数十〜数百量子ビット程度が限界（研究の最前線で 256 量子ビットなど）
といった事情から、サンプル実装では「15, 21, 35 くらいまで」という制限が生まれています。
例えば、$N = 2773$ に対して Shorのアルゴリズムをそのまま適用しようとすると、
必要な量子ビット数や回路深さが 現状の QPU のキャパを超えてしまうのです。
import numpy as np
integer_N = 2773
n = int(np.ceil(np.log2(integer_N)))
print(n) # → 12 （最低でもこの程度のビット数が必要）
二桁の素数同士の掛け合わせ（約 12 ビット）ですら、実機でちゃんと Shorのアルゴリズムを回すのはギリギリ！
…というのが、いまの量子コンピュータの「手に届く範囲」です。
例えば、us-east-1で利用できるデバイス（QPU)はコンソールの以下の画面から確認できます。どれも数十ビットの量子コンピュータです。
https://us-east-1.console.aws.amazon.com/braket/home?region=us-east-1#/devices
6.4 それでも「PQC を考え始めるべき」と言われる理由
今年、2025年4月に、理化学研究所が「世界最大級の256量子ビットの超伝導量子コンピュータを開発」と発表しています。
これが最先端に近い"現在地点"です。
一方、NTT が「2027年に 1万量子ビット、2030 年には 100万量子ビット」を目指すロードマップなど、量子ビット数のスケールアップ計画が本気で進んでいることも報じられています。
今は 256 量子ビットの世界でも、数年〜十数年スパンで、桁違いの量子ビット数が現実味を帯びてきている
という背景から、「今すぐ RSA が全部破られる」わけではありません。
しかし、「今のうちから “量子に強い暗号方式” に移行準備を始めないと手遅れになる」という問題意識で、PQC（Post-Quantum Cryptography：ポスト量子暗号） が真面目に議論されている、という構図になります。
7.じゃあPQCって、何がどう違うの？
ここまで本記事では、RSAを題材に「なぜ？どこがヤバいのか」を、順を追って見てきました。ポイントは、RSAが「逆算（元に戻す）の難しさ」に安全性を預けていることです。
RSAが危うくなる道筋を、あえて“手順”として言い直すと次のようになります。
- ある数$a$を用意して$a^x\bmod n$を繰り返し、同じ値の並びが繰り返される周期 $𝑟$を見つける（周期探索）
- みつけた $r$ を手がかりに 最大公約数（gcd）を計算して、$n$の因数（素因数）にたどり着く（因数分解）
問題は、量子コンピュータがこの手順のうち (1) の「周期 $𝑟$を見つける」を得意としていることです。従来の計算機ではここが現実的な時間で終わらない前提だったのに対し、量子コンピュータの世界では、”この「周期探索」を破壊的に速く進められる可能性があること”が“ヤバさ”の核心でした。
鍵交換にはDH（Diffie–Hellman）、ECDH系の方式もあります。計算の仕方自体はRSAとは違いますが、こちらも本質は同じで、結局は 「ある値から元の指数を逆算するのが難しい」という前提に依存しています。量子コンピュータは、この手の「逆算の難しさ」を土台にした暗号と相性が悪い（量子コンピュータだと速く解けてしまう）、という点が共通しています。
PQCは、量子コンピュータが得意な“周期探索・離散対数・素因数分解”に安全性を依存しない方式へ置き換えていこう、という方向性です。
本記事はPQCそのものの解説はしませんが、PQCは「流行りの新暗号」というより、量子コンピュータが得意とする周期探索や“逆算”に安全性を預けないよう、前提となる計算問題そのものを差し替える取り組みだと捉えられます。
8. おわりに
この記事では、
- RSA 鍵交換を算数レベルまで分解し、
- $n = p \times q$ の因数分解において 「周期 $r$」がカギになること、
- その周期が分かると、オイラーの定理やユークリッドの互除法を通じて $p, q$ を取り出せること、
- そして、Shor のアルゴリズムが “周期 $r$ を効率よく見つける” アルゴリズムであること
を、Python と Amazon Braket を絡めながら見てきました。
現時点では、
- 実用的な RSA（2048 ビット級）を割るには、量子ビット数も誤り訂正も圧倒的に足りない
- とはいえ、研究の進み方次第では「思ったより早く“実用的な量子コンピュータ”が現れるかもしれない」
…という、ちょうど「コンピュータ黎明期」に似た空気感なのかもしれません。
（その当時の空気は知らないので、「かも」ですが）
本来、量子コンピュータはもっとその可能性を活かせる分野で輝くべきです。
（例えば、製薬とか医療とか）
しかし、その負の側面ともいえる現在の暗号方式が無力化される（可能性がある）というリスクから目を背けることもできません。
「とりあえず “強そうな暗号” をプルダウンから選ぶ」のではなく、何を守り、何のどこにどう破られる危険があるのか を、ざっくりでも理解しておくことは重要だと思っています。
そのための頭の整理として、この「なんちゃってRSA × 量子コンピュータ入門」が、少しでもお役に立てば幸いです。