Consider the elliptic curve E_p: y^2 identicalto x^3 - ax (mod p) where p identi
ID: 3109533 • Letter: C
Question
Consider the elliptic curve E_p: y^2 identicalto x^3 - ax (mod p) where p identicalto 3 (mod 4) is prime and a notidenticalto 0 (mod p). Show that x^3 - ax is a nonzero quadratic residue (mod p) if and only if -(x^3 - ax) is a quadratic nonresidue. Conclude that if x notequalto 0, then if a given value gives x solution to y^2 identicalto x^3 - ax (mod p) then -x must give none and hence that for each possible x (mod p) the pair x, -x gives precisely two points. Use the above to prove that under the conditions of the problem #E_p = p + 1.Explanation / Answer
Let p3(mod4) be a prime. We know that 1 is not a quadratic residue modulo p. This will be the key.
Consider the polynomial f(x)=x3ax as a function from Fp to itself. We easily see that f(x)=0 if and only if x{0,± a}.
For all these values of x there is thus exactly one value of yFp such that y2=f(x), namely y=0. Three solutions so far. Let x=a be any of the other p3 elements of Fp.
We know that f(a)0. Furthermore f(a)=f(a), so exactly one of f(a) and f(a) will be a quadratic residue.
When f(a) is a non-zero quadratic residue, the equation y2=f(a) holds for two distinct values of a. When f(a) is a quadratic non-residue, the equation y2=f(a) has no solutions. Altogether, the pair of choices x=±a thus gives rise to exactly two points on the curve.
There are (p3)/2 such pairs x=±a. We have shown that the equation y2=x3ax
has exactly 3+2(p3)/2=p solutions (x,y)F2p. When you include the point at infinity, you see that the number of Fp-rational points on this elliptic curve is p+1 as claimed.