[curves] Balancing reduced-radix and full-radix performance for extra-strength primes

[D. J. Bernstein]

http://bench.cr.yp.to/impl-scalarmult/curve25519.html compares speeds of
various Curve25519 implementations on various platforms. Longa was
presenting a small extract from this data.

For "64-bit" platforms the best non-vectorized radix is sometimes 2^64,
sometimes 2^51, for reasons explained in the Ed25519 paper. Vectorized
speed records---e.g., speed records on typical smartphones---typically
use radix 2^25.5.

Longa seemed to be trying to mislead people into believing that this
platform variation in _implementation_ techniques creates a platform
variation in _prime_ choices. It should be obvious that these data
points say nothing about prime choice: they're all for one prime.

A closer study of implementation techniques shows that choosing mediocre
primes such as 2^256-189

   * doesn't hurt typical full-radix implementations but
   * hurts typical reduced-radix implementations.

In other words, switching to mediocre primes hurts some platforms and
doesn't help others. To avoid seeing this damage, one has to ignore all
the reduced-radix implementations and ignore all the platforms where
those implementations are best---and even within these blinders there's
no advantage to the mediocre primes. Not A Tough Decision(tm).

I'm not saying that at _every_ security level there's a unique standout
cross-platform prime; I'm just saying that Longa wasn't looking at the
right data for the decision that he claimed to be interested in.

> 2) Full-radix may be safer and easier to implement, since
> reduced-radix requires "Bound analysis" to prevent inadvertent word
> spilling, thus is "error prone, errors are more difficult to catch".

There's a long history of hard-to-catch errors in full-radix software.
https://cryptojedi.org/papers/#verify25519 is the first step towards
confidently getting out of this mess---and it's significantly _easier_
for reduced-radix software than for full-radix software.

---Dan