連分数表現を用いる素因数分解アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
√<nx>の小数点以下の値を連分数展開して考慮した関数h_i(X)=(s_i+t_i⌊√<nx>⌋)^2-t^2_inxを用いて、√<n>よりも小さな関数値を効率的に集めることにより、少ない計算量で2次合同式k^2≡m^2mod.αn(α:正整数)の関係を求め、高速にnの素因数を求める素因数分解アルゴリズムを提案する。連分数の係数l_<i+1>と関数h_i(X)の間には、l_<i+1>≫1のとき|h_i(x)|=⌊2<nx>/l_<i+1>⌋の関係が成り立つ。従来の素因数分解アルゴリズムは変数xを変化させる1次元的な探索アルゴリズムであるのに対して、本方法は変数xに加えてもう一つの変数iをもつ小さな関数値h_i(X)を探す2次元的な探索アルゴリズムである。
社団法人電子情報通信学会の論文
1995-07-21

著者

関連論文

もっと見る

スポンサーリンク