Points on elliptic curve over finite field

Question

Find the points on the elliptic curve $y^2 = x^3 + 2x + 2$ in $\mathbb F_{17}$.

Do I have to guess a first point and then use an algorithm to spit out all other points?

Answer 1

One approach (see Example $15.5$ at Elliptic Curve Cryptography), is the following.

Take $x = 0 \ldots 16$ and for each $x$ solve: $$y^2 = x^3 + 2x + 2 \pmod {17}$$

This yields the following sets of points:

• $x = 0, 7, 10, y = 6, 11$
• $x = 3, 5, 9, y = 1, 16$
• $x = 6, y = 3, 14$
• $x = 13, y = 7, 10$
• $x = 16, y = 4, 13$

You can use Hasse's Theorem to quickly bound the number of points over $\mathbb{F}_{q}$, where $q = 17$ in your example and is given by:

$$q + 1 - 2 \sqrt{q} \le \#E(\mathbb{F}_q) \le q + 1 + 2 \sqrt{q}$$

You can also look into Point Counting Algorithms to determine the actual number of points on the curve.

Answer 2

This Matlab script

disp('***** y^2 = x^3 + ax + b mod p *****');
n=input('insert prime p: ');
a=input('insert coefficient a: ');
b=input('insert coefficient b: ');
x=[0:n-1];
y=[0:n-1];
figure
for i=1:n
    for j=1:n
        if rem(((y(j))^2)-((x(i))^3)-a*(x(i))-b,n)==0
            plot(x(i),y(j),'r o');
            hold on;
        end
    end
end
grid;
hold off;

may help you. In this specific case ($p=17$, $a=b=2$), it would plot the following:

This agrees with the result posted by @Amzoti and the script shows an algorithm for the purpose.