Faster const-time modinv divsteps (rebase of #1031) #1197

Algorithm by Peter Dettman, with original comments:

Changes to _divsteps_59 (_30) that give maybe 4% speed improvement to const-time modinv on 64 bit. I see a larger gain on 32 bit but measured on 64 bit so might not be real.

Start the result matrix scaled by 2^62 (resp. 2^30) and shift q, r down instead of u, v up at each step (should make life easier for vectorization). Since we're always shifting away the LSB of g, q, r, we can avoid doing a full negation for x, y, z (after a few tweaks).

A new variable $\theta = \delta - 1/2$ is introduced then, which is slightly cheaper than the $\zeta = -\delta-1/2$ used before.

Tested ACK 88d604e

Rebased on master (22245ae) and resolved the conflicts with the volatile barrier and determinant check in the modinv files. Tests and exhaustive tests pass fine.

Pushed the rebase here if useful: https://github.com/Yudis-bit/secp256k1/tree/fast_divsteps_rebase

57a09847d85f1207e2ec56129684fb2362e15e1e needs rebase

Tested Yudis-bit's rebase at 88d604e: inverses are correct and scalar_inverse is about 2% faster on Apple M5. This is not an ACK; the PR head still needs a rebase.

Yudis-bit's branch (fast_divsteps_rebase) applies cleanly to current master. I compared scalar and field inverses, constant-time and variable-time, with btclib-ecc's modular inverse on about 80,000 edge and random inputs. All results match, in plain, VERIFY and ASan/UBSan builds, and are bit-identical to master. The suite passes and the volatile barrier is kept. In bench_internal inverse, 15 interleaved runs per build, the median scalar_inverse goes from 1.52 to 1.49 us. The field_inverse difference, 1.3%, overlaps between runs and is within noise. The variable-time inverses did not change. I did not run the constant-time (valgrind) checks, and only the 64-bit path was timed. The harness and logs are available on request.