ショアのアルゴリズムとは？新人エンジニア向けにRSA暗号との関係・周期発見・量子計算の仕組みをやさしく解説
山崎講師こんにちは。ゆうせいです。
今回は、「ショアのアルゴリズム」を新人エンジニア向けに解説します。
ショアのアルゴリズムとは、量子コンピュータを使って、巨大な整数の素因数分解や離散対数問題を高速に解くためのアルゴリズムです。
1994年にPeter Shor氏が発表した量子アルゴリズムで、整数の素因数分解や離散対数を量子コンピュータ上で効率的に解けることを示しました。Shor氏本人の公開論文一覧でも、この論文は「量子コンピュータで素因数分解と離散対数を高速にできることを示した元論文」と説明されています。
このアルゴリズムが有名な理由は、RSA暗号や楕円曲線暗号など、現在広く使われている公開鍵暗号の安全性に大きく関係するからです。
いきなり難しく聞こえますよね。
でも、最初に押さえるべきポイントはシンプルです。
「大きな数を、掛け算の元になった小さな素数へ分解する」
ショアのアルゴリズムは、この「大きな数を素数の掛け算に戻す問題」を、量子コンピュータなら非常に効率よく解ける可能性があることを示したアルゴリズムです。
まず素因数分解を復習しよう
素因数分解とは、ある整数を素数の掛け算に分解することです。
素数とは、1と自分自身以外では割り切れない整数です。
たとえば、15を素因数分解すると、次のようになります。
15 = 3 * 5
15は3と5を掛けた数です。
21なら、次のようになります。
21 = 3 * 7
21は3と7を掛けた数です。
小さい数なら簡単です。
でも、数がとても大きくなると、人間にもコンピュータにも難しくなります。
たとえるなら、卵を割ってオムレツを作るのは簡単ですが、完成したオムレツから元の卵を完全に取り出すのは難しいですよね。
掛け算は簡単でも、掛け算の結果から元の素数を探すのは難しい。
この性質が、RSA暗号の安全性を支えています。
RSA暗号と素因数分解の関係
RSA暗号は、大きな2つの素数を掛け合わせた数を利用する公開鍵暗号です。
公開鍵暗号とは、暗号化に使う鍵を公開し、復号に使う鍵を秘密にする暗号方式です。
ざっくり言うと、RSA暗号は次の性質を利用しています。
p * q = N
2つの素数pとqを掛けると、大きな数Nができます。
pとqを知っていれば、秘密の計算ができます。
しかし、Nだけを見てpとqを見つけるのは、数が巨大だと非常に難しいと考えられてきました。
| 操作 | 難しさ | たとえ |
|---|---|---|
| pとqを掛けてNを作る | 比較的簡単 | 材料を混ぜて料理を作る |
| Nからpとqを見つける | 非常に難しい | 料理から元の材料を完全に取り出す |
ショアのアルゴリズムは、この「Nからpとqを見つける」問題を量子コンピュータで効率よく解く道を示しました。
そのため、十分に大規模で誤り訂正された量子コンピュータが実現すると、現在の公開鍵暗号の一部は危険になります。
NISTは、耐量子計算機暗号、つまりPQCの標準化を進めており、2024年にはFIPS 203、204、205という3つの標準を承認しています。
ショアのアルゴリズムの核心は「周期を見つける」こと
ショアのアルゴリズムを理解するうえで一番大切なのは、「素因数分解をそのまま力技で解くのではない」という点です。
ショアのアルゴリズムは、素因数分解の問題を「周期を見つける問題」に変換します。
周期とは、同じパターンが繰り返される間隔のことです。
たとえば、信号機を考えてみましょう。
green -> yellow -> red -> green -> yellow -> red
青、黄、赤の並びが繰り返されています。
この繰り返しの長さが周期です。
数学でも、ある計算結果が一定の間隔で繰り返されることがあります。
ショアのアルゴリズムでは、次のような関数の周期を探します。
f(x) = a^x mod N
aをx乗し、その結果をNで割った余りを求める関数です。
modとは、割り算の余りを求める演算です。
たとえば、17を5で割ると、商は3、余りは2です。
17 mod 5 = 2
17を5で割った余りは2です。
周期を見つけると、なぜ素因数分解できるのか
ここが最初の山場です。
ショアのアルゴリズムでは、Nを素因数分解したいとします。
まず、Nと互いに素な数aを選びます。
互いに素とは、2つの数が1以外の共通の約数を持たないことです。
次に、次の関数を考えます。
f(x) = a^x mod N
aを何回も掛けて、その結果をNで割った余りを見ていきます。
この関数は、あるところで同じ値に戻ることがあります。
つまり、周期rがあります。
a^r mod N = 1
aをr乗してNで割った余りが1になるようなrを探すという意味です。
このrが偶数で、さらに次の条件を満たすと、Nの因数を見つけられる場合があります。
a^(r / 2) mod N != -1
aのr/2乗をNで割った余りが、-1と同じ扱いにならないことが必要です。
条件がそろうと、次の最大公約数を計算します。
gcd(a^(r / 2) - 1, N)
aのr/2乗から1を引いた数とNの最大公約数を求めます。
gcd(a^(r / 2) + 1, N)
aのr/2乗に1を足した数とNの最大公約数を求めます。
gcdとは、最大公約数のことです。
最大公約数とは、2つの整数を共通して割り切れる一番大きな整数です。
この計算によって、Nの因数が出てくることがあります。
まるで、鍵の直接解錠が難しいので、鍵穴のリズムを調べて別の入口から開けるようなものです。
小さな例で見てみよう：15を分解する
ここでは、N = 15を例にします。
本当の答えは次の通りです。
15 = 3 * 5
15は3と5に分解できます。
ショアのアルゴリズムの流れを簡単に体験するため、a = 2を選びます。
N = 15
分解したい数は15です。
a = 2
周期を調べるために2を選びます。
次の関数を考えます。
f(x) = 2^x mod 15
2をx乗して15で割った余りを調べます。
順番に計算してみましょう。
| x | 2^x | 2^x mod 15 |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 2 | 2 |
| 2 | 4 | 4 |
| 3 | 8 | 8 |
| 4 | 16 | 1 |
| 5 | 32 | 2 |
| 6 | 64 | 4 |
余りの並びを見ると、次のように繰り返されています。
1, 2, 4, 8, 1, 2, 4, 8
1、2、4、8の4つの値が繰り返されています。
したがって、周期rは4です。
r = 4
繰り返しの長さは4です。
rは偶数なので、次に進めます。
r / 2 = 2
周期4の半分は2です。
aのr/2乗を計算します。
a^(r / 2) = 2^2 = 4
、2の2乗は4です。
ここから、最大公約数を計算します。
gcd(4 - 1, 15) = gcd(3, 15) = 3
4から1を引いた3と15の最大公約数は3です。
gcd(4 + 1, 15) = gcd(5, 15) = 5
4に1を足した5と15の最大公約数は5です。
因数が出ました。
15 = 3 * 5
15を3と5に分解できました。
この例では小さすぎるので、人間でも簡単に解けます。
しかし、ショアのアルゴリズムの本質は、大きなNでも同じ考え方を使う点にあります。
古典コンピュータと量子コンピュータの役割分担
ショアのアルゴリズムは、すべてを量子コンピュータだけで行うわけではありません。
実は、古典コンピュータ、つまり普通のコンピュータでできる部分も多いです。
| 処理 | 担当 | 内容 |
|---|---|---|
| aを選ぶ | 古典コンピュータ | Nと互いに素な数を選ぶ |
| 最大公約数を計算する | 古典コンピュータ | gcdで因数を取り出す |
| 周期を見つける | 量子コンピュータ | 重ね合わせと量子フーリエ変換を使う |
| 結果を検証する | 古典コンピュータ | 因数が正しいか確認する |
一番難しい部分が、周期を見つける処理です。
量子コンピュータは、この周期発見を得意とします。
ショアのアルゴリズムは、量子コンピュータを「素因数分解マシン」として直接使うというより、「周期を高速に見つける装置」として使っているのです。
量子コンピュータは何が違うのか
普通のコンピュータは、ビットを使います。
ビットは0か1のどちらかです。
bit = 0 or 1
普通のビットは0または1のどちらかの状態を持ちます。
量子コンピュータは、量子ビットを使います。
量子ビットは、0と1の重ね合わせ状態を扱えます。
qubit = alpha * |0> + beta * |1>
量子ビットは0の状態と1の状態を、係数alphaとbetaを使って重ね合わせた状態として表せます。
重ね合わせとは、0か1のどちらかに決まる前の状態を、波のように同時に持つ考え方です。
高校生向けにたとえるなら、コインを投げて空中で回っている状態です。
机に落ちれば表か裏に決まります。
でも、空中で回っている間は、表と裏の可能性が同時にあるように見えます。
量子ビットは、このような重ね合わせを計算に利用します。
ただし、量子コンピュータは「すべての答えを一気に読める魔法の箱」ではありません。
測定すると、1つの結果しか出てきません。
だからこそ、必要な答えが出やすくなるように、量子状態の波をうまく干渉させる必要があります。
量子フーリエ変換とは何か
ショアのアルゴリズムで重要なのが、量子フーリエ変換です。
量子フーリエ変換は、英語でQuantum Fourier Transform、略してQFTと呼ばれます。
フーリエ変換とは、複雑な波を、どんな周期の波が含まれているかに分解する方法です。
音楽でたとえると分かりやすいです。
ピアノの和音を聞いたとき、人間には「ジャーン」と1つの音に聞こえるかもしれません。
でも、実際にはド、ミ、ソなど複数の音が混ざっています。
フーリエ変換は、その混ざった音から、どんな高さの音が含まれているかを調べる道具です。
ショアのアルゴリズムでは、周期を持つ関数から、その周期の情報を取り出すために量子フーリエ変換を使います。
periodic_pattern -> QFT -> period_information
周期的なパターンに量子フーリエ変換を使うことで、周期に関する情報を取り出します。
ショアの元論文でも、量子コンピュータ上で素因数分解や離散対数を効率的に扱うアルゴリズムが示されており、周期発見が中核になります。
ショアのアルゴリズムの全体像
ショアのアルゴリズムの流れを、少し整理しましょう。
| ステップ | 内容 | 担当 |
|---|---|---|
| 1 | 分解したい整数Nを用意する | 古典 |
| 2 | Nより小さい整数aを選ぶ | 古典 |
| 3 | gcd(a, N)を計算する | 古典 |
| 4 | gcd(a, N)が1でなければ因数が見つかる | 古典 |
| 5 | f(x) = a^x mod Nの周期rを探す | 量子 |
| 6 | rが条件を満たすか確認する | 古典 |
| 7 | gcd(a^(r / 2) - 1, N)を計算する | 古典 |
| 8 | gcd(a^(r / 2) + 1, N)を計算する | 古典 |
| 9 | Nの因数を得る | 古典 |
この流れを見ると、量子コンピュータが担当するのは主に周期発見です。
つまり、ショアのアルゴリズムは、量子計算と古典計算を組み合わせたハイブリッドなアルゴリズムと考えると理解しやすいです。
なぜ普通のコンピュータでは難しいのか
普通のコンピュータでも、周期を探すことはできます。
ただし、大きなNになると、調べる候補が膨大になります。
力技で調べると、時間がかかりすぎます。
これは、巨大な迷路で出口を1本道ずつ試すようなものです。
小さい迷路ならなんとかなります。
でも、迷路が都市全体くらい大きくなったら大変ですよね。
量子コンピュータは、重ね合わせと干渉を使って、周期に関する情報を効率よく取り出します。
ただし、繰り返しますが、量子コンピュータは候補を全部同時に試して全部の答えを読めるわけではありません。
波の干渉を使って、欲しい答えの確率を高めるのです。
ショアのアルゴリズムが暗号に与える影響
ショアのアルゴリズムが注目される最大の理由は、暗号への影響です。
RSA暗号は素因数分解の難しさに関係します。
Diffie-Hellman鍵共有や楕円曲線暗号は、離散対数問題の難しさに関係します。
ショアのアルゴリズムは、素因数分解だけでなく離散対数問題にも関係します。
そのため、十分に強力な量子コンピュータが実現した場合、現在使われている公開鍵暗号の一部は安全ではなくなる可能性があります。
| 暗号技術 | 安全性の土台 | ショアのアルゴリズムとの関係 |
|---|---|---|
| RSA | 素因数分解の難しさ | 影響を受ける |
| Diffie-Hellman | 離散対数問題の難しさ | 影響を受ける |
| 楕円曲線暗号 | 楕円曲線上の離散対数問題 | 影響を受ける |
| AESなどの共通鍵暗号 | 鍵探索の難しさ | 主にグローバーのアルゴリズムの文脈で考える |
ただし、今日のパソコンや普通のサーバーでショアのアルゴリズムを使ってRSAを破れるわけではありません。
ショアのアルゴリズムは、量子コンピュータ上で動くアルゴリズムです。
さらに、実用的な暗号を破るには、大規模で誤りに強い量子コンピュータが必要です。
耐量子計算機暗号とは何か
ショアのアルゴリズムによる将来のリスクに備えて研究・標準化が進められているのが、耐量子計算機暗号です。
英語ではPost-Quantum Cryptography、略してPQCと呼ばれます。
耐量子計算機暗号とは、量子コンピュータが発展しても破られにくいと考えられる数学問題を土台にした暗号技術です。
NISTは、PQCの標準としてML-KEM、ML-DSA、SLH-DSAなどを示しており、これらは今後の多くの導入の基礎になると説明しています。
新人エンジニアにとって大切なのは、「量子コンピュータが来たら全部の暗号が終わり」と雑に理解しないことです。
正しくは、影響を受けやすい暗号方式があり、そのために新しい暗号方式への移行準備が進んでいる、という理解です。
ショアのアルゴリズムのメリット
アルゴリズムとして見た場合、ショアのアルゴリズムには大きなメリットがあります。
| メリット | 説明 |
|---|---|
| 素因数分解を効率的に扱える | 量子コンピュータ上で、大きな整数の因数分解を高速化できる可能性を示した |
| 量子計算の価値を示した | 量子コンピュータが単なる理論ではなく、特定問題で強力になり得ることを示した |
| 暗号移行の重要性を明確にした | 公開鍵暗号の将来リスクを具体的に考えるきっかけになった |
| 周期発見という考え方を広めた | 量子フーリエ変換を使った周期発見の重要性を示した |
ショアのアルゴリズムは、量子コンピュータ研究における代表的な「キラーアプリ」の1つとして扱われます。
つまり、「量子コンピュータが実現すると、こんなに大きな違いが出るかもしれない」と世界に示したアルゴリズムです。
ショアのアルゴリズムの注意点
一方で、注意点もあります。
| 注意点 | 説明 |
|---|---|
| 量子コンピュータが必要 | 普通のコンピュータでそのまま高速に動くわけではない |
| 大規模な誤り訂正が必要 | 実用的な暗号を破るには、安定した大規模量子計算が必要になる |
| 1回で必ず成功するわけではない | aの選び方や周期rの条件によってはやり直しが必要になる |
| 暗号全部を壊すわけではない | 主に素因数分解や離散対数に依存する公開鍵暗号が問題になる |
| 理解には数学の土台が必要 | mod、最大公約数、周期、フーリエ変換などの知識が必要になる |
新人エンジニアは、ショアのアルゴリズムを「量子コンピュータで暗号を壊すやつ」とだけ覚えないでください。
それでは理解が浅いです。
本質は、「素因数分解を周期発見に変換し、量子フーリエ変換で周期を見つける」点にあります。
新人エンジニアが押さえるべき用語
| 用語 | 意味 | たとえ |
|---|---|---|
| 素因数分解 | 整数を素数の掛け算に分けること | 完成品を部品に分解する |
| RSA暗号 | 素因数分解の難しさを利用する公開鍵暗号 | 掛け算は簡単、逆向きは難しい鍵 |
| mod | 割り算の余りを求める演算 | 曜日の繰り返し |
| 周期 | 同じパターンが繰り返される間隔 | 信号機や曜日のサイクル |
| 量子ビット | 量子コンピュータで使う情報単位 | 空中で回るコインのような状態 |
| 重ね合わせ | 複数の状態が同時に存在するように扱う量子的性質 | 測る前の可能性の重なり |
| 量子フーリエ変換 | 量子状態から周期情報を取り出す変換 | 和音から音の成分を取り出す |
| PQC | 耐量子計算機暗号 | 量子時代に備える新しい鍵 |
ショアのアルゴリズムを学ぶ順番
ショアのアルゴリズムは、いきなり論文から読むとかなり難しいです。
新人エンジニアは、次の順番で学ぶと理解しやすくなります。
| 順番 | 学ぶ内容 | 理由 |
|---|---|---|
| 1 | 素数と素因数分解 | RSA暗号との関係を理解する土台になる |
| 2 | 最大公約数とユークリッドの互除法 | 因数を取り出す計算で必要になる |
| 3 | mod演算 | a^x mod Nの意味を理解するため |
| 4 | 周期 | ショアのアルゴリズムの核心だから |
| 5 | RSA暗号の概要 | なぜ重要なのかが分かる |
| 6 | 量子ビットと重ね合わせ | 量子計算の入口になる |
| 7 | 量子フーリエ変換 | 周期発見の仕組みに近づける |
| 8 | ショアのアルゴリズム全体 | 古典計算と量子計算の役割分担を理解する |
最初から量子フーリエ変換に突撃しないでください。
まずは、15を3と5に分ける小さな例で十分です。
小さな例を何度も追うと、全体像が見えてきます。
まとめ
ショアのアルゴリズムは、量子コンピュータを使って整数の素因数分解や離散対数問題を効率的に解くための重要なアルゴリズムです。
特にRSA暗号のように、素因数分解の難しさを安全性の土台にしている暗号方式に大きく関係します。
ただし、ショアのアルゴリズムは、普通のコンピュータで暗号を一瞬で破る魔法ではありません。
十分に大規模で安定した量子コンピュータが必要です。
ショアのアルゴリズムの流れを一言でまとめると、次の通りです。
factorization -> period_finding -> gcd
素因数分解の問題を周期発見の問題に変換し、周期から最大公約数を使って因数を取り出す流れです。
今回の最重要式を振り返りましょう。
f(x) = a^x mod N
aをx乗してNで割った余りを求める関数です。
a^r mod N = 1
r回進むと余りが1に戻るような周期rを探します。
gcd(a^(r / 2) - 1, N)
aのr/2乗から1を引いた数とNの最大公約数を求めます。
gcd(a^(r / 2) + 1, N)
aのr/2乗に1を足した数とNの最大公約数を求めます。
| ポイント | 内容 |
|---|---|
| 何をするアルゴリズムか | 量子コンピュータで素因数分解や離散対数問題を効率的に解く |
| なぜ重要か | RSA暗号などの公開鍵暗号に影響する |
| 核心は何か | 素因数分解を周期発見に変換すること |
| 量子計算の役割 | 量子フーリエ変換で周期情報を取り出すこと |
| 新人がまず学ぶべきこと | mod、gcd、周期、RSA、量子ビットの基礎 |
ショアのアルゴリズムを理解すると、量子コンピュータがなぜ注目されるのか、暗号技術がなぜ変わろうとしているのかが見えてきます。
今後の学習では、まず素因数分解、最大公約数、mod演算、RSA暗号の基礎を押さえましょう。その後、量子ビット、重ね合わせ、干渉、量子フーリエ変換へ進むと、ショアのアルゴリズムが「暗号を破る魔法」ではなく、「周期を見つける数学と量子計算の組み合わせ」だと理解できるようになります！
投稿者プロフィール
- 代表取締役
-
セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
海外放浪の末、2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。
学生時代は趣味と実益を兼ねてリゾートバイトにいそしむ。長野県白馬村に始まり、志賀高原でのスキーインストラクター、沖縄石垣島、北海道トマム。高じてオーストラリアのゴールドコーストでツアーガイドなど。現在は野菜作りにはまっている。
