Do the solutions to an elliptic curve over a finite field correspond to solutions over the reals?

222 Views Asked by At

In cryptography, we often deal with elliptic curves defined over a finite field, such as the integers modulo a large prime p. My mental intuition for what this does to the graph of the elliptic curve is that the x- and y-axes “wrap around” at 0 and p and then we consider only points that have exact integer coordinates. To illustrate, I have plotted a graph of $y^2 = x^3 - 3x + 3$ below “modulo” 13 (for a naïve translation of the $\operatorname{mod}$ operation to $\mathbb R$, which I will denote $\mathbb R_{13}$ in what is probably a horrible abuse of notation—I am not a mathematician). The graph plots x from -2.1 to 52.

I have also plotted the actual solutions to the curve equation in GF(13) for comparison. Only some of the points are intersected by the line of the graph over $\mathbb R_{13}$. My intuition is that if I extended the graph over $\mathbb R_{13}$ far enough it would eventually intersect all of the points in GF(13) and that there would be no other solutions where x and y are both integers. Is this intuition correct, or does the definition of square-roots in a finite fields differ sufficiently from that in the reals that this intuition is misleading?

The elliptic curve <span class=$y^2 = x^3 - 3x + 3 drawn wrapping around at 13, with points of solutions in GF(13) also drawn.$" />

1

There are 1 best solutions below

5
On BEST ANSWER

If I were to show this curve in an introductory class, I would use, instead, the modified equation $$ y^2=x^3-16x+16.\qquad(*) $$ The connection with your curve is hopefully clear given that $16\equiv3\pmod{13}$. I simply chose to use $16$ as the rational number lying over $3$. The reason for these choices is that the resulting curve passes through several familiar looking points with integer coordinates, namely $$(-4,\pm4),(0,\pm4),(1,\pm1),(4,\pm4),(8,\pm20)\quad\text{and}\quad(24,\pm116).$$ See the figure below where these points are show as dots (with the exception of the last pair for they were too far out).

All those twelve points show as points on your curve over $GF(13)$ when we reduce the coefficients modulo $13$. For example, the point $(-4,-4)$ corresponds to your point $(9,9)\in GF(13)^2$, and the point $(24,-116)$ to $(11,1)$ as $24\equiv11\pmod{13}$ and $-116\equiv1\pmod{13}$.

This points at a better description of the connection between the two elliptic curves. Points of this curve, call it $E_{\Bbb{R}}$, with integer coordinates become points of your curve, $E_{GF(13)}$, when we reduce the coordinates modulo $p$.

We can extend that reduction mapping to many points of $E_{\Bbb{R}}$ with rational coordinates. Using the chord-tangent -method we easily find that the point $Q=(161/4,-2033/8)$ is also on the curve $E_{\Bbb{R}}$. As neither denominator is a multiple of $13$, we can interpret those coordinates as elements of $GF(13)$. After all, in $GF(13)$ we have $\overline{4}\cdot\overline{10}=\overline{1}$ as well as $\overline{8}\cdot\overline{5}=\overline{1}$. So division by four can also be realized as multiplication by ten et cetera. Here $$ \overline{161}/\overline{4}=\overline{5}\cdot\overline{10}=\overline{11} $$ and $$ \overline{-2033}/\overline{8}=\overline{8}/\overline{8}=\overline{1}. $$ Therefore the point $Q$ also becomes $(\overline{11},\overline{1})$.

We encountered a phenomenon that several points with rational coordinates may become the same point when reduced modulo $p$. This always happens, if $E_{\Bbb{R}}$ has infinitely many points with rational coordinates, but that it is a more difficult question (above my paygrade to be honest).

Observe that we have noe seen the points $(5,\pm3)\in E_{GF(13)}$ as reductions at all. I don't know if they appear at all? I didn't produce too many points with rational coordinates, and I don't know whether it is gotten in the same way. Sometimes there are points of $E_{GF(p)}$ that don't come from any point on $E_{\Bbb{Q}}$. That is because some elliptic curves have very few points over $\Bbb{Q}$. Those are, again, a bit deeper questions in number theory.

Instead, I use $(5,\pm3)$ to demonstrate a different aspect of the "reduction modulo $p$" -business. We can plug in $x=5$ into $(*)$. When we do that we see that complex points $(5,\pm\sqrt{61})$ satisfy the equation $(*)$. It happens that $$61\equiv9=3^2\pmod{13}.$$ This means that, in the field $GF(13)$ we can think of $\overline{3}$ as $\sqrt{61}$. This kind of points of $E_{\Bbb{R}}$ with square roots in their coordinates then "cover" the points that were missed out by those with rational or integer coordinates.

A summary:

There is natural mapping from $E_{\Bbb{Q}}$ to $E_{GF(p)}$. How well a curve "lifted" to reals (or, more naturally, rationals) in this way covers the points over a finite field is a more difficult question. It may miss many points of $E_{GF(p)}$ altogether. Or it can be a (infinitely) many-to-1 relation. The details of the lifting process may become hairy, and there are related, deep open questions.