perf: Legendre using Pornin20

[Tabaie]

This PR implements Legendre symbol calculation based on the Binary GCD algorithm.
For large fields, the approximation approach from https://eprint.iacr.org/2020/972 is used to achieve about 50% additional speedup over "vanilla" Binary GCD. (Benchmarked over the base field of BLS12-381 https://github.com/Consensys/gnark-crypto/blob/perf/legendre-symbol-p20/ecc/bls12-381/fp/element_test.go#L2954)

[Copilot]

Pull Request Overview

This PR replaces the exponentiation-based Legendre symbol calculation with an optimized binary GCD algorithm (Pornin20) across all field and curve implementations, adds a zero-value test case, and updates the code generator and configuration to support the new approach.

• Implement the Pornin20 binary GCD method for Legendre() in all element.go
• Add require.Equal(t, 0, new(Element).Legendre(), "(0|q) must be zero") to all element_test.go
• Update generator templates (tests.go, sqrt.go, inverse.go, base.go) and config (field_config.go) to support the new algorithm

Reviewed Changes

Copilot reviewed 51 out of 51 changed files in this pull request and generated no comments.

Show a summary per file

File	Description
field/koalabear/element.go	Replace exponentiation with Pornin20 binary GCD algorithm
field/koalabear/element_test.go	Add zero-case Legendre test
field/goldilocks/element.go	Same as above
field/goldilocks/element_test.go	Same as above
field/babybear/element.go	Same as above
field/babybear/element_test.go	Same as above
ecc/stark-curve/fr/element.go	Same as above for ECC curve
ecc/stark-curve/fr/element_test.go	Same as above
ecc/stark-curve/fp/element.go	Same as above for FP
ecc/stark-curve/fp/element_test.go	Same as above
ecc/secp256k1/...	Same as above for secp256k1
ecc/grumpkin/...	Same as above for grumpkin
... (all other curve backends)	Same as above
field/generator/internal/templates/element/tests.go	Add zero-case test in generator
field/generator/internal/templates/element/sqrt.go	Inject Pornin20 Legendre in template
field/generator/internal/templates/element/inverse.go	Fix approximate mask constant
field/generator/internal/templates/element/base.go	Add missing period to comment
field/generator/config/field_config.go	Add new slice NbWordsIndexesNoZeroNoLast and fix ranges

Comments suppressed due to low confidence (1)

field/generator/config/field_config.go:200

• The loop for i := range F.NbWords attempts to range over an integer. It should iterate over the slice F.NbWordsIndexesFull, for example:

for i := range F.NbWordsIndexesFull {
    F.NbWordsIndexesFull[i] = i
}

	for i := range F.NbWords {

[yelhousni]

Great PR and great documentation!

I would just remove expByLegendreExp from element_exp.go or maybe keep it and add a test against Legendre() to check that the GCD approach and Euler's criterion output the same result (the test with big.Jacobi also uses GCD).

[Tabaie]

Great PR and great documentation!

I would just remove expByLegendreExp from element_exp.go or maybe keep it and add a test against Legendre() to check that the GCD approach and Euler's criterion output the same result (the test with big.Jacobi also uses GCD).

Thank you! Since it was a lot of code I opted for deleting.