Paper 2008/149
Toy Factoring by Newton's Method
Daniel R. L. Brown
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.
Note: Cited previous work of Bentahar
Metadata
- Available format(s)
- PS
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- factoring
- Contact author(s)
- dbrown @ certicom com
- History
- 2008-06-26: revised
- 2008-04-08: received
- See all versions
- Short URL
- https://ia.cr/2008/149
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/149,
author = {Daniel R. L. Brown},
title = {Toy Factoring by Newton's Method},
howpublished = {Cryptology ePrint Archive, Paper 2008/149},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/149}},
url = {https://eprint.iacr.org/2008/149}
}
