2
$\begingroup$

This is regarding finding points along an Elliptic Curve

$y^2 = x^3 + 8x + 1$ Over $\Bbb F_{11}$

In the "Elliptic Curves over Finite Fields" chapter of "Elliptic Curves: Number Theory and Cryptography" by Lawrence C. Washington, all the points along an elliptic curve are found by using a table of all the possible $x$ values in the field (0 and all the positive integers up to $p-1$ where $p$ is the finite field order) and considering which of these values are square numbers.

Here is a picture of the example. To test my understanding, I have carried out a similar process with the Elliptic Curve and Galois Field given at the top.

I found all the points, or so I thought I did. Here are the values I found. I have only included them up to 4, but I have computed all the values elsewhere.

$$\begin{array}{|c|c|c|c|c|c|} \text{$x$} & \text{$x^3+8x+1$ $mod$ $11$} & \text{$y$} & \text{Coordinates $mod$ $11$} \\ \hline \text{0} & 1 & 1,-1 & (0,1), (0,10)\\ \hline \text{1} & 10 & - & - \\ \hline \text{2} & 3 & - & - \\ \hline \text{3} & 8 & - & - \\ \hline \text{4} & 9 & 3,-3 & (4,3), (4,8) \\ \hline \end{array}$$

I hence found all the points with this method. I then added the point $P=(0,1)$ to itself and found that 8P was equal to (2,5). However, in the table above, we saw that when $x=2$, $x^3+8x+1$ mod 11 was equal to 3, which is not a square number, so there would not be a point along the elliptic curve there. Of course, I noticed that $x^3+8x+1$ when $x=2$ was equal to 25, and 25 is a square number, giving $y$ values of 5 and -5.

I am confused as to why we square root 25 before we take the modulus. With the table I followed in Washington, the modulus was taken first and then the result was square rooted.

A similar case arises when $x=8$. Taking the modulus first gives 5, which is not a square number, so this was omitted from the table method. 6P gives a point with $x$-coordinate 8. At $x=8$, $x^3+8x+1=577$, and 577 mod 11 = 5 mod 11 = 16 mod 11. This means that $y$ is 4 or -4 because 16 is a square number.

577 is a less obvious example to spot than 25. How do we know when the number is a square number in the modulus, just by seeing the remainder? Is the best method to simply check if $x+11k$, where k is an integer, is a square number for each value of $x$?

To recap, my main question is, with this table method, how do we find the points along the elliptic curve which have y-coordinates which have a square greater than the order of the field? So, how do we know when $x$ mod p can be rewritten as $a^2$ mod p where a is an integer?

|cite|improve this question
$\endgroup$
  • $\begingroup$ In the field $\Bbb{F}_{11}$ we have $25=3$. Not just congruent - equal! So in $\Bbb{F}_{11}$ we also have $\sqrt3=\pm5$. Also $$5^2\equiv 2^3+8\cdot2+1\pmod{11},$$ so $(x,y)=(2,5)$ is a solution. $\endgroup$ – Jyrki Lahtonen Jun 26 '17 at 16:10
  • $\begingroup$ For the question in the last paragraph you should learn about quadratic residues. In the case of a very small field (such as $\Bbb{F}_{11}$) you can also simply build a list of the squares $0,1,4,9,16=5,25=3=36$. $\endgroup$ – Jyrki Lahtonen Jun 26 '17 at 16:12
  • $\begingroup$ @JyrkiLahtonen, Thank you very much, that cleared it up a lot for me. This was a basic example to understand the process before I implemented a more complex example over a larger finite field. I am looking to find all the points, but I understand that I must know the details of the quadratic residues in the field I am working with to find all of these points. Do you know of any other methods which will allow me to find all the points, without listing out all the squares? $\endgroup$ – Harry Alli Jun 27 '17 at 1:01
  • $\begingroup$ For moderate size $p$ you can do that by integer factoring and applying the law of quadratic reciprocity. For larger $p$ you probably don't want to list the points of an elliptic curve. After all, there are at least $p+1-2\sqrt p$ of them, so if $p$ has 20 digits or so... There are other methods for counting the number of points, but those rely on deeper algebra. They run with a complexity that is something like $\mathcal{O}((\log p)^8)$ (may be the exponent was five, I'm not sure). At least Menezes's book (targeting cryptopeople) explains some but not all of those. $\endgroup$ – Jyrki Lahtonen Jun 27 '17 at 7:21

Your Answer

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

Browse other questions tagged or ask your own question.