How do you derive the lambda and beta values for endomorphism on the secp256k1 curve?

Question

You can see a little background about this on this bitcointalk post by the late Hal Finney.

Beta and lambda are the values on the secp256k1 curve where:

λ^3 (mod N) = 1

β^3 (mod P) = 1

As seen here, in hex, N and P are:

N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

The actual values of lambda and beta are easily verifiable and are:

λ = 5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

β = 7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

The question for me is, how do you derive this? Can someone show me step-by-step how you can figure out these values?

Also posted to the Cryptography Stack Exchange

You might be more likely to get an answer on the cryptography SE site. — Tyler, Feb 02 '15 at 07:03
Hal Finney says he found hints about how to compute it in pages 125-129 of the *Guide to Elliptic Curve Cryptography*, by Hankerson, Menezes and Vanstone. He found a PDF on a Russian website. — David Grayson, Feb 02 '15 at 23:55
I've actually read that book and those particular pages multiple times and couldn't figure it out. — Jimmy Song, Feb 02 '15 at 23:57

morsecoder · Accepted Answer · 2015-02-03T05:17:19.797

With a bit of reverse engineering, I think I was able to see how Hal was able to get to these results.

First, it's a pretty well known result of Fermat's little theorem that if p is a prime number and g is a generator for the field Z/pZ, then:

g ^ (p - 1) = 1

Note, don't confuse this abstract generator g with the generator for the secp256k1 group G. Now, given the above equation, it's not a big leap to see that:

(g ^ ((p - 1)/3)^3 = g ^ (p - 1) = 1

Thus, we can find λ and β by first finding generators for Z/NZ and Z/PZ (N and P being the parameters given in the original question), and then raising them to the (N-1)/3 and (P-1)/3 powers, respectively. You can check that both N-1 and P-1 are divisible by 3.

The generator that it seems Hal used for λ is 3, and for β is 2. I'm not sure why he picked those, there are plenty of other good generators to choose from. It was probably on a trial and error basis.

Using sage mathematics notebook, I was able to produce the same values for λ and β.

enter image description here

lambda and beta are non-trivial cube roots of 1 in the respective fields (mod n for lambda, mod p for beta). There are only two such values. Starting from a generator g and raising to the power (n-1)/3 resp. (p-1)/3 to find them is just one way of doing so. And it doesn't matter which g one starts with, one always finds one of the two valid solutions, or 1 (if the g started from wasn't a generator, but a cube). — Pieter Wuille, Aug 18 '22 at 02:14

score 2 · Answer 2 · edited Jun 16 '20 at 11:10

Quoting cryptography.stackexchange.com:

Given that N and P are prime, one obvious way to do this is to select a random value g from [1,N−1], and compute g^((N−1)/3) mod N; assuming that N≡1(mod 3), this resulting value will either be 1, the displayed value of λ, or N−λ−1 (with equal probabilities of each). If N≢1(mod 3), then the only modular cube root of 1 will be 1.

And, to compute β, you do the same with P.

The reason this works is due to Fermat's little theorem which states:

g^(N-1) ≡ 1 (mod N)

which implies

(g^((N-1)/3))^3 ≡ 1 (mod N)

which implies

g^((N-1)/3) is our potential λ. If it's not 1, it'll work for the purposes of endomorphism.

I'm in the middle of writing the same thing up, basically, but with some more concrete numbers. :/ — morsecoder, Feb 03 '15 at 04:56

score 0 · Answer 3 · edited Jun 16 '20 at 11:10

Python code to get beta and lambda values for p and n of secp256k1 curve

Getting beta of p

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
print "beta of p = 0x%x" % pow(2, (p-1)/3, p)

beta of p = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

Getting lambda of n

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
print "lambda of n = 0x%x" % pow(3, (n-1)/3 , n)

lambda of n = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

More info

I experimented further with this by getting beta and lambda for both p and n and discovered that all the results generated become useful for finding the identical values for x or y in the equation y ^ 2 = x ^ 3 + 7 mod p

#beta and lambda for p
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
betaOfP = pow(2, (p-1)/3, p)
lambdaOfP = pow(3, (p-1)/3, p)
print "betaOfP \t= 0x%x " % betaOfP 
print "lambdaOfP\t= 0x%x " % lambdaOfP 
print

#beta and lambda for n
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
betaOfN = pow(2, (n-1)/3 , n)
lambdaOfN = pow(3, (n-1)/3 , n)
print "betaOfN \t= 0x%x" % betaOfN
print "lambdaOfN\t= 0x%x" % lambdaOfN

betaOfP = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee lambdaOfP = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40

betaOfN = 0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce lambdaOfN = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

How do you derive the lambda and beta values for endomorphism on the secp256k1 curve?

3 Answers3

Linked