2

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.

1 Answer 1

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

2
  • 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
    Aug 25, 2022 at 21:15
  • 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. Aug 25, 2022 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.