Re: [Cfrg] ECC mod 8^91+5

["D. J. Bernstein" <[e-mail]>]

Ilari Liusvaara writes:
> Unfortunately there is another related problem: The theorem that says
> that folded Montgomery ladder always works assumes that there is
> unique point of order 2.

The theorem in the Curve25519 paper assumed a unique point of order 2,
but this turned out to be unnecessary. See Theorem 4.5 in

   https://cr.yp.to/papers.html#montladder

and in particular the proofs of the underlying DBL and DADD theorems via
the Edwards addition law. The paper also gives proofs from the
historical Weierstrass perspective.

The completeness issue is more problematic outside the ladder context:

   * The fast complete Edwards formulas don't apply to this curve: the
     curve doesn't have a unique point of order 2.

   * The fast complete Hessian formulas also don't apply to this curve:
     the curve doesn't have a unique point of order 3.

   * The formulas from https://cr.yp.to/talks/2009.07.17/slides.pdf and
     https://eprint.iacr.org/2015/1060 do apply but don't meet the
     SafeCurves requirements of speed and simplicity ("implementations
     of scalar multiplication for the same curve cannot be much faster"
     and "reasonably fast implementations of scalar multiplication for
     the same curve cannot be much more concise"), so implementors are
     pressured to use incomplete formulas instead.

---Dan