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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
