A property of some Koblitz elliptic curves over a prime field

Question

secp256k1 is an elliptic curve $E$ over a prime field $\mathbb F_p$, of equation $y^2\equiv x^3+b\pmod p$, with prime order $n$.

I noticed† that the different curve $E'$ over the prime field $\mathbb F_n$ with the same equation has order $p$. The roles of $p$ and $n$ are reversed in $E$ and $E'$.

That also holds for secp160k1 (not secp224k1 or secp192k1), and it's easy to come with other examples small (e.g. $p=13$, $b=2$, $n=19$) or large (e.g. $p=2^{256}-1539$, $b=11$, $n=2^{256}-349115002089537994600663805616504561333$).

Why is that? Has this been studied? Is there any application, perhaps in pairings?

Possibly related: what's a method to quickly compute the order of a Koblitz curve over a prime field, like the one used in Sagemath's EllipticCurve.cardinality() ?

---

† when trying to figure out the purpose of code posted in a comment.

Answer 1

The magic here is in curves with complex multiplication. It's easiest to see in the secp256k1 case where the complex multiplication uses $\mathbb Q(\sqrt{-3})$. This is due to the endomorphism $$(x,y)\mapsto (\omega x,y)$$ where $\omega$ is a cube root of unit such as $(1+\sqrt 3)/2$. All elliptic curves over prime fields can be thought of as being reductions of curves with complex multiplication using a particular quadratic field where the prime splits into principal ideals.

The number of points on a curve over a prime field is strongly related to its complex multiplication structure. If the discriminant of the field is $-\Delta$ (so $\Delta=3$ in the secp256k case) then the splitting of the primes tells us that either $p$ (in the case $\Delta\equiv 1,2\pmod 4$) or $4p$ (in the case $\Delta\equiv 3\pmod 4$) can be uniquely written in the form $x^2+\Delta y^2$. The magic of complex multiplication and the trace of Frobenius then says (see e.g. section 18.1.5 of The Handbook Elliptic and Hyperelliptic Curve Cryptography) that our elliptic curve and its twist respectively have either $p+1\pm 2x$ points (in the case $\Delta\equiv 1,2\pmod 4$) or $p+1\pm x$ points (in the case $\Delta\equiv 3\pmod 4$), using the same value of $x$.

We can check this for secp256k1 where

4p=432420386565659656852420866390673177327^2+3*303414439467246543595250775667605759171^2

and

n=p+1-432420386565659656852420866390673177327

Now consider the case when $n$ is itself prime and the $x$ value is subtracted (I'll only deal with the case where $\Delta\equiv 3\pmod 4$, but the other cases are easy enough). We have $n=p+1-x$ so that $$4n=4p+4- 4x=x^2+\Delta y^2+4-4x=(x- 2)^2+\Delta y^2,$$ so that $n$ is a prime that splits into principal ideas in $\mathbb Q(\sqrt{-\Delta})$ and the number of points on our CM curve or its twist over the field with $n$ elements will be $n+1+(x- 2)$. Now note that $$4(n+1+(x-2))=(x- 2)^2+\Delta y^2+ (4x-4)=x^2+\Delta y^2=4p$$ so that our curve has $p$ points.

Tricks like these allow us to construct curves with prescribed numbers of points and are critical for constructing curves with small embedding degrees in pairing-based cryptography. This is why so many pairing-based curves are either of the form $y^2=x^3+b$ (which has CM by $\sqrt{-3}$) or $y^2=x^3+ax$ (which has CM by $i$).