<p>When looking for efficiently-computable endomorphisms, let's consider all functions of the form:</p>
<pre><code>f(x, y) = (beta * x, y) [in Z/pZ]
</code></pre>
<p>with the property that they map points on the curve to a fixed multiple of themselves, so</p>
<pre><code>f(x, y) = lambda * (x,y) [EC group]
</code></pre>
<p>for some constants beta (in Z/pZ) and lambda (in Z/nZ).</p>
<p>Now consider repeated application of f. The function f^j is j invocations of f. So</p>
<pre><code>f^0(x, y) = (x, y)
f^j(x, y) = f(f^{j-1}(x, y))
</code></pre>
<p>Substituting the definitions above, we get:</p>
<pre><code>f_j(x, y) = (beta^j * x, y)
f_j(x, y) = lambda^j * (x, y)
</code></pre>
<p>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:</p>
<pre><code>f_q(x, y) = (beta^q * x, y) = (x, y)
f_q(x, y) = lambda^q * (x, y) = (x, y)
</code></pre>
<p>In other words, q is the smallest power of beta such that <code>beta^q = 1</code> (in Z/pZ). Alternatively, it is also the smallest power of lambda such that <code>lambda^q = 1</code> (in Z/nZ). These two definitions must match, because if one yields the identity, so must the other.</p>
<p>For the GLV endomorphism, q=3, but let's not restrict ourselves to this.</p>
<p>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:</p>
<pre><code>factor(p - 1) = 2 * 3 * 7 * 13441 * 205115282021455665897114700593932402728804164701536103180137503955397371
factor(n - 1) = 2^6 * 3 * 149 * 631 * 107361793816595537 * 174723607534414371449 * 341948486974166000522343609283189
</code></pre>
<hr />
<p>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.</p>
<p>q=1 is simple. That's just beta=1 and lambda=1, and f is the identity itself.</p>
<p>q=2 and q=6 don't exist, at least not with an f of this form, but see further.</p>
<p>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?</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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:</p>
<ul>
<li>g=0 obviously yields g^((n-1)/3) = 0, which is not a non-trivial cube root of 1.</li>
<li>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.</li>
<li>otherwise, g^((n-1)/3) will equal one of the two non-trivial cube roots of 1, a valid choice for lambda.</li>
</ul>
<p>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.</p>
<p>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 <code>lambda^3 = 1</code>.</p>
<hr />
<p>Back to q being 2 or 6. This isn't possible with <code>f(x, y) = (beta * x, y)</code>, but q=2 is possible with <code>f(x, y) = (x, gamma * y)</code>. 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: <code>-(x, y) = (x, -y)</code>.</p>
<p>Composing these two endomorphisms, one gets an order q=6 one: <code>f(x, y) = (beta * x, -y) = -lambda * (x, y)</code>.</p>

CC BY-SA 4.0
2022-08-25T21:15:55.340Z
q=2 and q=6 don't exist, at least not with an f of this form. can u please explain this.?
on the curve the following is true: 2 Privet key equal 1 X . The inverse Y is equal to second PKey times (N-1), also Consecutive privKeys move in geometric progression.
 And it is always increasing from 1 to (N-1)/2. 
the details are in scalar number. it must be a way to reverse the path from X coordinate to private Key via relationship between N and P.
 also curve is half , X point doubled, total y1+y=P or P=N+trace.
the rings will be  N ,2N, and in EC will be P or 2P
tony pham
CC BY-SA 4.0
2022-08-25T21:21:17.580Z
There exist no endomorphisms of the elliptic curve with order 2 or 6 of the form `(x,y)->(a*x,y)`, for any value of a. There however an order 2 one of the form `(x,y)->(x,-y)` namely point negation. And there is an order 6 one of the form `(x,y)->(beta*x,-y)` (the composition of the GLV endormorphism of order 3, and point negation of order 2). I don't understand anything else of what you're saying. Consecutive private keys do not move in a geometric progression, they are just numbers in range 1...N-1.
Pieter Wuille
CC BY-SA 4.0
2022-08-18T00:11:19.557Z
2022-08-18T01:01:06.837Z
2022-08-18T01:01:06.837Z
Pieter Wuille
<p>As you can seen here, in hex, N and P are:</p>
<p>N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141</p>
<p>P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F</p>
<p>The actual values of lambda and beta are easily verifiable and are:</p>
<p>λ = 5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72</p>
<p>β = 7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee</p>
<p>λ2=AC9C52B33FA3CF1F5AD9E3FD77ED9BA4A880B9FC8EC739C2E0CFC810B51283CF</p>
<p>β2=851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40</p>
<p>From Fermat's little theorem, if p is a prime number and g is a generator for the field Z/pZ,
Z/nZ then:</p>
<pre><code>(g ^ ((p - 1)/3)^3 = g ^ (p - 1) = 1
(g ^ ((N - 1)/3)^3 = g ^ (N - 1) = 1
</code></pre>
<p>β2 and λ2 can be generated by switching 2 and 3 in the equation, so we can generate 6 set of privet/public that group up in 3 rings.</p>
<p>Can some one explain why g choose to be 2 and 3?</p>
<p>what is the relation between 2 groups generated from λ which are <code>(pvk, N-pvk)  </code>with each to be equal to N and 2N, and a group generated from β, which is  <code>(X coordinates)</code>
that sum of it be equal to P or 2P ?</p>
<p>Prime Curve (p), Prime Multiplier (N), Trace (P−N), Curve is Half. Multipliers (M1+M2)=N, y Coordinates + Inverse Y Coordinate = P.</p>
<p>6 Pubkeys are</p>
<pre><code> Pubkey = [x,y]  [x*beta%p, y]  [x*beta2%p, y] [x,p-y]  [x*beta%p, p-y]  [x*beta2%p, p-y]
</code></pre>
<p>6 Privatekeys are</p>
<pre><code>pvk, pvk*lmda%N, pvk*lmda2%N, N-pvk, N-pvk*lmda%N, N-pvk*lmda2%N
</code></pre>
<p>is that possible to  find the relation using mod <code>((N-1)+(P-1))/2</code>?</p>
<p>There must be a third value such as λ and β to connect the abelian groups.</p>

<cryptography><ecdsa><secp256k1>
Why g is 2 and 3 to derive the lambda and beta values for endomorphism on the secp256k1 curve?
tony pham
# Why g is 2 and 3 to derive the lambda and beta values for endomorphism on the secp256k1 curve?

(Asked by: username_0 on 2022-08-17)

As you can 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

λ2=AC9C52B33FA3CF1F5AD9E3FD77ED9BA4A880B9FC8EC739C2E0CFC810B51283CF

β2=851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40

From Fermat's little theorem, if p is a prime number and g is a generator for the field Z/pZ,
Z/nZ then:

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

```

β2 and λ2 can be generated by switching 2 and 3 in the equation, so we can generate 6 set of privet/public that group up in 3 rings.

Can some one explain why g choose to be 2 and 3?

what is the relation between 2 groups generated from λ which are `(pvk, N-pvk)` with each to be equal to N and 2N, and a group generated from β, which is `(X coordinates)`
that sum of it be equal to P or 2P ?

Prime Curve (p), Prime Multiplier (N), Trace (P−N), Curve is Half. Multipliers (M1+M2)=N, y Coordinates + Inverse Y Coordinate = P.

6 Pubkeys are

```
 Pubkey = [x,y]  [x*beta%p, y]  [x*beta2%p, y] [x,p-y]  [x*beta%p, p-y]  [x*beta2%p, p-y]

```

6 Privatekeys are

```
pvk, pvk*lmda%N, pvk*lmda2%N, N-pvk, N-pvk*lmda%N, N-pvk*lmda2%N

```

is that possible to find the relation using mod `((N-1)+(P-1))/2`?

There must be a third value such as λ and β to connect the abelian groups.

**Tags:** cryptography, ecdsa, secp256k1


---

## 1 answers

### Answer by username_1 on 2022-08-18. Score: 1

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)`.

> **Comments:**
> **username_0**: q=2 and q=6 don't exist, at least not with an f of this form. can u please explain this.? on the curve the following is true: 2 Privet key equal 1 X . The inverse Y is equal to second PKey times (N-1), also Consecutive privKeys move in geometric progression.  And it is always increasing from 1 to (N-1)/2.  the details are in scalar number. it must be a way to reverse the path from X coordinate to private Key via relationship between N and P.  also curve is half , X point doubled, total y1+y=P or P=N+trace. the rings will be  N ,2N, and in EC will be P or 2P  
> **username_1**: There exist no endomorphisms of the elliptic curve with order 2 or 6 of the form `(x,y)->(a*x,y)`, for any value of a. There however an order 2 one of the form `(x,y)->(x,-y)` namely point negation. And there is an order 6 one of the form `(x,y)->(beta*x,-y)` (the composition of the GLV endormorphism of order 3, and point negation of order 2). I don't understand anything else of what you're saying. Consecutive private keys do not move in a geometric progression, they are just numbers in range 1...N-1.  

---

