講演抄録/キーワード |
講演名 |
2010-05-21 17:10
数値解析的手法の素因数分解への適用 ○白勢政明(公立はこだて未来大) ISEC2010-9 |
抄録 |
(和) |
素因数分解の困難性は,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 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2010-9 |