第43話 Shorが示した量子計算因数分解アルゴリズム

これまでの話
第1話 量子の夜明け
...
第41話 量子計算とRSA暗号と素因数分解
第42話 Shor（ショア）のアルゴリズム

を因数分解する。ｘ< nで次式を満たすnと互いに素なxと周期rを探す。

から周期rを算出

ここで用意する量子ビット数Nは

として以下のフローで周期rを求める。

ショアのアルゴリズムの妙技は次のStep5,Step6です。

今日はこんなとこで、次回は、この量子計算因数分解アルゴリズムを各ステップ毎に具体例を交えて見てみる事にします。