International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Toy Factoring by Newton's Method

Authors:
Daniel R. L. Brown
Download:
URL: http://eprint.iacr.org/2008/149
Search ePrint
Search Google
Abstract: A theoretical approach for integer factoring using complex analysis is to apply Newton's method on an analytic function whose zeros, within in a certain strip, correspond to factors of a given integer. A few successful toy experiments of factoring small numbers with this approach, implemented in a naive manner that amounts to complexified trial division, show that, at least for small numbers, Newton's method finds the requisite zeros, at least some of time (factors of nearby numbers were also sometimes found). Nevertheless, some heuristic arguments predict that this approach will be infeasible for factoring numbers of the size currently used in cryptography.
BibTeX
@misc{eprint-2008-17826,
  title={Toy Factoring by Newton's Method},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / factoring},
  url={http://eprint.iacr.org/2008/149},
  note={ dbrown@certicom.com 14056 received 3 Apr 2008, last revised 26 Jun 2008},
  author={Daniel R. L. Brown},
  year=2008
}