sage: verify Eisenstein integer connection for GLV constants

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.

0# The group order N factors as N = pi * conj(pi) in Z[w], where pi = a - b*w
1# 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:

0# 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:

0A_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:

0assert 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

sage: verify Eisenstein integer connection for GLV constants #1800

Summary

Details