Welcome to the resource topic for 2009/626
Title:
Approximate Integer Common Divisor Problem relates to Implicit Factorization
Authors: Santanu Sarkar, 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.
ePrint: https://eprint.iacr.org/2009/626
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .