Extended Montgomery coordinates

[tarcieri]

This paper describes complete formulas for Montgomery curves which are as efficient as the ones for Edwards curves:

https://tches.iacr.org/index.php/TCHES/article/view/11808/11313

In this paper, we introduce extended Montgomery coordinates as a novel representa-tion for points on Montgomery curves. This coordinate system enables us to define birational multiplication-free maps between the extended twisted Edwards coordinates and extended Montgomery coordinates. Using this map, we can transfer the complete addition laws from twisted Edwards curves to Montgomery curves without incurring additional multiplications or squarings.

Notably there are places today where we implement operations on MontgomeryPoint by converting first to EdwardsPoint, performing the operation, and converting back to MontgomeryPoint, most importantly scalar multiplication. With an extended Montgomery coordinate system those same operations could be implemented directly on MontgomeryPoint, along with the full suite of e.g. group::Group operations.

See also: RustCrypto/elliptic-curves#1306

cc @daxpedda