Risa／Asir上の複数多項式2次ふるい（MPQS）の実装について

摘要

整数の素因数分解問題は数学的に難しい問題として知られており，暗号·通信などの分野に応用される一方で，世界各地の様々な団体がこの間題に挑戦している8最近の成果としては，2003年3月頃にF-Bahrら5名がRSA－160と呼ばれるm＝鞘型の10進160桁の合成数を分解することに成功しており，彼らの用いた手法はGNFS（一般数体ふるい法）と呼ばれるものである。 今回扱うMPQSはGNFSと同様「ふるい」によるアルゴリズムの一つとして知られており，矧こ10進100桁程度までの合成数に対してその効果を発揮するものである。