Perf: Optimize Sqrt in Fp2 for all fields

[yelhousni]

Description

Optimise the square root computations in the quadratic extension Fp2. Applications: Hash-to-G2 and G2-points decompression. This PR implements https://eprint.iacr.org/2024/1563.pdf (Alg. 3) for the case p = 3 mod 4 and https://eprint.iacr.org/2020/1497.pdf (Sec. 6.3) otherwise.

N.B.: We can further optimize the generic case (e.g. BLS12-377, KoalaBear) by merging the inverse and sqrt computations as 1/x = x^{p-2} = x^{2^{e-1}-1} * (x * y^4)^{2^{e-1}} where y is the same exponentiation computed in Tonelli-Shanks sqrt (y = x^{(p-2^e-1)/(2^{e+1})}).

Type of change

• New feature (non-breaking change which adds functionality)

How has this been tested?

Current Sqrt tests pass.

How has this been benchmarked?

A few benchmarks on AWS z1d.large:

• BN254 Fp2:

benchmark             old ns/op     new ns/op     delta
BenchmarkE2Sqrt-8     42712         11773         -72.44%

• BLS12-381 Fp2:

benchmark             old ns/op     new ns/op     delta
BenchmarkE2Sqrt-2     107870        27895         -74.14%

• BLS12-377 Fp2:

benchmark             old ns/op     new ns/op     delta
BenchmarkE2Sqrt-2     118520        73473         -38.01%

• KoalaBear Fp2 and Fp4:

benchmark             old ns/op     new ns/op     delta
BenchmarkE2Sqrt-8     1814          1292          -28.78%
BenchmarkE4Sqrt-8     5924          3321          -43.94%

Checklist:

• I have performed a self-review of my code
• I have commented my code, particularly in hard-to-understand areas
• I have made corresponding changes to the documentation
• I have added tests that prove my fix is effective or that my feature works
• I did not modify files generated from templates
• golangci-lint does not output errors locally
• New and existing unit tests pass locally with my changes
• Any dependent changes have been merged and published in downstream modules

---

Note

Optimizes Fp2 (E2) Sqrt using new algorithms (p≡3 mod 4 and p≡1 mod 4), adds exported exponentiation helpers, updates codegen/templates, and refreshes tests/benchmarks; also introduces a combined SqrtAndInverse for bls12-377.

• Algorithms/Implementations:
  • Optimize E2.Sqrt across curves:
    • p≡3 (mod 4): Aardal et al. (Algo 3) using ExpBySqrtPp1o4/ExpBySqrtPm3o4.
    • p≡1 (mod 4): Scott (Sec. 6.3); uses direct sqrt composition, some cases with fused inverse.
  • Add bls12-377/fp.Element.SqrtAndInverse and internal expByC1.
• Exponentiation helpers (exported):
  • Rename and export fixed-exponent ops: ExpBySqrtExp, ExpBySqrtPp1o4, ExpBySqrtPm3o4, ExpBySqrtPm5o8, ExpByLegendreExp (replace expBy*).
• Code generation/templates:
  • Generate exported ExpBy… helpers (pp1o4/pm3o4/pm5o8) and updated E2.Sqrt templates.
  • Extend config with SqrtQ3Mod4Exponent2; wire addchain data accordingly.
• Field updates:
  • Update Sqrt in various fp/fr packages to use new helpers; adjust comments.
  • Update Sqrt in Fp for q≡3 mod 4 to use ExpBySqrtPp1o4.
• Tests/Benchmarks:
  • Update tests to new exported helper names and exponents.
  • Adjust BenchmarkE2Sqrt/E4Sqrt to pre-square inputs and avoid aliasing.

^{Written by Cursor Bugbot for commit d08787a. This will update automatically on new commits. Configure here.}

[gbotrel]

lgtm, just I think the ExpByXXXX functions that are now public should have better names / docs, see comments

[cursor]

Bug: Incorrect Exponent Assignment in Constant

The sqrtExponent2{{.ElementName}} constant is incorrectly assigned {{.SqrtQ3Mod4Exponent}}. It should use {{.SqrtQ3Mod4Exponent2}} to represent the distinct (p-3)/4 exponent, instead of duplicating the (p+1)/4 value.