書誌事項
- タイトル別名
-
- A Factoring Algorithm Using the Continued Fraction Expression
この論文をさがす
説明
√<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次元的な探索アルゴリズムである。
収録刊行物
-
- 電子情報通信学会技術研究報告. ISEC, 情報セキュリティ
-
電子情報通信学会技術研究報告. ISEC, 情報セキュリティ 95 (172), 19-27, 1995-07-21
一般社団法人電子情報通信学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1571135652340625280
-
- NII論文ID
- 110003297013
-
- NII書誌ID
- AN10060811
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles
