Paper 2009/626 Original: eprint.iacr.org/2009/626 ↗
Approximate Integer Common Divisor Problem relates to Implicit Factorization
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2010-05-11: last updated
- 2009-12-26: published
- Short URL
- https://ia.cr/2009/626
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2009/626}
}