素因数分解問題とは、与えられた自然数の自明でない約数を 求める問題である。この問題は数論の分野では古くから知ら れている問題であるが、効率的な解法、つまり入力値のサイ ズに関する多項式時間アルゴリズムは知られておらず、最良 のアルゴリズムでも準指数時間を必要とする。本講演では、 素因数分解にまつわる現状と、いくつかの分解アルゴリズム の紹介を行う予定である。
プログラムに戻る
．