Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Greatest Common Divisor, Factorization, Integer Approximations, Implicit Factorization, Lattice, LLL

Date: received 18 Dec 2009, last revised 11 May 2010

Contact author: subho at isical ac in

Available format(s): PDF | BibTeX Citation

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

Short URL: ia.cr/2009/626

[ Cryptology ePrint archive ]