Approximate Integer Common Divisor Problem relates to Implicit Factorization

Santanu Sarkar; Subhamoy Maitra

Paper 2009/626

Approximate Integer Common Divisor Problem relates to Implicit Factorization

Santanu Sarkar and Subhamoy Maitra

Abstract

In this paper, we analyse how to calculate the GCD of $k$ $(\geq 2)$ many large integers, given their approximations. Two versions of the approximate common divisor problem, presented by Howgrave-Graham in CaLC 2001, are special cases of our analysis when $k = 2$. We then relate the approximate common divisor problem to the implicit factorization problem. This has been introduced by May and Ritzenhofen in PKC 2009 and studied under the assumption that some of Least Significant Bits (LSBs) of certain primes are same. Our strategy can be applied to the implicit factorization problem in a general framework considering the equality of (i) Most Significant Bits (MSBs), (ii) Least Significant Bits (LSBs) and (iii) MSBs and LSBs together. We present new and improved theoretical as well as experimental results in comparison with the state of the art works in this area.

Note: New results and detailed comparisons with existing works added.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Greatest Common Divisor Factorization Integer Approximations Implicit Factorization Lattice LLL
Contact author(s): subho @ isical ac in
History: 2010-05-11: last of 2 revisions; 2009-12-26: received; See all versions
Short URL: https://ia.cr/2009/626
License: CC BY

BibTeX

@misc{cryptoeprint:2009/626,
      author = {Santanu Sarkar and Subhamoy Maitra},
      title = {Approximate Integer Common Divisor Problem relates to Implicit Factorization},
      howpublished = {Cryptology ePrint Archive, Paper 2009/626},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/626}},
      url = {https://eprint.iacr.org/2009/626}
}