電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2010-05-21 17:10
数値解析的手法の素因数分解への適用
白勢政明公立はこだて未来大
技報オンラインサービス実施中
抄録 (和) 素因数分解の困難性は,RSA暗号の安全性の根拠となっており,その困難性の分析は重要である.素因数分解の方法としては,$\rho$法,$p-1$法,楕円曲線法,2次篩法,数体篩法等がある.数体篩法は,計算コストが$O(\exp ((64/9)^{1/3}) (\ln n)^{1/3} (\ln \ln n)^{2/3})$の準指数時間アルゴリズムであり,現在の最速素因数分解アルゴリズムである.離散対数アルゴリズムのための篩法ように,数体篩法の計算コストの削減を達成できるかも知れないが,多項式時間アルゴリズムにすることはできなさそうである.本稿は,$n$の約数で零となる約数発見関数${\cal F}(n,x)$を構成し,それに数値解析的手法を適用することを考え,素因数分解の更なる高速化の可能性について考察する. 
(英) It is important to analyze the hardness of prime factorization
which the security of RSA cryptosystems is based on.
There are some methods for solving prime factorization such as
the $\rho$ method, the $p-1$ method, the elliptic curve method, the quadratic sieve,
and the number field method.
The number field sieve is the current fastest algorithm for solving
prime factorization, and is a semi-exponential time algorithm whose cost is $O(\exp ((64/9)^{1/3}) (\ln n)^{1/3} (\ln \ln n)^{2/3})$. As sieves for solving discrete logarithm problem have improved, the number field sieve may be improved, however, the author thinks it is impossible that the number field sieve becomes a polynomial time algorithm. This report considers the possibility of further speed-up of prime factorization by constructing a \lq\lq finding divisor function'' ${\cal F}(n,x)$ whose zeros are divisors of $n$ and by applying a numerical analysis technique to the function.
キーワード (和) 素因数分解 / RSA暗号 / 数値解析 / / / / /  
(英) prime factorization / RSA cryptosystem / numerical analysis / / / / /  
文献情報 信学技報, vol. 110, no. 44, ISEC2010-9, pp. 57-62, 2010年5月.
資料番号 ISEC2010-9 
発行日 2010-05-14 (ISEC) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 ISEC  
開催期間 2010-05-21 - 2010-05-21 
開催地(和) 機械振興会館 
開催地(英) Kikai-Shinko-Kaikan Bldg. 
テーマ(和) 一般 
テーマ(英)  
講演論文情報の詳細
申込み研究会 ISEC 
会議コード 2010-05-ISEC 
本文の言語 日本語 
タイトル(和) 数値解析的手法の素因数分解への適用 
サブタイトル(和)  
タイトル(英) Applying Numerical Analysis Technique To Prime Factorization 
サブタイトル(英)  
キーワード(1)(和/英) 素因数分解 / prime factorization  
キーワード(2)(和/英) RSA暗号 / RSA cryptosystem  
キーワード(3)(和/英) 数値解析 / numerical analysis  
キーワード(4)(和/英) /  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 白勢 政明 / Masaaki Shirase / シラセ マサアキ
第1著者 所属(和/英) 公立はこだて未来大学 (略称: 公立はこだて未来大)
Future University Hakodate (略称: FUN)
第2著者 氏名(和/英/ヨミ) / /
第2著者 所属(和/英) (略称: )
(略称: )
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2010-05-21 17:10:00 
発表時間 25 
申込先研究会 ISEC 
資料番号 IEICE-ISEC2010-9 
巻番号(vol) IEICE-110 
号番号(no) no.44 
ページ範囲 pp.57-62 
ページ数 IEICE-6 
発行日 IEICE-ISEC-2010-05-14 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会