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.
Version: 20100511:095043 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]