TY - GEN
T1 - A simple and improved algorithm for integer factorization with implicit hints
AU - Nuida, Koji
AU - Itakura, Naoto
AU - Kurosawa, Kaoru
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
KW - Gaussian reduction
KW - Integer factorization with implicit hint
UR - http://www.scopus.com/inward/record.url?scp=84930466967&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84930466967&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-16715-2_14
DO - 10.1007/978-3-319-16715-2_14
M3 - Conference contribution
AN - SCOPUS:84930466967
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 258
EP - 269
BT - Topics in Cryptology - CT-RSA 2015 - The Cryptographers’ Track at the RSA Conference 2015, Proceedings
A2 - Nyberg, Kaisa
PB - Springer Verlag
T2 - RSA Conference Cryptographers’ Track, CT-RSA 2015
Y2 - 21 April 2015 through 24 April 2015
ER -