Re: [Cfrg] Comparing ECC curves

[Mike Hamburg <[e-mail]>]

On 7/24/2014 8:11 AM, Phillip Hallam-Baker wrote:
> E-521 seems to have been chosen as the fastest prime giving a work
> factor of at least 2^256. If someone finds a prime that gives a work
> factor of 2^240  and is 30% faster, I would have to think about which I
> preferred.
It may interest you to know that that the prime 2^480 - 2^240 - 1 is 
about 40% faster than 2^512 - 569 on modern 64-bit Intel processors, 
meaning that each field operation takes about 60% of the time.  For 
example, on Haswell a field multiply mod 2^480 - 2^240 - 1 costs about 
121 cycles, and addition (with no reduce, because of reduced radix) 
takes fewer cycles than the pipeline (it's just two AVX2 add instructions).

I believe it is also about that much faster on than 2^521 - 1 on Sandy 
Bridge, but only by 20% or so on Haswell due to an implementation of 
multiplication mod 2^521-1 using 3-way Karatsuba/Chung-Hasan with AVX2.  
It uses 9 limbs of 58 bits each organized as (Z[w]/(w^3-2))[t]/(t^3-w), 
and needs AVX2 for all the adding.

I don't know how the three primes stack up on ARM.

-- Mike