[curves] The Pareto frontiers of sleeveless primes
mike at shiftleft.org
Mon Oct 27 02:17:35 PDT 2014
> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Curves