Paper 2014/839
A Simple and Improved Algorithm for Integer Factorization with Implicit Hints
Koji Nuida, Naoto Itakura, and 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 polynomialtime algorithm in a parameter $\kappa$, with an improved bound $t = 2\alpha  O(\log \kappa)$; it is the first nonconstant improvement of the bound. Both the construction and the proof of our algorithm are very simple; the worstcase 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 factoringbased primitives.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 factoring
 Contact author(s)
 k nuida @ aist go jp
 History
 20141020: received
 Short URL
 https://ia.cr/2014/839
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/839, author = {Koji Nuida and Naoto Itakura and Kaoru Kurosawa}, title = {A Simple and Improved Algorithm for Integer Factorization with Implicit Hints}, howpublished = {Cryptology ePrint Archive, Paper 2014/839}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/839}}, url = {https://eprint.iacr.org/2014/839} }