スマートフォン用の表示で見る

素因数分解

サイエンス

素因数分解

そいんすうぶんかい

整数Nを素数の積としてあらわすこと。

アルゴリズムとしては以下のものが知られている。

  • ρ法
  • p-1法
  • p+1法
  • 楕円曲線
  • 連分数法
  • 線形ふるい法
  • 2次ふるい法
  • 数体ふるい法

公開鍵暗号の一部*1では二つの巨大な素数の積が鍵として用いられる。これをもとの素数に分解すれば暗号を破れるが、莫大な計算を必要とするので事実上不可能であることがセキュリティのかなめとなっている。また、量子コンピュータが実現すれば、Shorのアルゴリズムにより確率的多項式時間で解けることが分かっている。

*1:具体的にはRSA暗号Rabin暗号、Goldwasser-Micali暗号