Chinese Remainder theorem on Elliptic Curve group 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.
 A: 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)$
A: 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.
