Cryptology ePrint Archive: Report 2006/220

Multi-Dimensional Montgomery Ladders for Elliptic Curves

Daniel R. L. Brown

Abstract: Montgomery's ladder algorithm for elliptic curve scalar multiplication uses only the x-coordinates of points. Avoiding calculation of the y-coordinates saves time for certain curves. Montgomery introduced his method to accelerate Lenstra's elliptic curve method for integer factoring. Bernstein extended Montgomery's ladder algorithm by computing integer combinations of two points, thus accelerating signature verification over certain curves. This paper modifies and extends Bernstein's algorithm to integer combinations of two or more points.

Category / Keywords: implementation / ECC Montgomery ladder

Date: received 29 Jun 2006, last revised 30 Jun 2006

Contact author: dbrown at certicom com

Available format(s): PDF | BibTeX Citation

Note: To be updated.

Version: 20060630:134049 (All versions of this report)

Short URL: ia.cr/2006/220