Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / factoring

Date: received 3 Apr 2008, last revised 26 Jun 2008

Contact author: dbrown at certicom com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Note: Cited previous work of Bentahar

Version: 20080626:130307 (All versions of this report)

Short URL: ia.cr/2008/149

Discussion forum: Show discussion | Start new discussion