When looking for efficiently-computable endomorphisms, let's consider all functions of the form:
f(x, y) = (beta * x, y) [in Z/pZ]
with the property that they map points on the curve to a fixed multiple of themselves, so
f(x, y) = lambda * (x,y) [EC group]
for some constants beta (in Z/pZ) and lambda (in Z/nZ).
Now consider repeated application of f. The function f^j is j invocations of f. So
f^0(x, y) = (x, y)
f^j(x, y) = f(f^{j-1}(x, y))
Substituting the definitions above, we get:
f_j(x, y) = (beta^j * x, y)
f_j(x, y) = lambda^j * (x, y)
Now we can wonder, what is the smallest non-zero value of j for which f_j is the identity. Let's call that value q. So f_q(x, y) = (x, y), and thus:
f_q(x, y) = (beta^q * x, y) = (x, y)
f_q(x, y) = lambda^q * (x, y) = (x, y)
In other words, q is the smallest power of beta such that beta^q = 1 (in Z/pZ). Alternatively, it is also the smallest power of lambda such that lambda^q = 1 (in Z/nZ). These two definitions must match, because if one yields the identity, so must the other.
For the GLV endomorphism, q=3, but let's not restrict ourselves to this.
Restating the relation above, q is both the order of beta in the multiplicative group of Z/pZ, and the order of lambda in the multiplicative group of Z/nZ. The order of an element in a finite group always divides the order of the group. The orders of these groups are:
factor(p - 1) = 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
factor(n - 1) = 2^6 * 3 * 149 * 631 * 107361793816595537 * 174723607534414371449 * 341948486974166000522343609283189
Since q needs to divide the order of both, it needs to divide the GCD of n-1 and p-1, which is 6. In other words, q is 1, 2, 3, or 6.
q=1 is simple. That's just beta=1 and lambda=1, and f is the identity itself.
q=2 and q=6 don't exist, at least not with an f of this form, but see further.
q=3 is the GLV endormorphism, and it can only exist in curves which have n mod 3 = 2, and p mod 3 = 2, like secp256k1. Now to answer your real question: how do we find lambda and beta?
lambda and beta must be elements of order 3 in the multiplicative groups of Z/nZ and Z/pZ. There are exactly 2 of those, in each: the non-trivial cube roots of 1 in those fields. If you have one, the square is a solution too.
The approach will be: first find a solution to lambda, then observe what lambda*(x, y) is for a random point (x, y), and see what beta factor for x it yields. That beta will necessarily have to be a cube root of 1.
A way of finding such a cube root of 1 is starting with a generator g - any generator - of the multiplicative group of Z/nZ, and raising it to the power lambda=g^((n-1)/3). This is necessarily a cube root of 1, as lambda^3 = g^(n-1), which is 1 by Fermat's Little Theorem.
It really doesn't matter which value is picked for g, actually, as long as it is not a cube. Specifically, it does not need to be 2 or 3. Depending on which g you start with, you can obtain:
- g=0 obviously yields g^((n-1)/3) = 0, which is not a non-trivial cube root of 1.
- if g is a cube, then g^((n-1)/3) = 1, which is also not good. This is the case for 1/3 of non-zero field elements.
- otherwise, g^((n-1)/3) will equal one of the two non-trivial cube roots of 1, a valid choice for lambda.
Since there are two non-trivial solutions to lambda, you will end with either one: either the one Hal Finney found and is used in libsecp256k1, or its square.
So to be clear: g does not need to be 2 or 3. A majority of field elements work. It's just a way of finding solutions to lambda^3 = 1.
Back to q being 2 or 6. This isn't possible with f(x, y) = (beta * x, y), but q=2 is possible with f(x, y) = (x, gamma * y). The exact same reasoning applies otherwise. And now we need a lambda that is a non-trivial square root of 1. There is only one such number: lambda=-1 (which is equal to n-1 in Z/nZ), with corresponding gamma=-1. And this is the well-known elliptic curve negation formula: -(x, y) = (x, -y).
Composing these two endomorphisms, one gets an order q=6 one: f(x, y) = (beta * x, -y) = -lambda * (x, y).
