暗黙的なヒントを持つ整数因子分解の簡単な改良

HARASAWA Ryuichi; RYUTO Heiwa; SUEYOSHI Yutaka

文献

J-GLOBAL ID：201602219247800919 整理番号：16A1227042

暗黙的なヒントを持つ整数因子分解の簡単な改良

A Simple Improvement for Integer Factorizations with Implicit Hints

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=16A1227042&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=16A1227042&from=J-GLOBAL&jstjournalNo=U0466A") }}

著者 (3件)： , ,
資料名：
巻： E99.A 号： 6 ページ： 1090-1096(J-STAGE) 発行年： 2016年
JST資料番号： U0466A ISSN： 1745-1337 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

本論文では,暗黙的なヒントを持つkのRSAモジュラスN_i=p_iq_i(1≦i≦k)の整数因子分解の改良について述べた。すなわち,すべてのp_iがtの最下位ビットを共有した。Mayらは,kのRSAモジュラスのシステムから得られた次元kの格子における最短(または比較的短い)ベクトルを見つけるため,この問題を減少させた。これらのモジュラスに,ガウス減少またはLLLアルゴリズムを適用した。本論文では,kもRSAモジュラスから得られた格子の行列式を増やすことにより,それらの方法を改良した。改良後,Mayらの方法は,より高い確率で円滑に機能することを確認した。筆者らは,さらに,様々なパラメータに対するコンピュータ実験によって,本方法の効率を検証した。(翻訳著者抄録)

, , , , , , , ,
,

著者キーワード (1件)：

計算理論 , 数値計算

引用文献 (17件)：

[1] D. Coppersmith, “Finding a small root of a bivariate integer equation; Factoring with high bits known,” Advances in Cryptology, EUROCRYPT'96, Lecture Notes in Computer Science, vol.1070, pp.178-189, 1996.
[2] J.-C. Faugère, R. Marinier, and G. Renault, “Implicit factoring with shared most significant and middle bits,” Public Key Cryptography, PKC 2010, Lecture Notes in Computer Science, vol.6056, pp.70-87, 2010.
[3] B. Helfrich, “Algorithms to construct Minkowski reduced and hermite reduced lattice bases,” Theor. Comput. Sci., vol.41, pp.125-139, 1985.
[4] R. Kannan, “Minkowski's convex body theorem and integer programming,” Math. Oper. Res., vol.12, no.3, pp.415-440, 1987.
[5] K. Kurosawa and T. Ueda, “How to factor N₁ and N₂ when p₁=p₂ mod 2^t,” Advances in Information and Computer Security, IWSEC 2013, Lecture Notes in Computer Science, vol.8231, pp.217-225, 2013.

, ,

前のページに戻る