[curves] The Pareto frontiers of sleeveless primes

[Ben Harris]

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 <mike at shiftleft.org> wrote:

>
> 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
>
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20141029/e9c5d89d/attachment.html>