Montgomery Algorithm over a Prime Field

New formulae for point addition and point doubling on elliptic curves over prime fields are presented. Based on these formulae, an improved Montgomery algorithm is proposed. The theoretical analysis indicates that it is about 13.4% faster than Brier and Joye's Montgomery algorithm. Experiments on the elliptic curve over a 256-bit prime field recommended by the National Institute of Standards and Technology and over a 256-bit prime field in Chinese elliptic curve standard SM2 support the theoretical analysis.