Cryptology ePrint Archive: Report 2010/047

Lower Bounds for Straight Line Factoring

Daniel R. L. Brown

Abstract: Straight line factoring algorithms include a variant Lenstra's elliptic curve method. This note proves lower bounds on the length of straight line factoring algorithms.

Category / Keywords: public-key cryptography / Factoring, RSA, Straight line programs

Date: received 29 Jan 2010, last revised 31 May 2010

Contact author: dbrown at certicom com

Available formats: PDF | BibTeX Citation

Note: Riesel may have produced similar results in 1985 (reported to me by D. J. Bernstein). Paper will be revised accordingly.

Version: 20100531:203208 (All versions of this report)

Discussion forum: Show discussion | Start new discussion