Make secp256k1_i128_check_pow2 support -(2^n)
Make secp256k1_modinv64_det_check_pow2 support abs val
Native jacobi symbol algorithm
This introduces variants of the divsteps-based GCD algorithm used for
modular inverses to compute Jacobi symbols. Changes compared to
the normal vartime divsteps:
* Only positive matrices are used, guaranteeing that f and g remain
positive.
* An additional jac variable is updated to track sign changes during
matrix computation.
* There is (so far) no proof that this algorithm terminates within
reasonable amount of time for every input, but experimentally it
appears to almost always need less than 900 iterations. To account
for that, only a bounded number of iterations is performed (1500),
after which failure is returned. In VERIFY mode a lower iteration
count is used to make sure that callers exercise their fallback.
* The algorithm converges to f=g=gcd(f0,g0) rather than g=0. To keep
this test simple, the end condition is f=1, which won't be reached
if started with non-coprime or g=0 inputs. Because of that we only
support coprime non-zero inputs.
Add secp256k1_fe_is_square_var function
The implementation calls the secp256k1_modinvNN_jacobi_var code, falling back
to computing a square root in the (extremely rare) case it failed converge.
Describe Jacobi calculation in safegcd_implementation.md
This is a backport of secp256k1#979