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?

$\endgroup$
4
  • $\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, 2017 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, 2017 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, 2017 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, 2017 at 7:21

0

Reset to default

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.