Combine two given Elliptic Curves

Question

I want to combine two Elliptic curves such $E_p$ (defined in the field $F_p$) and $E_q$ (defined in the field $F_q$) i.e to find $E_n$ where $n=pq$. Is there any method to do it?

Answer 1

Here is a concrete example. Let $E_5: y^2 = x^3+1$, defined over $\mathbb{F}_5$, and let $E_7: y^2=x^3+2x+3$ defined over $\mathbb{F}_7$. We want to find an elliptic curve $E/\mathbb{Q} : y^2=x^3+Ax+B$, with $A,B\in \mathbb{Z}$ such that $E\equiv E_5 \bmod 5$ and $E\equiv E_7 \bmod 7$. It suffices to find integers $A$ and $B$ such that $$\begin{cases}A\equiv 0\bmod 5,\\ A\equiv 2\bmod 7\end{cases},\quad \text{ and }\quad \begin{cases}B\equiv 1\bmod 5,\\ B\equiv 3\bmod 7\end{cases}.$$ The solutions of these congruences are $$A\equiv 30 \bmod 35, \quad \text{ and } \quad B\equiv 31 \bmod 35,$$ so we can pick $A=30$ and $B=31$, and the curve we are looking for is $$E: y^2=x^3+30x+31$$ whose discriminant is $\Delta=-2143152= -2^4\cdot 3^3\cdot 11^2\cdot 41\neq 0$, so $E$ is non-singular, and by construction, $E\equiv E_5 \bmod 5$ and $E\equiv E_7 \bmod 7$.

Answer 2

I assume you want to construct $E ~ \colon \quad y^2+a_1 xy + a_3 y=x^3 + a_2x^2+a_4x+a_6$ modulo $pq$ so that modulo $p$ the $a_i$ coefficients are the same as those of $E_p$ and modulo $q$ as those of $E_q$. This is possible by using the Chinese Remainder theorem to (uniquely) determine each coefficient. Of course, curves with the same coefficients mod $p$ will have the same points mod $p$.

But I think most people will agree that this construction isn't mathematically interesting.

Answer 3

Chinese remainder theorem is the way to understand elliptic curves (mod n). You have to be careful about points that are infinity mod p but not mod q.

Such curves have been used for some crypto applications. See:

• N. Demytko, A New Elliptic Curve Based Analogue of RSA, EUROCRYPT 1993, 40-49.
• S. Galbraith, Elliptic curve Paillier schemes, Journal of Cryptology, Vol. 15, No. 2 (2002) 129-138.