The most important computation in ECC is single-scalar multiplication: computing the curve point nP given an integer n and a curve point P. This is the bottleneck in
Montgomery curves y^2=x^3+Ax^2+x support a very simple scalar-multiplication method, the Montgomery ladder, introduced by 1987 Montgomery. There are several reasons that the Montgomery ladder is simpler than, e.g., the standard short-Weierstrass scalar-multiplication methods:
SafeCurves requires curves to support simple, fast, constant-time single-coordinate single-scalar multiplication, avoiding conflicts between simplicity, efficiency, and security. This is not a requirement specifically to use Montgomery curves: there are other types of curves that support simple, fast, constant-time ladders. "Fast" means that implementations of scalar multiplication for the same curve cannot be much faster, and "simple" means that reasonably fast implementations of scalar multiplication for the same curve cannot be much more concise. At this time there are no examples close enough to the edge to warrant quantification of "much".
Isomorphism (and birational equivalence)
One can sometimes convert a short Weierstrass curve y^2=x^3+ax+b to a Montgomery curve as follows. Find r satisfying r^3+ar+b=0. Find s satisfying s^2=3r^2+a. Define u=(x-r)/s, B=1/s^3, and A=3r/s. Then By^2=u^3+Au^2+u. One can perform x-coordinate scalar multiplication on y^2=x^3+ax+b by converting x to u, performing u-coordinate scalar multiplication on By^2=u^3+Au^2+u with the Montgomery ladder, and converting back.
The reason this does not always work is that, for the majority of curves, the field F_p does not contain suitable elements r and s. One can work around this by replacing F_p with an extension field, but this requires much less simple field operations inside scalar multiplication.
In particular, curves of prime order or 2*prime order can never be converted to Montgomery curves over F_p: Montgomery curves always have order divisible by 4.
The Brier–Joye ladder
2003 Brier–Joye presented a constant-time x-coordinate ladder applicable to every short Weierstrass curve y^2=x^3+ax+b. However, the Brier–Joye ladder is much slower than the Montgomery ladder: it requires 19 field operations per bit, many more field operations than standard addition chains for short Weierstrass curves. It thus creates a conflict between efficiency and security.
The following table reports the ladder support for various existing curves:
Version: This is version 2013.10.13 of the ladder.html web page.