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 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
factoring
Contact author(s)
k nuida @ aist go jp
History
2014-10-20: received
Short URL
https://ia.cr/2014/839
License
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2014/839}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.