Geodesic
Approximate common divisor problem and lattice sieving
Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 2, pp. 87-98 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A heuristic algorithm for computing common divisors of two integers (one of which is known only approximately) is described. We reduce this computational problem to the solution of a system of integer linear inequalities. This system with two unknowns is solved by the method suggested by J. Franke and T. Kleinjung for lattice sieving. In some cases our algorithm is faster than other methods. 
@article{MVK_2018_9_2_a6,
     author = {K. D. Zhukov},
     title = {Approximate common divisor problem and lattice sieving},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {87--98},
     year = {2018},
     volume = {9},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2018_9_2_a6/}
}
TY  - JOUR
AU  - K. D. Zhukov
TI  - Approximate common divisor problem and lattice sieving
JO  - Matematičeskie voprosy kriptografii
PY  - 2018
SP  - 87
EP  - 98
VL  - 9
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2018_9_2_a6/
LA  - en
ID  - MVK_2018_9_2_a6
ER  - 
%0 Journal Article
%A K. D. Zhukov
%T Approximate common divisor problem and lattice sieving
%J Matematičeskie voprosy kriptografii
%D 2018
%P 87-98
%V 9
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2018_9_2_a6/
%G en
%F MVK_2018_9_2_a6
K. D. Zhukov. Approximate common divisor problem and lattice sieving. Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 2, pp. 87-98. http://geodesic.mathdoc.fr/item/MVK_2018_9_2_a6/

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

[2] Franke J., Kleinjung T., “Continued fractions and lattice sieving”, SHARCS 2005 http://www.hyperelliptic.org/tanja/SHARCS/talks/FrankeKleinjung.pdf

[3] May A., Ritzenhofen M., “Implicit factoring: on polynomial time factoring given only an implicit hint”, Lect. Notes Comput Sci., 5443, 2009, 1–14 | DOI | MR | Zbl

[4] Van Dijk M., Gentry C., Halevi S., Vaikuntanathan V., “Fully homomorphic encryption over the integers”, Lect. Notes Comput Sci., 6110, 2010, 24–43 | DOI | MR | Zbl

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

[6] Zhukov K. D., “Approximate common divisor problem and continued fractions”, Mathematical Aspects of Cryptography, 7:2 (2016), 61–70 | MR