1 Search Results for "Srivastava, Shubham Sahai"


Document
Integer Factoring Using Small Algebraic Dependencies

Authors: Manindra Agrawal, Nitin Saxena, and Shubham Sahai Srivastava

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.MFCS.2016.6,
  author =	{Agrawal, Manindra and Saxena, Nitin and Srivastava, Shubham Sahai},
  title =	{{Integer Factoring Using Small Algebraic Dependencies}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.6},
  URN =		{urn:nbn:de:0030-drops-64234},
  doi =		{10.4230/LIPIcs.MFCS.2016.6},
  annote =	{Keywords: integer, factorization, factoring integers, algebraic dependence, dependencies}
}
  • Refine by Author
  • 1 Agrawal, Manindra
  • 1 Saxena, Nitin
  • 1 Srivastava, Shubham Sahai

  • Refine by Classification

  • Refine by Keyword
  • 1 algebraic dependence
  • 1 dependencies
  • 1 factoring integers
  • 1 factorization
  • 1 integer

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

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