I just quickly played around with this too. Looking at 96 potential Crandalls (2^n - c, 80 <= n <= 1024, c < 32, no prime for smaller c), looking at those that aren't dominated for size, 32-bit length, 28-bit limbs or 58-bit limbs gets 60 potentials. Ignoring the 28-bit kills 9 more.
prime mod 4 28 32 58 2^95 - 15 1 4 3 2 2^96 - 17 3 4 3 2 2^109 - 31 1 4 4 2 2^110 - 21 3 4 4 2 2^116 - 3 1 5 4 2 2^122 - 3 1 5 4 3 2^127 - 1 3 5 4 3 2^137 - 13 3 5 5 3 2^140 - 27 1 5 5 3 2^152 - 17 3 6 5 3 2^158 - 15 1 6 5 3 2^166 - 5 3 6 6 3 2^174 - 3 1 7 6 3 2^189 - 25 3 7 6 4 2^191 - 19 1 7 6 4 2^196 - 15 1 7 7 4 2^206 - 5 3 8 7 4 2^221 - 3 1 8 7 4 2^226 - 5 3 9 8 4 2^230 - 27 1 9 8 4 2^235 - 15 1 9 8 5 2^251 - 9 3 9 8 5 2^255 - 19 1 10 8 5 2^266 - 3 1 10 9 5 2^285 - 9 3 11 9 5 2^291 - 19 1 11 10 6 2^321 - 9 3 12 11 6 2^336 - 3 1 12 11 6 2^338 - 15 1 13 11 6 2^369 - 25 3 14 12 7 2^383 - 31 1 14 12 7 2^389 - 21 3 14 13 7 2^401 - 31 1 15 13 7 2^414 - 17 3 15 13 8 2^444 - 17 3 16 14 8 2^452 - 3 1 17 15 8 2^468 - 17 3 17 15 9 2^489 - 21 3 18 16 9 2^495 - 31 1 18 16 9 2^521 - 1 3 19 17 9 2^529 - 31 1 19 17 10 2^537 - 9 3 20 17 10 2^546 - 11 1 20 18 10 2^550 - 5 3 20 18 10 2^563 - 9 3 21 18 10 2^583 - 27 1 21 19 11 2^607 - 1 3 22 19 11 2^610 - 27 1 22 20 11 2^620 - 15 1 23 20 11 2^664 - 17 3 24 21 12 2^694 - 3 1 25 22 12 2^699 - 9 3 25 22 13 2^715 - 7 1 26 23 13 2^717 - 25 3 26 23 13 2^729 - 9 3 27 23 13 2^810 - 5 3 29 26 14 2^848 - 17 3 31 27 15 2^850 - 3 1 31 27 15 2^869 - 21 3 32 28 15 2^923 - 31 1 33 29 16 On 27 October 2014 17:17, Michael Hamburg <[email protected]> wrote: > > On Oct 26, 2014, at 11:57 PM, Mike Hamburg <[email protected]> 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 > > _______________________________________________ > Curves mailing list > [email protected] > https://moderncrypto.org/mailman/listinfo/curves > >
_______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
