Re: [Cfrg] ECC reboot

[Ilari Liusvaara <[e-mail]>]

On Thu, Oct 23, 2014 at 02:17:35PM -0400, Phillip Hallam-Baker wrote:
> 
> And the AVX-512 extensions provide 512 bit native registers.

Those are vectored registers. The widest multiply appears to be
64x64->128.

Even if 2^512-569 seems like it fits into 8x64 bits, unless you have
good carry handling (you don't for SIMD on Intel CPUs), you need 9x64
bits for optimal speed.

Now, the 9x64 bits could also store 2^521-1 (or 2^522-2), which have
faster reductions due to constant being small and power of two (or 1).

This explains why 2^521-1 is faster than 2^512-567, despite having to
do 9 extra bits and seemingly break word boundary.


Similarly, current fastest implementations for Curve25519 use 5x64
bits, not 4x64 bits.


-Ilari