計算コラム

(71) 素因数分解は難解

  • Back
2014/ 3/20
素数とは「1と自分自身以外に約数がない自然数」と定義されるが、中を覗くと不思議な世界が見える。2と3を除けば、素数は6m±1(mは整数)上に存在する。この手法で16桁の整数nから8桁の素数p,qを5,7,11,…と探し続けると、少なくとも10000000×2/6=3333333回以上の除算が必要となる。検証は1回の乗算p×q=nで済むが、それに比し素因数分解は計算量が桁数増に対し指数的に増え膨大となる。この計算難解の特徴はクレジットカードやインターネット、携帯電話などの公開鍵暗号方式に応用され、現代文明の根幹技術となっている。暗号解読を試みるコンピュータ性能との戦いには、暗号鍵の桁長の変更で凌いでいる。しかし、素因数分解の画期的な計算手法が発見されれば暗号は容易に解かれ、現代文明は危機に直面する。今後50年先、100年先まで暗号解読=素因数分解は安全だと誰が言えるであろうか。
関連リンク
[1]素因数分解