# Calculate a base point on the twist of secp192k1 with maximal order

I want to calculate a base point on the twist of secp192k1 with maximal order.

'secp192k1': _ECData(
p=2**192 - 2**32 - 2**12 - 2**8 - 2**7 - 2**6 - 2**3 - 1,
a=0, b=3,
Gx=0xDB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D,
Gy=0x9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D,

n=0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D

• Comments are not for extended discussion; this conversation has been moved to chat. Commented Jul 31, 2020 at 17:13

## 1 Answer

Let $$\beta$$ a non-square element in $$\mathbf{F}_p$$, then the elliptic curve defined by $$\beta y^2 = x^3 + 3$$ is a quadratic twist of secp192k1 whose equation is $$y^2 = x^3 + 3$$.

It means that if $$x_0^3 + 3$$ is a square, there exists $$y_0 \in \mathbf{F}_p$$ that is a square root of $$x_0^3 + 3$$, so $$(x_0, y_0)$$ belongs to secp192k1, and on the other hand if $$x_0^3 + 3$$ is not a square, there exists $$y_0$$ such that $$\beta y_0^2 = x_0^3 + 3$$, so $$(x_0, y_0)$$ lies on the quadratic twist instead. Here, we can take $$\beta = -1$$ since it is not a square in the finite field $$\mathbf{F}_p$$.

There is a relation between the cardinality (number of points) with the quadratic twist. The cardinality of secp192k1 is a prime number $$n$$, that can be rewritten as $$n = p + 1 - t,$$ where the value $$t$$ is called the trace of Frobenius. Then it is easy to compute the cardinality $$n'$$ of the quadratic twist: \begin{align} n' & = p + 1 + t, \\ & = 3 \cdot 373 \cdot 56383 \cdot 619124299 \cdot 160695254510139039862526647837522958722153. \end{align} Write $$n'= h\cdot q$$ where $$q$$ is the largest prime in the decomposition. The goal is to find a point of order $$q$$ on the twist. Let's use SageMath for the computation, but unfortunately it does not handle elliptic curves with an equation of the form $$-y^2 = x^3 + 3$$. That's not a problem, a simple change of variable will do the trick: let $$x'=-x$$, and the equation becomes $$-y^2 = -x'^3 + 3$$, and by multiplying each side by $$-1$$ we get $$y^2 = x'^3 - 3$$.

We can make some check that all is good:

p = 2**192 - 2**32 - 2**12 - 2**8 - 2**7 - 2**6 - 2**3 - 1
E = EllipticCurve(GF(p), [0, 3])
n = E.cardinality()
print(n.is_prime())
t = p + 1 - n
Et = EllipticCurve(GF(p), [0, -3])
nn = Et.cardinality()
print(nn == p + 1 + t)
print(Et.is_quadratic_twist(E))


The last command returns a nonzero value if the two curves are indeed a quadratic twist of each other.

To find a point whose order is the largest prime $$q$$, we can run something similar as in this post.

1. Generate a random point on the twist;
2. Compute $$Q = [h]P$$;
3. If $$Q \neq \mathcal{O}$$, then $$Q$$ is a point of order $$q$$.
h = 39062147507228523
q = 160695254510139039862526647837522958722153
while True:
P = Et.random_element()
Q = h*P
if Q != Et(0):
break
print(Q)
print(Q.order() == q)

• The relation of the cardinality of of a Curve and it's quadratic twist over a finite field can be better explained as either the $y$ is a quadratic residue or a non-quadratic residue. So the curve and the twist contains exactly two points $(x,y_i)$ for $x\in F_p$. So in total, it makes $2q+2$ with the point of infinity counted twice. Now we can use the trace of the Frobenius. Commented Jul 31, 2020 at 10:53