みなさん、こんにちは！今回は、量子コンピューティングの重要なアルゴリズムである「ショアのアルゴリズム（Shor’s algorithm）」について解説します。
今回のブログは、量子コンピューティング企業であるblueqat（ブルーキャット）の代表・湊さんの解説記事をベースに、さらに分かりやすく噛み砕いてお届けします。元となる湊先生の素晴らしい記事は以下からご覧いただけます。
それでは、さっそく解説を始めましょう！
そもそも「ショアのアルゴリズム」とは？
一言でいうと、「数学的な特定のステップを踏むことで、どんなに大きな数でも効率よく素因数分解できてしまうアルゴリズム」です。
現在、インターネットの安全性を支えている「RSA暗号」などは、「巨大な素数同士を掛け算した数 N」を公開鍵として使っています。掛け算は一瞬でできますが、逆にその巨大な N から元の素数を見つけ出す（素因数分解する）のは、従来のコンピュータでは天文学的な時間がかかるため、「解読できない」という性質を利用しています。
しかし、量子コンピュータ（量子ゲート方式）の上でこの「ショアのアルゴリズム」を実行すると、その巨大な N の素因数分解も短時間で解けてしまうため、セキュリティの世界で非常に大きな話題（そして課題）となっています。
このブログシリーズでは、まずは概念からスタートし、最終的には高校生でもわかるように、実際に量子ゲートを使ってショアのアルゴリズムを実装するところまでを目指します！（湊さんの連載記事の展開に合わせて進めていく予定です）
まずは手計算で流れを掴もう！ N＝15 を素因数分解する
量子ゲートでの実装に入る前に、全体の流れを直感的に掴むため、まずは手計算でショアのアルゴリズムを体験してみましょう。
今回は、例として N ＝ 15 を素因数分解します。
もちろん「15 ＝ 3 × 5」なのは一瞬で分かりますが、あえて答えが分からない前提でアルゴリズムを進めていきます。
ステップ1：適当な数を選ぶ
まず、15 と互いに素（最大公約数が 1）になる数を、適当に1つ選びます。
※万が一、ここで選んだ数が偶然 15 の公約数（3や5）だった場合は、その時点で素因数分解が成功して終了となります。しかし、現実のRSA暗号で使われる N は桁数が膨大なため、偶然公約数を引き当てる確率は極めて低いです。
今回は、適当に選んだ数を x ＝ 7 とします。
ステップ2：公式に当てはめて「周期性」を見つける
ショアのアルゴリズムの肝となるのが、次の数式を満たす最小の正の整数 r（周期）を見つけることです。
- xのr乗 ≡ 1 (mod N)
これは、「xのr乗を N で割った余りが 1 になる」という意味です。この r が分かると、次のステップで素因数分解ができるようになります。「周期」と呼ばれるのは、これ以降も r を増やしていくと、特定のパターンが繰り返されるためです。
今回、x ＝ 7, N ＝ 15 ですので、「7のr乗」を 15 で割った余りが 1 になる r を、 r ＝ 1 から順番に探してみます。
- r ＝ 1 のとき： 7の1乗 ＝ 7 ⇒ 15 で割った余りは 7
- r ＝ 2 のとき： 7の2乗 ＝ 49 ⇒ 49 ÷ 15 ＝ 3 余り 4
- r ＝ 3 のとき： 7の3乗 ＝ 343 ⇒ 343 ÷ 15 ＝ 22 余り 13
- r ＝ 4 のとき： 7の4乗 ＝ 2401 ⇒ 2401 ÷ 15 ＝ 160 余り 1
余りが 1 になりました！ したがって、周期は r ＝ 4 だと分かります。
※「mod（合同式）」に馴染みがない方は、高校数学の数A（整数の性質）などで登場するので、ぜひ復習してみてください。
ステップ3：因数分解と最大公約数から答えを導く
周期 r ＝ 4 が見つかったので、これを使って 15 の公約数を求めていきます。
ステップ2の式を書き換えると、「xのr乗 － 1」は N の倍数になるため、整数 k を使って以下のように表せます。
- (xのr乗) － 1 ＝ k × N
ここで、左辺を因数分解の公式を使って変形します。
- ｛(xの r/2 乗) ＋ 1｝×｛(xの r/2 乗) － 1｝＝ k × N
ここに、今回の値（x ＝ 7, r ＝ 4, N ＝ 15）を代入してみましょう。r/2 は 4/2 ＝ 2 なので、「7の2乗」を計算します。
- (7の2乗 ＋ 1) × (7の2乗 － 1) ＝ (49 ＋ 1) × (49 － 1) ＝ 50 × 48
つまり、50 × 48 ＝ 15 × k となります。
この式が意味するのは、「50 と 48 のどちらか（または両方）に、15の約数（3や5）が含まれている」ということです。 そこで、それぞれの数と 15 との最大公約数（gcd）を計算してみます。
- gcd(50, 15) ＝ 5
- gcd(48, 15) ＝ 3
見事に 15 の約数である 5 と 3 が導き出されました！
これで、 15 ＝ 3 × 5 と素因数分解完了です。
※基本的にはこのように両方の因数が手に入りますが、極めて稀に片方しか手に入らない場合もあります。
なぜ量子コンピュータが必要なのか？
「手計算でできるなら、普通のコンピュータ（古典コンピュータ）でやればいいのでは？」と思うかもしれません。
実は、ステップ2の「周期 r を見つける作業」が大きな壁になります。
今回は 15 という2桁の小さな数だったため、4回計算するだけで r＝4 が見つかりました。しかし、現実のRSA暗号で使われている数は 10の300乗桁（約2048ビット）以上という圧倒的な巨大さです。
この規模になると、現在のスーパーコンピュータを総動員しても、周期を見つけるまでに約1億年かかると言われています。
しかし、量子コンピュータの「量子重ね合わせ」や「量子フーリエ変換」という特有の性質を使うと、この途方もない周期探しの計算を、一瞬で終わらせることができます。だからこそ、この部分を量子ゲートに任せようというわけです。
まとめと次回予告
今回は、ショアのアルゴリズムの仕組みを理解するために、まずは手計算での流れを解説しました。
- 適当な数を選ぶ
- 割った余りが1になる「周期 r」を見つける（←ここを量子コンピュータにやらせたい）
- 因数分解と最大公約数を使って、素因数を取り出す
この流れがショアのアルゴリズムの全体像です。
次回は、一番の難所である「周期探し」を、実際に量子ゲートを使ってどのように処理していくのか、その具体的な流れを解説していきます。お楽しみに！