, PRIMES is in P, Annals of Mathematics, vol.160, issue.2, pp.781-793, 2004.
DOI : 10.4007/annals.2004.160.781
, Factor Refinement, Journal of Algorithms, vol.15, issue.2, pp.199-222, 1993.
DOI : 10.1006/jagm.1993.1038
, Sums of Divisors, Perfect Numbers and Factoring, SIAM Journal on Computing, vol.15, issue.4, pp.1143-1154, 1986.
DOI : 10.1137/0215083
, Factoring into coprimes in essentially linear time, Journal of Algorithms, vol.54, issue.1, pp.1-30, 2005.
DOI : 10.1016/j.jalgor.2004.04.009
, Detecting perfect powers by factoring into coprimes, Mathematics of Computation, vol.76, issue.257, pp.385-388, 2007.
DOI : 10.1090/S0025-5718-06-01837-0
URL : http://cr.yp.to/lineartime/powers2-20040630.pdf
, Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences, Public-Key Cryptography -PKC 2014 -17th International Conference on Practice and Theory in Public-Key Cryptography. Proceedings, pp.185-202, 2014.
DOI : 10.1007/978-3-642-54631-0_11
URL : https://hal.archives-ouvertes.fr/hal-00926902
, A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers, Advances in Cryptology -EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques Proceedings, pp.251-267, 2005.
DOI : 10.1007/11426639_15
, Factoring N = p r q for Large r, Advances in Cryptology -CRYPTO '99, 19th Annual International Cryptology Conference Proceedings, volume 1666 of Lecture Notes in Computer Science, pp.326-337, 1999.
DOI : 10.1007/3-540-48405-1_21
, Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier???Manin Operator, SIAM Journal on Computing, vol.36, issue.6, pp.1777-1806, 2007.
DOI : 10.1137/S0097539704443793
URL : https://hal.archives-ouvertes.fr/inria-00103401
, Applications of Fourier coefficients of modular forms. phd thesis Available at https://tspace.library.utoronto.ca/handle, p.70815, 1807.
, Finding a Small Root of a Univariate Modular Equation, International Conference on the Theory and Application of Cryptographic Techniques, pp.155-165, 1996.
DOI : 10.1007/3-540-68339-9_14
, Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities, Journal of Cryptology, vol.10, issue.4, pp.233-260, 1997.
DOI : 10.1007/s001459900030
, Divisors in residue classes, constructively, Mathematics of Computation, vol.77, issue.261, pp.531-545, 2008.
DOI : 10.1090/S0025-5718-07-02007-8
, Finding Small Solutions to Small Degree Polynomials, Cryptography and Lattices, International Conference, pp.20-31, 2001.
DOI : 10.1007/3-540-44670-2_3
, Finding Small Roots of Bivariate Integer Polynomial Equations Revisited, Advances in Cryptology -EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques Proceedings, pp.492-505, 2004.
DOI : 10.1007/978-3-540-24676-3_29
, Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach, 27th Annual International Cryptology Conference Proceedings, pp.379-394, 2007.
DOI : 10.1007/978-3-540-74143-5_21
, Factoring N = p r q s for large r and s, Topics in Cryptology -CT-RSA 2016 -The Cryptographers' Track at the RSA Conference 2016 Proceedings, volume 9610 of Lecture Notes in Computer Science, pp.448-464, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01250302
, Faster deterministic integer factorization, Mathematics of Computation, vol.83, issue.285, pp.339-345, 2014.
DOI : 10.1090/S0025-5718-2013-02707-X
URL : http://arxiv.org/pdf/1201.2116.pdf
, Prime numbers ? A Computational Perspective, 2005.
, Implicit Factoring with Shared Most Significant and Middle Bits, Public Key Cryptography -PKC 2010, 13th International Conference on Practice and Theory in Public Key Cryptography Proceedings, volume 6056 of Lecture Notes in Computer Science, pp.70-87, 2010.
DOI : 10.1007/978-3-642-13013-7_5
, Factoring Safe Semiprimes with a Single Quantum Query. working paper or preprint, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01229587
, An introduction to the theory of numbers, Bulletin of the American Mathematical Society, vol.35, issue.6, 1985.
DOI : 10.1090/S0002-9904-1929-04793-1
, Approximate Integer Common Divisors, Cryptography and Lattices, International Conference, pp.51-66, 2001.
DOI : 10.1007/3-540-44670-2_6
URL : http://cr.yp.to/bib/2001/howgrave-graham.pdf
, Finding small roots of univariate modular equations revisited, Cryptography and Coding, 6th IMA International Conference Proceedings, pp.131-142, 1997.
DOI : 10.1007/BFb0024458
, On finding small solutions of modular multivariate polynomial equations, Advances in Cryptology -EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques Proceeding, volume 1403 of Lecture Notes in Computer Science, pp.158-170, 1998.
, The Art of Computer Programming: Seminumerical Algorithms, 1997.
, Some remarks on computing the square parts of integers, Information and Computation, vol.78, issue.3, pp.246-253, 1988.
DOI : 10.1016/0890-5401(88)90028-4
, Factoring large integers, Mathematics of Computation, vol.28, issue.126, pp.637-646, 1974.
DOI : 10.1090/S0025-5718-1974-0340163-2
URL : http://www.ams.org/mcom/1974-28-126/S0025-5718-1974-0340163-2/S0025-5718-1974-0340163-2.pdf
, Divisors in residue classes, Mathematics of Computation, vol.42, issue.165, pp.331-340, 1984.
DOI : 10.1090/S0025-5718-1984-0726007-1
, Random equivalence of factorization and computation of orders, 1981.
, On the average number of divisors of the Euler function, Publ. Math. Debrecen, vol.70, issue.12, pp.125-148, 2007.
, Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint, 12th International Conference on Practice and Theory in Public Key Cryptography Proceedings, pp.1-14, 2009.
DOI : 10.1007/BFb0052241
, Using LLL-Reduction for Solving RSA and Factorization Problems, The LLL Algorithm, Information Security and Cryptography, pp.315-348, 2010.
DOI : 10.1007/978-3-642-02295-1_10
, Riemann's hypothesis and tests for primality, Proc. 7th STOC, pp.234-239, 1975.
, Implementing the asymptotically fast version of the elliptic curve primality proving algorithm, Mathematics of Computation, vol.76, issue.257, pp.493-505, 2007.
DOI : 10.1090/S0025-5718-06-01890-4
URL : https://hal.archives-ouvertes.fr/hal-00004136
, Digitalized signatures and public-key functions as intractable as factorization, Massachusetts Institute of Technology, 1979.
, On efficiently calculating small solutions of systems of polynomial equations: lattice-based methods and applications to cryptography, 2010.
, Efficient factoring based on partial information Advances in Cryptology -EUROCRYPT '85, Workshop on the Theory and Application of of Cryptographic Techniques, Proceedings, pp.31-34, 1985.
, Further results on implicit factoring in polynomial time, Advances in Mathematics of Communications, vol.3, issue.2, pp.205-217, 2009.
, Approximate Integer Common Divisor Problem Relates to Implicit Factorization, IEEE Transactions on Information Theory, vol.57, issue.6, pp.4002-4013, 2011.
DOI : 10.1109/TIT.2011.2137270
URL : http://eprint.iacr.org/2009/626.pdf
, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, vol.26, issue.5, pp.1484-1509, 1997.
DOI : 10.1137/S0097539795293172
, Modern Computer Algebra (3, 2013.
, Reductions among number theoretic problems Information and Computation Zralek. A deterministic version of Pollard's p-1 algorithm, Math. Comput, vol.72, issue.79269, pp.167-179513, 1987.
DOI : 10.1016/0890-5401(87)90030-7
URL : https://doi.org/10.1016/0890-5401(87)90030-7
, LIX -Laboratoire d'informatique de l' ´ Ecole polytechnique, GRACE -Inria Saclay -Ile de France E-mail address, F. Morain: morain@lix.polytechnique.fr E-mail address, Smith: smith@lix.polytechnique.fr (G. Renault) Agence Nationale de la Sécurité des Systèmes d'Information, POLSYS -INRIA Paris - UPMC -LIP6 E-mail address