perf: optimize Eisenstein arithmetic

[yelhousni]

Description

Some optimisations for Eisenstein arithmetic. This saves -50% for Half-GCD which we use in hints for emulated scalar multiplications in gnark.

Type of change

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

How has this been tested?

Existing tests pass + test for new method MulByConjugate.

How has this been benchmarked?

Macbook Air M1:

benchmark              old ns/op     new ns/op     delta
BenchmarkHalfGCD-8     74454         36803         -50.57%
BenchmarkMul-8         175           113           -35.17%
BenchmarkNorm-8        109           60.2          -44.93%
BenchmarkQuoRem-8      1034          396           -61.69%

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

[Copilot]

Pull Request Overview

This PR optimizes Eisenstein integer arithmetic by switching to inline big.Int storage, introducing Karatsuba-based multiplication, and adding new division routines (Quo, MulByConjugate) and round-nearest logic.
Key changes:

• Redesigned ComplexNumber to store temporaries and prevent unintended copies.
• Added MulByConjugate, roundNearest, Quo, and reworked QuoRem and HalfGCD for performance.
• Updated tests and benchmarks to cover the new methods and signatures.

Reviewed Changes

Copilot reviewed 2 out of 2 changed files in this pull request and generated 3 comments.

File	Description
field/eisenstein/eisenstein.go	Refactored ComplexNumber, implemented Karatsuba mul, new division and rounding methods, and adjusted HalfGCD.
field/eisenstein/eisenstein_test.go	Added property tests for MulByConjugate, updated Norm and QuoRem tests, and expanded benchmarks.

Comments suppressed due to low confidence (1)

field/eisenstein/eisenstein_test.go:122

• The new property in TestEisensteinArithmetic is never executed because there's no properties.TestingRun call at the end of that test function. Add properties.TestingRun(t, gopter.ConsoleReporter(false)) to ensure the property runs.

	properties.Property("Mul(Conjugate) & MulByConjugate should output the same result", prop.ForAll(

[cursor]

Bug: Nil Pointer Dereference in Complex Number Benchmarks

The new benchmark functions BenchmarkMul, BenchmarkNorm, and BenchmarkQuoRem attempt to use uninitialized *ComplexNumber pointers from the benchRes array (e.g., benchRes[0], benchRes[1]). Since benchRes elements are nil by default, these operations result in nil pointer dereference panics when methods are called or fields are accessed.

field/eisenstein/eisenstein_test.go#L394-L405

gnark-crypto/field/eisenstein/eisenstein_test.go

Lines 394 to 405 in 0dcd1ad

	for i := 0; i < b.N; i++ {
	benchRes[0].Mul(&a, &c)
	}
	}
	func BenchmarkNorm(b *testing.B) {
	a0, _ := new(big.Int).SetString("121538263010334165887337363056149355411", 10)
	a1, _ := new(big.Int).SetString("249054933928109647438301795139995905723", 10)
	a := ComplexNumber{A0: *a0, A1: *a1}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
	a.Norm(&benchRes[0].A0)

field/eisenstein/eisenstein_test.go#L417-L418

gnark-crypto/field/eisenstein/eisenstein_test.go

Lines 417 to 418 in 0dcd1ad

	for i := 0; i < b.N; i++ {
	benchRes[0].QuoRem(&a, &c, benchRes[1])

Fix in Cursor • Fix in Web

---

Bug: Method Modifies Input Parameter Violating Expectations

The QuoRem method incorrectly modifies its input parameter x by using x.t1 as a temporary variable for norm calculations. This violates the expectation that input parameters remain unchanged. Specifically, when the receiver z and parameter x are the same object, bestQ0 (aliased to z.t1) is overwritten by candR.Norm(&x.t1) before the comparison, leading to incorrect quotient selection in the Euclidean division's lattice search.

field/eisenstein/eisenstein.go#L265-L270

gnark-crypto/field/eisenstein/eisenstein.go

Lines 265 to 270 in 0dcd1ad

	if candR.Norm(&x.t1).Cmp(bestNorm) < 0 {
	bestQ0.Set(&z.A0)
	bestQ1.Set(&z.A1)
	r.Set(&candR)
	bestNorm.Set(&x.t1)

field/eisenstein/eisenstein.go#L240-L241

gnark-crypto/field/eisenstein/eisenstein.go

Lines 240 to 241 in 0dcd1ad

	// If Euclidean inequality already holds we're done.
	if r.Norm(&x.t1).Cmp(&y.t0) < 0 {

Fix in Cursor • Fix in Web

---

Was this report helpful? Give feedback by reacting with 👍 or 👎