Optimize doubling: secp256k1 has no y=0 point #120

1. 
   sipa commented at 2:33 pm on November 28, 2014: contributor

   This gives a 1.5% verification improvement when using the endomorphism, 2.3% improvement when not.
2. 
   gmaxwell commented at 8:53 pm on November 28, 2014: contributor

   Add a comment that the assigment in the if is intentional or otherwise we’re going to get bug reports for it. (or leave the original handling for that branch, … doesn’t it generate the same code?)

   And yes, our curve has no point of order 2, so this must be safe.

   My chat backscroll suggests you used a somewhat different argument, about -7 having a cube root mod p. I guess the whole argument goes something like:

   “For some group element Q of curve E, if 2Q = Infinity, thus Q+Q = Q + -Q, thus Q = -Q, which means that Q.{x,y} = Q.{x,-y}, so this could only be true if there is some point on the curve with y=0, which is only true there exists a cube root of […]”.

   Might be useful to include the argument lest someone reviewing the code think it was just forgotten. :)

3. Optimize doubling: secp256k1 has no y=0 point f7dc1c6513
4. Explain why no y=0 check is necessary for doubling

   Explanation suggested by Greg Maxwell.

   e3d692ff75
5. sipa force-pushed on Nov 28, 2014
6. 
   sipa commented at 9:20 pm on November 28, 2014: contributor

   Fixed.
7. sipa cross-referenced this on Nov 28, 2014 from issue Avoid field inverse for r == x comparison by sipa
8. 
   gmaxwell commented at 9:17 am on December 1, 2014: contributor

   ACK. As semi-aside: Technically, do we even need the branch and return on infinity? just copy it over. Doen’t matter what the rest is… the common case is uh, not trying to double infinities. :P The branch should be perfectly predicted, so it may not matter at all though.
9. 
   sipa commented at 9:48 am on December 1, 2014: contributor

   I tried not branching and just setting infinity correctly, which seemed slower. I can’t explain why, as this should not be a common case.
10. 
    gmaxwell commented at 10:18 am on December 1, 2014: contributor

    Some test doing something dumb? Might just be a matter of stirring the alignment. No big deal in any case.
11. sipa merged this on Dec 1, 2014
12. sipa closed this on Dec 1, 2014

    ---

13. sipa referenced this in commit 0af5b47133 on Dec 1, 2014

Contributors
sipa gmaxwell