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

[Robert Ransom]

On 1/19/15, Watson Ladd <watsonbladd at gmail.com> wrote:
> So I remember a while ago we had a list of high performance primes. I
> don't remember 2^379-19 being on it, but can check to see if there are
> obviously dominated choices.
>
> But it seems that any prime with exponent between 352 and 384 will
> have the same full-width performance. (I imagine the reduction is a
> variant of Barrett reduction). I do think that 2^389-21 probably
> wasn't the best choice: it was one of two suggested primes, the other
> being 2^383-31, which has similar properties to 2^379-19.

-31 is congruent to 1 mod 8, which makes square roots rather more annoying.

Samuel Neves suggested 2^379-19 in
<http://www.ietf.org/mail-archive/web/cfrg/current/msg05626.html>.


Robert Ransom