Exercise 5.8.6 (Order of the group $E_f(\mathbb{Z}_p)$)

Question

Suppose that the polynomial $x^3 + ax^2 + bx +c$ has no repeated root $\pmod p$, and put $f(x,y) = y^2 - (x^3 +ax^2 + bx +c)$. Show that the group of points of the elliptic curve $\mathscr{C}_f(\mathbb{Z}_p)$ has order
$$|E_f(\mathbb{Z}_p)| = p+ 1 + \sum_{x = 1}^p \genfrac{(}{)}{}{}{f(x)}{p}.$$

Note: Here $f(x)$ is  $f(x) =x^3 + ax^2 + bx +c$ (note of R.G.).

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof} 
Since $E_f(\Z_p) = \mathscr{C}_f(\Z_p) \cup \{O\}$, where $O$ is the point at infinity of the curve, we obtain
$$|E_f(\Z_p)| = |\mathscr{C}_f(\Z_p)| + 1.$$
Put, for some fixed $z \in \Z_p$,
$$N(y^2 = z) = \mathrm{Card}\{y \in \Z_p \mid y^2 = z\}.$$

We know that for all $z \in \Z_p$,
$$N(y^2 = z) = 1 + \legendre{z}{p}.$$
(Consider the three cases $z = 0$, $z$ is a nonzero residue, and $z$ is a nonresidue.)

For every fixed $x_0$ put $A_{x_0} = \{(x_0,y) \in \Z_p \mid y^2 = f(x_0)\}$. Then   $A_{x_0}$ is in bijective correspondence with $B_{x_0} = \{y \in \Z_p \mid y^2 = f(x_0)\}$ by $(x_0,y) \mapsto y$, and $\mathscr{C}_f(\Z_p) = \bigcup\limits_{x \in \Z_p} A_x$ (disjoint union). Hence we obtain
\begin{align*}
|\mathscr{C}_f(\Z_p)| &= \sum_{x \in \Z_p} N(y^2 = f(x))\
&= \sum_{x \in \Z_p} \left ( 1 + \legendre{f(x)}{p}ight)\
&= p +  \sum_{x \in \Z_p}  \legendre{f(x)}{p}.
\end{align*}
Therefore
$$|E_f(\Z_p)|  = p + 1 + \sum_{x \in \Z_p}  \legendre{f(x)}{p}.$$
\end{proof}

Example: Consider the group of the curve $y^2 = x^3 - 7x + 7$ on the field $\Z_p$, where $p = 37409$ (see p. 286).
\begin{verbatim}
sage: p = 37409
sage: is_prime(p)
True
sage: def f(x): return (x^3 - 7*x + 7) % p
sage: N = p + 1 + sum(kronecker(f(x),p) for x in range(p)); N
37620
sage: factor(N)
2^2 * 3^2 * 5 * 11 * 19
\end{verbatim}
So $|E_f(\Z_p)|  = 37620 = 2^2\cdot 3^2 \cdot 5 \cdot 11 \cdot 19.$

This ``lengthy calculation'' takes 0.15 s on my modest computer.

Exercise 5.8.6 (Order of the group $E_f(\mathbb{Z}_p)$)

Answers

Comments

Exercise 5.8.6 (Order of the group $E_f(\mathbb{Z}_p)$)

Answers

Comments

Add answer