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

[Trevor Perrin]

At Real World Crypto, Patrick Longa discussed the question of choosing
efficient field primes for extra-strength curves.  He suggested such
primes should be chosen to strike a balance between efficiency in
full-radix and reduced-radix implementations (i.e. "saturated" and
"unsaturated" arithmetic):

http://www.realworldcrypto.com/rwc2015/program-2/RWC-2015-Longa.pdf?attredirects=0

2^379 - 19 was given as an example.

Most of the discussion of extra-strength primes I've seen assumes
reduced-radix implementations, so this is an interesting twist.  His
argument for considering full-radix was:

 1) Full-radix is more efficient on several platforms ("AMD, "Intel
Atom, Intel Quark, ARM w/o Neon, microcontrollers"), whereas
reduced-radix is most advantageous on more advanced processors ("Intel
desktop/server", "ARM with NEON").
 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".

I'm not qualified to assess (1).  But if it's true that full-radix
implementations are faster on more primitive platforms that seems
significant, since optimizing for these is probably more important
than achieving maximum speed on advanced processors.

Anyways, I'm curious what other people think of this approach, and of
2^379 - 19 in particular.

The slides give performance numbers for a "Ted37919" curve based on
this prime on Sandy Bridge, which I added to the spreadsheet here:

https://docs.google.com/a/trevp.net/spreadsheet/ccc?key=0Aiexaz_YjIpddFJuWlNZaDBvVTRFSjVYZDdjakxoRkE&usp=sharing#gid=0


Trevor