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.

  • $\begingroup$ huh, I'm not quite sure I know what a projective point over a ring means. Can you clarify how is $E(\Bbb Z/15 \Bbb Z)$ defined ? $\endgroup$ – mercio Apr 28 '15 at 8:07
  • $\begingroup$ I took it to be solutions to the following equation $y^2z=x^3+axz^2+bz^3\pmod{15}$ and not including $[0:0:0]$. "We define a natural group law on such curves ($E(\mathbb{Z}/N\mathbb{Z})$), although one usually gives these in terms of projective coordinates so as to cope with the occurrence of zero divisors." $\endgroup$ – BlackAdder Apr 28 '15 at 8:11
  • $\begingroup$ If anything it should be the triplets that are coprime (not all multiples of 3 or 5), quotiented by multiplication by the invertibles of Z/15Z. Also E(F5) has 9 elements and not 16. $\endgroup$ – mercio Apr 28 '15 at 8:22
  • $\begingroup$ But $[0:2:3]$ is a projective point in $E(\mathbb{F}_5)$ and not equal to any of the affine points nor the identity. I'm not really sure what to make of the projective points to be honest. What would you do with the point $[0:0:3]$? Thanks for your input so far by the way. $\endgroup$ – BlackAdder Apr 28 '15 at 8:46
  • $\begingroup$ remember that you can multiply projective coordinates by any invertible element so $[0:2:3] = [0:4:1]$ and $[0:0:3] = [0:0:1]$ $\endgroup$ – mercio Apr 28 '15 at 9:17

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

  • 1
    $\begingroup$ Hey, thanks for your input. I've changed the question so that the curves are now non-singular. We have elliptic curves mod a composite number because this is looking at ECM, where we are factoring $N$. Lastly, I would think that $E$ should remain the same in some sense, else, it would look like one could choose the group then construct the curve and it'll be trivially true. $\endgroup$ – BlackAdder Apr 28 '15 at 5:52

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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