【しょあのあるごりずむ】

ショアのアルゴリズムとは？

最終更新: 2026年10月3日

💡 大きな数の素因数を、量子計算で効率よく探す方法

量子コンピュータで整数の素因数分解や離散対数を、入力の桁数に対して多項式時間で解くアルゴリズム。ピーター・ショアが1994年に発表し、RSAなどの公開鍵暗号への脅威を示した。

📌 このページのポイント

15 = 3 × 5は仕組みの小さな例で、実機の性能や限界を示しません。対策欄はNISTの2024年の3標準です。

ひよこ

ショアのアルゴリズムって何がすごいの？

ペンギン先生

大きな数の素因数分解などを、量子コンピュータで効率よく解く方法なんだ。入力の桁数が増えても必要な計算手順が多項式の範囲で増えるので、RSAなどの暗号にとって大きな脅威になるよ

ひよこ

古典コンピュータでは1つずつ割るしかないの？

ペンギン先生

そんなことはないよ。数体ふるい法など、総当たりより効率のよい方法もあるんだ。ただし一般の大きな整数を多項式時間で素因数分解する古典アルゴリズムは、知られていないよ

ひよこ

量子コンピュータなら一瞬で暗号を破れるの？

ペンギン先生

多項式時間というのは計算手順の増え方で、一瞬という意味ではないよ。実用的な鍵を扱うには十分な規模と精度の量子計算が必要で、実際の時間は装置や誤り訂正などの条件に左右されるんだ

ひよこ

対策はあるの？

ペンギン先生

量子コンピュータによる攻撃にも耐えられるように設計されたポスト量子暗号があるよ。NISTは2024年に、鍵共有用のML-KEMと署名用のML-DSA・SLH-DSAの3つの標準を公開したんだ

ひよこ

仕組みはどうなってるの？

ペンギン先生

素因数分解を、数をべき乗して余りを取る計算の周期を探す問題へ結び付けるんだ。量子フーリエ変換を使って周期の情報を測定し、古典計算も組み合わせて素因数を求めるよ。すべての候補の答えを一度に読み出せるわけではないんだ

まとめ：ざっくりこれだけ覚えればOK！

「ショアのアルゴリズム」って出てきたら「量子計算で素因数分解などを効率よく解く方法」と思えばだいたいOK！

📖 おまけ：英語の意味

「Shor's Algorithm」＝ショアのアルゴリズム

💬 ピーター・ショアの名前に由来するよ。1994年の会議発表をもとに、素因数分解と離散対数の詳しい論文が書かれたんだ

参考資料