Generate addition chains for exponentiation by fixed value in Sqrt

[gbotrel]

Using github.com/mmcloughlin/addchain (which is awesome 👍 ) ; code-generate exp by fix exponent for the field element Sqrt methods. A part from bls12-377 (using TonelliShanks) speed up for Sqrt is ~20%:

2021/11/10 19:39:41 comparing ../ecc/bls12-377/fp ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  30.2µs ± 1%  28.3µs ± 1%  -6.32%  (p=0.000 n=10+10)


2021/11/10 19:39:41 comparing ../ecc/bls12-377/fr ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  15.4µs ± 1%  14.2µs ± 1%  -8.26%  (p=0.000 n=9+10)


2021/11/10 19:39:41 comparing ../ecc/bls12-381/fp ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  16.8µs ± 2%  12.3µs ± 1%  -26.37%  (p=0.000 n=10+10)


2021/11/10 19:39:41 comparing ../ecc/bls12-381/fr ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  10.7µs ± 1%   8.9µs ± 0%  -16.39%  (p=0.000 n=10+10)


2021/11/10 19:39:41 comparing ../ecc/bls24-315/fp ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  11.6µs ± 1%   9.8µs ± 1%  -15.76%  (p=0.000 n=9+10)


2021/11/10 19:39:41 comparing ../ecc/bls24-315/fr ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  7.58µs ± 2%  6.38µs ± 1%  -15.82%  (p=0.000 n=10+10)


2021/11/10 19:39:41 comparing ../ecc/bn254/fp ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  5.63µs ± 1%  4.59µs ± 1%  -18.51%  (p=0.000 n=10+9)


2021/11/10 19:39:41 comparing ../ecc/bn254/fr ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  9.09µs ± 1%  7.92µs ± 1%  -12.79%  (p=0.000 n=10+10)


2021/11/10 19:39:41 comparing ../ecc/bw6-633/fp ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  67.9µs ± 1%  52.9µs ± 1%  -22.16%  (p=0.000 n=10+10)


2021/11/10 19:39:41 comparing ../ecc/bw6-633/fr ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  11.6µs ± 1%   9.7µs ± 1%  -16.21%  (p=0.000 n=10+10)


2021/11/10 19:39:41 comparing ../ecc/bw6-761/fp ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16   131µs ± 2%   105µs ± 1%  -19.62%  (p=0.000 n=10+10)


2021/11/10 19:39:41 comparing ../ecc/bw6-761/fr ElementSqrt
name            old time/op  new time/op  delta
ElementSqrt-16  30.6µs ± 1%  28.3µs ± 1%  -7.63%  (p=0.000 n=10+10)

Which should impact positively point decompression, among other things.

Generated code is in element_exp.go to avoid cluttering element.go .

Generated code for Legendre too, may not be worth it (not measured). For bls12-377 we may want to keep the older version for readability.

[gbotrel]

Update: worth it to keep it for Legendre (similar perf improvement).

Keeping it for sake of code generation simplicity for bls12-377, but this #98 will change our numbers anyway.

[yelhousni]

💯