Sorry, I have a very basic question about Schoof's paper, when he is talking about taking the sum of quadratic residues to count points.
"This implies that evaluating the sum $$\sum_{x \in F_p} \left(\frac{x^3 + Ax + B}{p} \right)$$ is the same problem as computing $\#E(F_p)$".
He then says: "In practice it is convenient to make first a table of squares modulo $p$" and then count how often $x^3 + Ax + B$ is a square for $x = 0, 1, ..., p-1$."
I've stared at it for a long time but I don't really understand this process. Sorry if this is really basic but I would really appreciate if someone can explain. So for example if we have $p = 3$ and elliptic curve $C: y^2 = x^3 +1$, then how does this work?
Well, the curve you offered is not elliptic, since when $p=3$, we have $x^3+1=(x+1)^3$. Let’s perform the task for $y^2=x^3-x$ in case $p=3$ and in case $p=5$.
When you evaluate $x^3-x$ for $x=0,1,2\in\Bbb F_3$, you get zero every time, and there is only one $y$ with $y^2=0$, so that there are three points in the “finite” plane, giving a total of four when you count the point $\Bbb O$ at infinity.
More interestingly, when you work in $\Bbb F_5$ and evaluate $x^3-x$ at $0,1,2,3,4$, you can check that the values are $0,0,1,4,0$. The zero values contribute one each to the total count, and since both $1$ and $4$ are squares in $\Bbb F_5$, you get two points on the curve when $x$ is each of $2$ and $3$. Including $\Bbb O$ again, you get a total count of eight points on the curve.
You’ll find that when you do the same computation for $y^2=x^3-x$ at $p=7$, some evaluations of $x^3-x$ give a nonsquare like $6$ or $3$, and then there is no contribution to the totality of points on the curve.