複数の放物線を用いる素因数分解アルゴリズム

概要

論文の詳細を見る
素因数分解に適した一群の多項式を系統的に発生させることができる関数を用いて、素因数分解の高速化をはかる。関数g(x)=(1+⌊√<nx>⌋)^2-nxは一つの区間(I^±_<j,k-1>,I^±_<j,k>)において関数値がおおよそ√<n>からn+√<n>の間を単調に変化する一つの放物線で表わされ、次の区間(I^±_<j,k>,I^±_<j,k+1>)においても同様な別の放物線となる。一方、√<nx>の小数点以下の値を連分数展開してi桁目まで考慮した関数h_i(x)=(s_i+t_i⌊√<nx>⌋)^2-t^2_inxは、関数g(x)が一つの放物線で表わされる一つの区間において、複数の区間をもつ周期的な放物線となり、添字iの大きさに比例して区間の数も多くなる。すなわち、g(x)が一つの放物線で表わされるある区間で考えると、Silvermanの複数多項式2次ふるい法と同じく、関数h_i(x)を用いることにより複数の放物線を生成することができる。次の区間においても同様な複数の放物線が得られることから、本方法はSilvermanの方法を2次元的に拡張したことに対応する方法であると解釈することもでき、素因数分解の高速化が期待される。
1995-09-20