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

Question

Note: This question was reposted from Bitcoin Stack Exchange, where it received alike answers.

---

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 such that: $$\begin{align} \lambda^3 &= 1 \mod N \\ \beta^3 &= 1 \mod P \\ \end{align}$$

As seen here, in hex, $N$ and $P$ are: $$\begin{align} N &= \mathtt{FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFE\ BAAEDCE6\ AF48A03B\ BFD25E8C\ D0364141} \\ P &= \mathtt{FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFE\ FFFFFC2F} \\ \end{align}$$

The actual values of lambda and beta are easily verifiable and are: $$\begin{align} \lambda &= \mathtt{5363ad4c\ c05c30e0\ a5261c02\ 8812645a\ 122e22ea\ 20816678\ df02967c\ 1b23bd72} \\ \beta &= \mathtt{7ae96a2b\ 657c0710\ 6e64479e\ ac3434e9\ 9cf04975\ 12f58995\ c1396c28\ 719501ee} \\ \end{align}$$

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

Answer 1

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} \bmod N$; assuming that $N \equiv 1 \pmod{3}$, this resulting value will either be 1, the displayed value of $\lambda$, or $N-\lambda-1$ (with equal probabilities of each). If $N \not\equiv 1 \pmod{3}$, then the only modular cube root of 1 will be 1.

And, to compute $\beta$, you do the same with $P$.

Answer 2

Steps for calculating beta of P

• Get ⅓ of P-1
• Calculate 2^[⅓ of P-1] mod P

Example Python Code

#method for calculating beta of p
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
print hex(p)
#get ⅓ of p-1
thirdOfPm1 = (p-1)/3
print hex(thirdOfPm1 )
#calculate 2^thirdOfPm1 mod p
beta = pow(2, thirdOfPm1, p)
print hex(beta)

0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2fL 0x55555555555555555555555555555555555555555555555555555554fffffebaL 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501eeL

---

Steps for calculating lambda of N

• Get ⅓ of N-1
• Calculate 3^[⅓ of N-1] mod N

Example Python Code

#method for calculating lambda of n
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
print hex(n)
#get ⅓ of n-1
thirdOfNm1 = (n-1)/3
print hex(thirdOfNm1)
#calculate 3^thirdOfNm1 mod n
lmbda = pow(3, thirdOfNm1, n)
print hex(lmbda)

0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141L 0x55555555555555555555555555555554e8e4f44ce51835693ff0ca2ef01215c0L 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72L

---

more info

The above method demonstrates getting beta and lambda for the parameters used in secp256k1. I applied the same method for the parameters used in curve secp192k1 and also got these results.

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37
beta = 0x447a96e6c647963e2f7809feaab46947f34b0aa3ca0bba74L

n = 0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D
lambda = 0x3d84f26c12238d7b4f3d516613c1759033b1a5800175d0b1L