A simple and improved algorithm for integer factorization with implicit hints

Koji Nuida, Naoto Itakura, Kaoru Kurosawa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


Given two integers N1 = p1q1 and N2 = p2q2 with α-bit primes q1, q2, suppose that the t least significant bits of p1 and p2 are equal. May and Ritzenhofen (PKC 2009) developed a factoring algorithm for N1,N2 when t ≥ 2α+3; Kurosawa and Ueda (IWSEC 2013) improved the bound to t ≥ 2α + 1. In this paper, we propose a polynomial-time algorithm in a parameter κ, with an improved bound t = 2α−O(log κ); 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. 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.

Original languageEnglish
Title of host publicationTopics in Cryptology - CT-RSA 2015 - The Cryptographers’ Track at the RSA Conference 2015, Proceedings
EditorsKaisa Nyberg
PublisherSpringer Verlag
Number of pages12
ISBN (Electronic)9783319167145
Publication statusPublished - 2015
Externally publishedYes
EventRSA Conference Cryptographers’ Track, CT-RSA 2015 - San Francisco, United States
Duration: Apr 21 2015Apr 24 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceRSA Conference Cryptographers’ Track, CT-RSA 2015
Country/TerritoryUnited States
CitySan Francisco

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A simple and improved algorithm for integer factorization with implicit hints'. Together they form a unique fingerprint.

Cite this