ショアのアルゴリズム

Shor's Algorithm

整数の素因数分解と離散対数の計算を、入力の大きさに対して多項式のステップ数で行う量子コンピュータ向けのアルゴリズムである。

詳細

概要

ショアのアルゴリズムは、整数の素因数分解と離散対数の計算という2つの問題に対する、量子コンピュータ上の効率的な乱択アルゴリズムである。

技術的な要点

この2つの問題は古典コンピュータでは難しいと一般に考えられており、複数の暗号方式の基礎として使われてきた。ショアのアルゴリズムは、因数分解する整数の桁数など入力の大きさに対して多項式のステップ数で解を求める。

産業での位置づけ

原論文は、素因数分解と離散対数が暗号方式の基礎に使われてきた問題であることを指摘している。スタートアップの説明文では、量子アルゴリズムや暗号の安全性の文脈で使われる。