sipa/secp256k1 — pull request #19 by peterdettman (2014-01-30 12:51:56+00:00)
Title: Re-write secp256k1_fe_sqrt and secp256k1_fe_inv to use a sliding window ...

...over blocks of 1s

See e.g. http://www.item.ntnu.no/europki08/presentations/europki08-brumley.pdf for a rough description of using "repunit" windows (i.e. blocks of 1s).

This reduces the cost of a sqrt from 259S + 32M to 253S + 13M, and a similar improvement for inversion. The addition chain used is the same for both methods.