講演名	1995/7/21 連分数表現を用いる素因数分解アルゴリズム 小林 邦勝, 田中 敦,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)	√の小数点以下の値を連分数展開して考慮した関数h_i(X)=(s_i+t_i⌊√⌋)^2-t^2_inxを用いて、√よりも小さな関数値を効率的に集めることにより、少ない計算量で2次合同式k^2≡m^2mod.αn(α:正整数)の関係を求め、高速にnの素因数を求める素因数分解アルゴリズムを提案する。連分数の係数l_と関数h_i(X)の間には、l_≫1のとき|h_i(x)|=⌊2/l_⌋の関係が成り立つ。従来の素因数分解アルゴリズムは変数xを変化させる1次元的な探索アルゴリズムであるのに対して、本方法は変数xに加えてもう一つの変数iをもつ小さな関数値h_i(X)を探す2次元的な探索アルゴリズムである。
抄録(英)	We propose a factoring algorithm using the continued fraction expression. In this algorithm we use a function h_i(X)=(s_i+t_i⌊√⌋)^2-t^2_inx which Contains a value under a decimal point of √, where s_i/t_i ≈ √-⌊√⌋. In the case of l_≫1, the function h_i(X) is related to a coefficient l_ of the continued fraction by the following equation |h_i(x)|=⌊2√/l_⌋The conventional factoring algorithms are one-dimensional searching algorithms, but this method is a two-dimensional searching algorithm which has two variables x and i.
キーワード(和)	素因数分解アルゴリズム / 連分数 / 2次元の探索アルゴリズム
キーワード(英)	factoring algorithm / continued fraction / two-dimensional searching algorithm
資料番号
発行日

研究会情報
研究会	ISEC
開催期間	1995/7/21(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Information Security (ISEC)
本文の言語	JPN
タイトル（和）	連分数表現を用いる素因数分解アルゴリズム
サブタイトル（和）
タイトル（英）	A Factoring Algorithm Using the Continued Fraction Expression
サブタイトル（和）
キーワード(1)（和/英）	素因数分解アルゴリズム / factoring algorithm
キーワード(2)（和/英）	連分数 / continued fraction
キーワード(3)（和/英）	2次元の探索アルゴリズム / two-dimensional searching algorithm
第 1 著者 氏名（和/英）	小林 邦勝 / Kunikatsu Kobayashi
第 1 著者 所属（和/英）	山形大学工学部電子情報工学科 Department of Electrical and Information Engineering, Faculty of Engineering, Yamagata University
第 2 著者 氏名（和/英）	田中 敦 / Atsushi Tanaka
第 2 著者 所属（和/英）	山形大学工学部電子情報工学科 Department of Electrical and Information Engineering, Faculty of Engineering, Yamagata University
発表年月日	1995/7/21
資料番号
巻番号（vol）	vol.95
号番号（no）	172
ページ範囲	pp.-
ページ数	9
発行日