[curves] The Pareto frontiers of sleeveless primes

[Michael Hamburg]

> On Oct 26, 2014, at 11:57 PM, Mike Hamburg <mike at shiftleft.org> wrote:

> Right.  In my try, I had calculated it by multiplication not requiring internal carry propagation, which depends on c as well as nail length.  This can be computed by expanding the prime into polynomial P in the radix, and comparing the largest coefficient of ((x^limbs - 1) / (x-1))^2 mod P to 2^(2*wordsize - 2*radix - extra). Here extra is some small amount (0.1) to account for not having reduced perfectly the first time; + 1 if the polynomial is signed;


+1 if the polynomial is signed isn’t quite right actually.  It should be something more like, always treat the non-leading coefficients of the polynomial as negative, so that when computing the reduction they always add to each other rather than canceling.

— Mike
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20141027/80097e57/attachment.html>