Geodesic
Approximate common divisor problem and continued fractions
Matematičeskie voprosy kriptografii, Tome 7 (2016) no. 2, pp. 61-70 
K. D. Zhukov. Approximate common divisor problem and continued fractions. Matematičeskie voprosy kriptografii, Tome 7 (2016) no. 2, pp. 61-70. http://geodesic.mathdoc.fr/item/MVK_2016_7_2_a5/
@article{MVK_2016_7_2_a5,
     author = {K. D. Zhukov},
     title = {Approximate common divisor problem and continued fractions},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {61--70},
     year = {2016},
     volume = {7},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2016_7_2_a5/}
}
TY  - JOUR
AU  - K. D. Zhukov
TI  - Approximate common divisor problem and continued fractions
JO  - Matematičeskie voprosy kriptografii
PY  - 2016
SP  - 61
EP  - 70
VL  - 7
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2016_7_2_a5/
LA  - en
ID  - MVK_2016_7_2_a5
ER  - 
%0 Journal Article
%A K. D. Zhukov
%T Approximate common divisor problem and continued fractions
%J Matematičeskie voprosy kriptografii
%D 2016
%P 61-70
%V 7
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2016_7_2_a5/
%G en
%F MVK_2016_7_2_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

We describe two algorithms for computing common divisors of two integers, when one of these integers is known only approximately. We generalize a known method based on the continued fraction technique. In some cases new algorithms overcome the best known algorithm based on Coppersmith's method: not so accurate approximation is reqiured to compute a divisor.

[1] Buhshtab A. A., Number Theory, Prosvechenie, M., 1966 (in Russian) | MR

[2] Dujella A., “Continued fractions and RSA with small secret exponent”, Tatra Mt. Math. Publ., 29 (2004), 101–112 | MR | Zbl

[3] Howgrave-Graham N., “Approximate integer common divisors”, Cryptography and Lattices, CaLC 2001, Lect. Notes Comput. Sci., 2146, 2001, 51–66 | DOI | MR | Zbl

[4] Sarkar S., Maitra S., “Approximate integer common divisor problem relates to implicit factorization”, IEEE Trans. Inf. Theory, IT, 57:6 (2011), 4002–4013 | DOI | MR

[5] MPIR: Multiple Precision Integers and Rationals, http://www.mpir.org/