sage: verify Eisenstein integer connection for GLV constants #1800

Justsomebuddy commented at 11:26 AM on January 14, 2026: contributor

Summary

Add assertions to gen_split_lambda_constants.sage to verify that the GLV decomposition constants arise from the Eisenstein integer factorization of the group order N.

Specifically:

N = a^2 + a*b + b^2 (norm equation in Z[ω])
λ = b/a mod N (eigenvalue from Z[ω]/(π) ≅ Z/NZ isomorphism)

This addresses the suggestion in #1798 to document/verify the algebraic origin of these constants in the sage script rather than C comments.

Details

The group order N factors as N = π·π̄ in the Eisenstein integers Z[ω], where:

ω = (-1 + √-3)/2 is a primitive cube root of unity
π = a - b·ω is an Eisenstein prime with norm N(π) = a² + ab + b²

The GLV constants (A1, B1) correspond to the Eisenstein factors (b, -a), and the endomorphism eigenvalue λ arises naturally as the image of ω under the quotient map Z[ω] → Z[ω]/(π) ≅ Z/NZ.

Closes #1798

in sage/gen_split_lambda_constants.sage:86 in d096bfbffe

  80 | @@ -81,6 +81,15 @@ assert (A1 + A2)/2 < sqrt(N)
  81 |  assert B1 < sqrt(N)
  82 |  assert B2 < sqrt(N)
  83 |  
  84 | +# Verify connection to Eisenstein integers Z[w] where w = (-1 + sqrt(-3))/2.
  85 | +# The group order N factors as N = pi * conj(pi) in Z[w], where pi = a - b*w
  86 | +# is an Eisenstein prime with norm N(pi) = a^2 + a*b + b^2. The GLV endomorphism

real-or-random commented at 1:16 PM on January 14, 2026:

N is overloaded here.

# The group order N factors as N = pi * conj(pi) in Z[w], where pi = a - b*w
# is an Eisenstein prime with norm a^2 + a*b + b^2. The GLV endomorphism

in sage/gen_split_lambda_constants.sage:87 in d096bfbffe

  80 | @@ -81,6 +81,15 @@ assert (A1 + A2)/2 < sqrt(N)
  81 |  assert B1 < sqrt(N)
  82 |  assert B2 < sqrt(N)
  83 |  
  84 | +# Verify connection to Eisenstein integers Z[w] where w = (-1 + sqrt(-3))/2.
  85 | +# The group order N factors as N = pi * conj(pi) in Z[w], where pi = a - b*w
  86 | +# is an Eisenstein prime with norm N(pi) = a^2 + a*b + b^2. The GLV endomorphism
  87 | +# eigenvalue lambda arises as the image of w under the isomorphism Z[w]/(pi) = Z/NZ.

real-or-random commented at 1:17 PM on January 14, 2026:

# eigenvalue LAMBDA arises as the image of w under the isomorphism Z[w]/(pi) = Z/NZ.

Is this really what the second assert checks? If yes, I don't see the connection immediately. Can you expand?

in sage/gen_split_lambda_constants.sage:88 in d096bfbffe

  80 | @@ -81,6 +81,15 @@ assert (A1 + A2)/2 < sqrt(N)
  81 |  assert B1 < sqrt(N)
  82 |  assert B2 < sqrt(N)
  83 |  
  84 | +# Verify connection to Eisenstein integers Z[w] where w = (-1 + sqrt(-3))/2.
  85 | +# The group order N factors as N = pi * conj(pi) in Z[w], where pi = a - b*w
  86 | +# is an Eisenstein prime with norm N(pi) = a^2 + a*b + b^2. The GLV endomorphism
  87 | +# eigenvalue lambda arises as the image of w under the isomorphism Z[w]/(pi) = Z/NZ.
  88 | +# Reference: https://github.com/bitcoin-core/secp256k1/issues/1798

real-or-random commented at 1:18 PM on January 14, 2026:

I suggest dropping this line. The code should be self-contained. (Of course, there's always more background, but people can use git blame.)

in sage/gen_split_lambda_constants.sage:89 in d096bfbffe

  80 | @@ -81,6 +81,15 @@ assert (A1 + A2)/2 < sqrt(N)
  81 |  assert B1 < sqrt(N)
  82 |  assert B2 < sqrt(N)
  83 |  
  84 | +# Verify connection to Eisenstein integers Z[w] where w = (-1 + sqrt(-3))/2.
  85 | +# The group order N factors as N = pi * conj(pi) in Z[w], where pi = a - b*w
  86 | +# is an Eisenstein prime with norm N(pi) = a^2 + a*b + b^2. The GLV endomorphism
  87 | +# eigenvalue lambda arises as the image of w under the isomorphism Z[w]/(pi) = Z/NZ.
  88 | +# Reference: https://github.com/bitcoin-core/secp256k1/issues/1798
  89 | +a_eis, b_eis = -B1, A1

real-or-random commented at 1:18 PM on January 14, 2026:

A_EIS, B_EIS = -B1, A1

these are constants.

in sage/gen_split_lambda_constants.sage:91 in d096bfbffe

  86 | +# is an Eisenstein prime with norm N(pi) = a^2 + a*b + b^2. The GLV endomorphism
  87 | +# eigenvalue lambda arises as the image of w under the isomorphism Z[w]/(pi) = Z/NZ.
  88 | +# Reference: https://github.com/bitcoin-core/secp256k1/issues/1798
  89 | +a_eis, b_eis = -B1, A1
  90 | +assert a_eis**2 + a_eis*b_eis + b_eis**2 == N, "N = a^2 + a*b + b^2 (Eisenstein norm)"
  91 | +assert Z(b_eis * inverse_mod(int(a_eis), int(N))) == LAMBDA, "lambda = b/a mod N"

real-or-random commented at 1:19 PM on January 14, 2026:

assert Z(b_eis / a_eis) == LAMBDA, "lambda = b/a mod N"

Pretty sure this works in sage. (And then you can drop the string because it doesn't add anything.)

in sage/gen_split_lambda_constants.sage:90 in d096bfbffe

  85 | +# The group order N factors as N = pi * conj(pi) in Z[w], where pi = a - b*w
  86 | +# is an Eisenstein prime with norm N(pi) = a^2 + a*b + b^2. The GLV endomorphism
  87 | +# eigenvalue lambda arises as the image of w under the isomorphism Z[w]/(pi) = Z/NZ.
  88 | +# Reference: https://github.com/bitcoin-core/secp256k1/issues/1798
  89 | +a_eis, b_eis = -B1, A1
  90 | +assert a_eis**2 + a_eis*b_eis + b_eis**2 == N, "N = a^2 + a*b + b^2 (Eisenstein norm)"

real-or-random commented at 1:22 PM on January 14, 2026:

I don't think the string adds much. I suggest dropping it.

real-or-random added the label meta/development on Jan 14, 2026

Justsomebuddy force-pushed on Jan 14, 2026

sage: verify Eisenstein integer connection for GLV constants

Add assertions to verify that the GLV decomposition constants arise
from the Eisenstein integer factorization of the group order N.

The group order factors as N = pi * conj(pi) in Z[w], where pi = A - B*w
is an Eisenstein prime. The GLV eigenvalue LAMBDA = B/A mod N, which is
the image of w^2 under the isomorphism Z[w]/(pi) -> Z/NZ.

29ac4d8491

Justsomebuddy force-pushed on Jan 14, 2026

Justsomebuddy commented at 3:49 PM on January 14, 2026: contributor

Thanks for the review! I've updated the code and the comment to address your suggestions.

Regarding your question about the second assert:

The connection is:

pi = A - B*w is an Eisenstein prime with Norm(pi) = N
Under the isomorphism Z[w]/(pi) -> Z/NZ: w -> A/B (from A - B*w = 0)
Since (A/B)^3 = 1 in Z/NZ, we have (A/B)^2 = (A/B)^{-1} = B/A
Therefore LAMBDA = B/A is the image of w^2 under this isomorphism

I've updated the comment to clarify this.

real-or-random approved

real-or-random commented at 10:04 AM on January 21, 2026: contributor

utACK 29ac4d8491b326ffaeb8e43d152a2d09049b9af3

real-or-random merged this on Jan 21, 2026

real-or-random closed this on Jan 21, 2026

fanquake referenced this in commit c4c4e04ca1 on Jan 26, 2026

fanquake referenced this in commit 2fccbea3c8 on Jan 27, 2026

fjahr referenced this in commit 182197f98a on Jan 29, 2026

fjahr referenced this in commit ea9a84ab3c on Jan 31, 2026

fjahr referenced this in commit 23c2527f12 on Feb 8, 2026

Sjors referenced this in commit d5660d3a13 on Feb 16, 2026

github-actions[bot] referenced this in commit c3f80fff5f on Mar 1, 2026

github-actions[bot] referenced this in commit 4aeff8400e on Mar 1, 2026

github-actions[bot] referenced this in commit 5f15eb0c55 on Mar 1, 2026

0x000000000019d6689c085ae165831e934ff76 referenced this in commit d54574beca on Mar 2, 2026

csjones referenced this in commit fb3e16af04 on Mar 2, 2026

real-or-random referenced this in commit 459eab20f2 on Mar 3, 2026

vmta referenced this in commit 1ddc2f947f on Apr 26, 2026

vmta referenced this in commit 56c40fe100 on Apr 27, 2026