Document Open Access Logo

Integer Factoring Using Small Algebraic Dependencies

Authors Manindra Agrawal, Nitin Saxena, Shubham Sahai Srivastava

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.6.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Manindra Agrawal
Nitin Saxena
Shubham Sahai Srivastava

Cite AsGet BibTex

Manindra Agrawal, Nitin Saxena, and Shubham Sahai Srivastava. Integer Factoring Using Small Algebraic Dependencies. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.6

Abstract

Integer factoring is a curious number theory problem with wide applications in complexity and cryptography. The best known algorithm to factor a number n takes time, roughly, exp(2*log^{1/3}(n)*log^{2/3}(log(n))) (number field sieve, 1989). One basic idea used is to find two squares, possibly in a number field, that are congruent modulo n. Several variants of this idea have been utilized to get other factoring algorithms in the last century. In this work we intend to explore new ideas towards integer factoring. In particular, we adapt the AKS primality test (2004) ideas for integer factoring. In the motivating case of semiprimes n=pq, i.e. p<q are primes, we exploit the difference in the two Frobenius morphisms (one over F_p and the other over F_q) to factor n in special cases. Specifically, our algorithm is polynomial time (on number theoretic conjectures) if we know a small algebraic dependence between p,q. We discuss families of n where our algorithm is significantly faster than the algorithms based on known techniques.
Keywords
  • integer
  • factorization
  • factoring integers
  • algebraic dependence
  • dependencies

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Annals of Math, 160(2):781-793, 2004. Google Scholar
  2. Shi Bai, Pierrick Gaudry, Alexander Kruppa, Emmanuel Thome, and Paul Zimmermann. Factorization of RSA-220 with CADO-NFS. 2016. Google Scholar
  3. Daniel Julius Bernstein. Introduction to post-quantum cryptography. In Post-quantum cryptography, pages 1-14. Springer, 2009. Google Scholar
  4. Dan Boneh et al. Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 46(2):203-213, 1999. Google Scholar
  5. Joe Peter Buhler, Hendrik Willem Lenstra Jr, and Carl Pomerance. Factoring integers with the number field sieve. In The development of the number field sieve, pages 50-94. Springer, 1993. Google Scholar
  6. Yingpu Deng and Yanbin Pan. An algorithm for factoring integers. Cryptology ePrint Archive, Report 2012/097, 2012. Google Scholar
  7. John D Dixon. Asymptotically fast factorization of integers. Mathematics of computation, 36(153):255-260, 1981. Google Scholar
  8. Carl Friedrich Gauss. Disquisitiones Arithmeticae. 1801. Article 329. Google Scholar
  9. Joseph Gerver. Factoring large numbers with a quadratic sieve. Mathematics of Computation, 41(163):287-294, 1983. Google Scholar
  10. Rajiv Gupta and Maruti Ram Murty. A remark on artin’s conjecture. Inventiones mathematicae, 78(1):127-130, 1984. Google Scholar
  11. F.R.S. Horsley, Rev. Samuel. The sieve of eratosthenes. being an account of his method of finding all the prime numbers. Philosophical Transactions (1683-1775), 62:327-347, 1772. Google Scholar
  12. Ravi Kannan. Algorithmic geometry of numbers. Annual review of computer science, 2(1):231-267, 1987. Google Scholar
  13. Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Klaas Lenstra, Emmanuel Thomé, Joppe W Bos, Pierrick Gaudry, Alexander Kruppa, Peter Lawrence Montgomery, Dag Arne Osvik, et al. Factorization of a 768-bit RSA modulus. In Advances in Cryptology-CRYPTO'10, pages 333-350. 2010. Google Scholar
  14. R Sherman Lehman. Factoring large integers. Mathematics of Computation, 28(126):637-646, 1974. Google Scholar
  15. Arjen Klaas Lenstra, Hendrik Willem Lenstra Jr., Mark Steven Manasse, and John M. Pollard. The number field sieve. In Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, pages 564-572, 1990. Google Scholar
  16. Arjen Klaas Lenstra, Hendrik Willem Lenstra, and Lászlo Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261:515-534, 1982. Google Scholar
  17. Hendrik Willem Lenstra Jr. Factoring integers with elliptic curves. Annals of mathematics, pages 649-673, 1987. Google Scholar
  18. James McKee. Turning euler’s factoring method into a factoring algorithm. Bulletin of the London Mathematical Society, 28(133):351-355, 1996. Google Scholar
  19. Pieter Moree. Artin’s primitive root conjecture—a survey. INTEGERS, 10(6):1305-1416, 2012. Google Scholar
  20. Oystein Ore. Number theory and its history. Courier Corporation, 2012. Google Scholar
  21. John M Pollard. Theorems on factorization and primality testing. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 76 of Cambridge Univ Press, pages 521-528, 1974. Google Scholar
  22. John M Pollard. A monte carlo method for factorization. BIT Numerical Mathematics, 15(3):331-334, 1975. Google Scholar
  23. Carl Pomerance. The quadratic sieve factoring algorithm. In Advances in cryptology, pages 169-182, 1985. Google Scholar
  24. Carl Pomerance. A tale of two sieves. Biscuits of Number Theory, 85, 2008. Google Scholar
  25. Arnold Schönhage. Factorization of univariate integer polynomials by diophantine approximation and improved basis reduction algorithm. ICALP, 172:436-447, 1984. Google Scholar
  26. Peter Williston Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484-1509, 1997. Google Scholar
  27. Lawrence Clinton Washington. Introduction to cyclotomic fields, volume 83. Springer, 2012. Google Scholar
  28. Hugh Cowie Williams. A p+1 method of factoring. Mathematics of Computation, 39(159):225-234, 1982. Google Scholar
  29. Hugh Cowie Williams and Jeffrey Outlaw Shallit. Factoring integers before computers. Mathematics of computation, 48:481-531, 1994. (1943-1993, Fifty Years of Computational Mathematics (W. Gautschi, ed.), Proc. Sympos. Appl. Math.). Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact