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 format(s): 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)
Short URL: ia.cr/2010/047
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]