2002/08/05 by Kirsten Eisentraeger, Kristin Lauter, Eisentraeger, Kirsten +3 · 2 citations
Computer Science · Mathematics · #11T71 #14G50 #Algebraic Geometry and Number Theory #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #math.NT #msc:11T71 #msc:14G50
paper · pdf · doi:10.48550/arxiv.math/0208038
12 pages, added some consequences for computing the Weil Pairing, to appear in Proceedings of RSA-CT 2003
openalex publication_date 2002/08/05 · arxiv created 2003/01/22 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an algorithm which speeds scalar multiplication on a general elliptic curve by an estimated 3.8 % to 8.5 % over the best known general methods when using affine coordinates. This is achieved by eliminating a field multiplication when we compute 2P+Q from given points P, Q on the curve. We give applications to simultaneous multiple scalar multiplication and to the Elliptic Curve Method of factorization. We show how this improvement together with another idea can speed the computation of the Weil and Tate pairings by up to 7.8 %.