Finding all Points on a Edwards curve

Question

I need to find all affine points on the Edwards curve:
$x^2 + y^2 = 1 - 5x^2y^2$ over $F_{13}$
I tackle this by transforming the equation to:
$y^2 = \frac{1-x^2}{1+5x^2}$
I then go from x = 0 to $\frac{p-1}{2}$ in this case x from 0 to 6.
If you can take the square root of $y^2$ you found a point. If you have a match you will find 4 points because of the symmetry of this equation. (x,y)(x,-y)(-x,y)(-x,-y).
I managed to find these points: (0,1)(0,12)(6,3)(6,10)(7,3)(7,10)(12,0)
However my computer algorithm says I'm missing the following points (3,6)(3,7)(10,6)(10,7). Simply put I'm missing x = 3.
This is my calculation of x = 3:
$y^2 = \frac{1-3^2}{1+5*3^2} = \frac{-8}{46} = \frac{5}{7} \rightarrow 5 * 7^{-1} \mod{13} \equiv 10$
however the square root of 10 isn't an integer. Could anyone answer my question?

Answer 1

The congruence class of $10$ is a square in $\mathbb{F}_{13}$. Indeed, $$6^2\equiv 36\equiv 10 \bmod 13$$ and similarly $(-6)^2\equiv 7^2\equiv 49\equiv 10\bmod 13$. Thus, for $x\equiv 3$ and $-3\equiv 10\bmod 13$, there are two possibilities for $y$, namely $6$ and $7\bmod 13$.

Notice that your algorithm could have run into trouble if $1+5x^2\equiv 0 \bmod 13$, for some $x\bmod 13$. Although $1+5x^2$ is never $0$ over $\mathbb{Q}$, it could have happened that $1+5x^2\equiv 0$ has a solution in $\mathbb{F}_{13}$. This is not the case, because a solution would imply that $x^2\equiv 5\bmod 13$, and $5$ is not a square in $\mathbb{F}_{13}$ (the squares are $1,3,4,9,10$, and $12$).