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

今のインターネットのセキュリティの多くはRSA暗号に支えられているんだけど、RSAは「大きな数の素因数分解は事実上不可能」という前提に立っている。ショアのアルゴリズムは量子コンピュータでこれを高速に解いてしまうから、暗号の前提が崩れるんだ

例えば2048ビットのRSA鍵を古典コンピュータで素因数分解しようとすると、宇宙の年齢よりも長い時間がかかる。でもショアのアルゴリズムを使える量子コンピュータなら、数時間で解けてしまう可能性があるんだ。指数時間が多項式時間になるという劇的な高速化だよ

今すぐではないよ。ショアのアルゴリズムで実用的なRSAを破るには数百万の物理量子ビットが必要で、2026年現在の量子コンピュータはまだ1000量子ビット台。でも「収穫して後で復号」攻撃といって、今のうちに暗号化された通信を保存しておいて将来解読する脅威があるんだ

ポスト量子暗号への移行が進んでいるよ。NISTが2024年に格子暗号ベースの新標準を策定して、GoogleやAppleもすでに実装を始めている。ショアのアルゴリズムでも解けない数学的問題に基づく暗号方式なんだ

ざっくり言うと、量子フーリエ変換を使って数の周期を見つけるんだ。素因数分解は周期発見問題に変換できて、量子コンピュータは重ね合わせを使って多数の周期候補を一度に検証できる。古典では1つずつ試すしかないところを、量子の並列性で一気にやるのがポイントだよ