Fast 4 way vectorized ladder for the complete set of Montgomery curves

Abstract

This paper introduces 4 way vectorization of Montgomery ladder on any Montgomery form elliptic curve. Our algorithm takes 2M4 + 1S 4 (M4 : A vector of four field multiplications, S 4 : A vector of four field squarings) per ladder step for variable-scalar variable-point multiplication. This is a theoretical improvement over the squared Kummer ladder which takes 2M4 + 1S 4 + 1d 4 per ladder step. This paper also introduces new formulas for doing arithmetic over GF(2255 − 19). We provide two implementations of curve25519 using our proposed algorithm. The first implementation uses AVX2 instruction set and takes 98484 cycles. This is competitive with the current speed record of 95437 cycles by Nath and Sarkar. The second implementation uses AVX-512 instruction set and takes 74368 cycles. This sets the new speed record over Faz-Hernandez, L ´ opez, and Dahab’s implementation ´ which takes 81600 cycles.