Welcome to the resource topic for 2014/839
Title:
A Simple and Improved Algorithm for Integer Factorization with Implicit Hints
Authors: Koji Nuida, Naoto Itakura, Kaoru Kurosawa
Abstract:Given two integers N_1 = p_1q_1 and N_2 = p_2q_2 with \alpha-bit primes q_1,q_2, suppose that the t least significant bits of p_1 and p_2 are equal. May and Ritzenhofen (PKC 2009) developed a factoring algorithm for N_1,N_2 when t \geq 2\alpha + 3; Kurosawa and Ueda (IWSEC 2013) improved the bound to t \geq 2\alpha + 1. In this paper, we propose a polynomial-time algorithm in a parameter \kappa, with an improved bound t = 2\alpha - O(\log \kappa); it is the first non-constant improvement of the bound. Both the construction and the proof of our algorithm are very simple; the worst-case complexity of our algorithm is evaluated by an easy argument, without any heuristic assumptions. We also give some computer experimental results showing the efficiency of our algorithm for concrete parameters, and discuss potential applications of our result to security evaluations of existing factoring-based primitives.
ePrint: https://eprint.iacr.org/2014/839
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .