Re: [Cfrg] ECC reboot

[Michael Hamburg <[e-mail]>]

> On Oct 23, 2014, at 3:21 PM, Samuel Neves <[e-mail]> wrote:
> 
> On 23-10-2014 21:14, Michael Hamburg wrote:
>> Goldilocks should work well in 512-bit registers.  If Intel has single-cycle PMUL[U]DQ on 512 bits, that will become the largest multiplier on the chip: 8x32x32 -> 8x64 compared to the 64x64->128 scalar multiplier.  The ARM NEON Karatsuba implementation should translate pretty well to that primitive, but the devil is in the details.
> 
> AVX-512 has better than VPMUL[U]DQ. Not only does AVX-512* have VPMULLQ (64x64->64), which is useful on its own, but
> also VPMADD52{L,H}UQ, which does a 52-bit multiply followed by a 64-bit addition of either the lower or upper 52 bits of
> the product. This latter instruction seems to expose the floating-point circuitry to the user.
> 
> * The fancy version of AVX-512, expected to be in Skylake; Knight's Corner only has a limited subset named AVX-512F.

Oh, huh, that’s pretty neat.  At first glance, it looks like it’d be most useful for an implementation of a 384-bit prime with radix 2^48.

Curve41417 or a curve over 2^416-2^208-1 would also work with radix 2^52 (since 8*52 = 416), but you’d have to reduce almost completely before multiplying which would offset the gains.

A final possibility is that since the register file of AVX512 is gi-freaking-normous, you could try to do 2-4 multiplies at a time using the extended addition formula.  Then you wouldn’t have to worry as much about the 416-bit input size of this operation, and it would be easier to apply to other primes.

— Mike