Chinese Remainder theorem on Elliptic Curve group

Question

I read somewhere (Blake, Seroussi, Smart: Elliptic Curves in Cryptography, p.160) that one can use the Chinese Remainder theorem to split $E(\mathbb{Z}/N\mathbb{Z})$, where $N$ is a composite number. Let me set up the question:

Let $N=pq$, where $p$, $q$ are primes. Now, consider the ring $\mathbb{Z}/N\mathbb{Z}$. If $E$ is an elliptic curve, then I would like to show that

• there is a group law on $E(\mathbb{Z}/N\mathbb{Z})$;
• $E(\mathbb{Z}/N\mathbb{Z})\cong E(\mathbb{F}_p)\times E(\mathbb{F}_q)$.

I've tried the following example to no avail:

• $E:y^2=x^3+x+1\pmod{3}$, then $E(\mathbb{F}_3)=\{\mathcal{O},(1,0),(0,\pm1)\}$
• $E:y^2=x^3+x+1\pmod{5}$, then $E(\mathbb{F}_5)=\{\mathcal{O},(0,\pm1),(2,\pm1),(3,\pm1),(4,\pm1)\}$
• $E:y^2=x^3+x+1\pmod{15}$, then $E(\mathbb{Z}/15\mathbb{Z})=\{\mathcal{O},(0,\pm1),(0,\pm4),(3,\pm1),(3,\pm4),(4,\pm3),(7,\pm6),(9,\pm2),(9,\pm7),(10,\pm6),(12,\pm4),(12,\pm1),(13,\pm6)\}$.

Looking at the order, one can tell that $E(\mathbb{Z}/15\mathbb{Z})\not\cong E(\mathbb{F}_3)\times E(\mathbb{F}_5)$.

I've computed the points by solving $y$ given $x$. Is that the right way to find points in $E(\mathbb{Z}/15\mathbb{Z})$? Where have I gone wrong? Perhaps not counting all the projective points.

Answer 1

Your computations look fine. I haven't seen elliptic curves modulo a composite number in cryptography before, but I am not an expert in this. On the other hand, if you were going to start with the two curves over $\mathbb{F}_p$ and $\mathbb{F}_q$ you'd need the condition $4a^3+27 b^2 \neq 0$ for nonsingularity of $$y^2=x^3+ax+b.$$ This would fail for your example, when $q=3$. Moreover, I am unsure if you'd necessarily have the same equation, i.e, with the same constants $a,b$ for the two curves $E(\mathbb{F}_p)$ and $E(\mathbb{F}_q)$

Answer 2

I have definitely forgotten to count the projective points. But we will get to that later. Firstly, let's prove $E(\mathbb{Z}/N\mathbb{Z})=E(\mathbb{F}_p)\times E(\mathbb{F}_q)$.

Consider the map $$f:E(\mathbb{Z}/N\mathbb{Z})\to E(\mathbb{F}_p)\times E(\mathbb{F}_q)$$ given by $$[x:y:z]\mapsto([\bar{x}_p:\bar{z}_p:\bar{z}_p],[\bar{x}_q:\bar{y}_q:\bar{z}_q]),$$ where $\bar{n}_u\equiv n\pmod{u}$.

Clearly the RHS is in the range because if $[x:y:z]\in E(\mathbb{Z}/N\mathbb{Z})$, then $$y^2z=x^3+axz^2+bz^3\pmod{N}\implies y^2z=x^3+axz^2+bz^3\pmod{p}$$ and likewise $q$.

Now, \begin{align*} &[x:y:z]\mapsto([0:1:0],[0,1,0])\\ \implies &x\equiv0\pmod{p}, x\equiv0\pmod{q}\implies x\equiv0\pmod{N}\\ \implies &y\equiv1\pmod{p}, y\equiv1\pmod{q}\implies y\equiv1\pmod{N}\\ \implies &z\equiv0\pmod{p}, z\equiv0\pmod{q}\implies z\equiv0\pmod{N}. \end{align*} So we have injectivity.

Surjectivity will come from the chinese remainder theorem.

As for the example, we actually have $\#E(\mathbb{F}_3)=4, \#E(\mathbb{F}_5)=16, \#E(\mathbb{Z}/15\mathbb{Z})=128$ after counting projective points.