Let $p$ be an odd prime number and let me call $G = \mathbb{F}_p^{\times}$ the multiplicative group of the field $\mathbb{F}_p$, i.e. $G = \mathbb{Z}_p^{\times}$ if you prefer this notation. Here we can define the concept of quadratic residue,
Let $a \in G$, then $a$ is a quadratic residue modulo $p$ if there exists $x \in G$ such that
$$x^2 \equiv a \bmod p$$
Since $p$ is prime we now that there are $(p-1) / 2$ quadratic residues in $G$. This means that $$|G / G^2| = 2$$
Moreover, we know how to detect the class of $a$ in $G/G^2$ using the Legendre symbol and the Reciprocity Law. Furthermore, we know algorithms that allow us to compute the Legendre symbol very quickly.
Now, let me move into the field of Elliptic Curves and let me call $H = E(\mathbb{F}_p)$ the additive abelian group of the elliptic curve $E$ defined over the finite filed $\mathbb{F}_p$. From a well-know theorem we know that:
$$ H \cong \mathbb{Z}_n \quad \text { or } \quad H \cong \mathbb{Z}_{n_1} \oplus \mathbb{Z}_{n_2} $$
for some integer $n \geq 1$ or integers $n_1,n_2 > 1$ such that $n_1 \, | \, n_2$.
Since we are working with additive groups the concept of quadratic residue fails. nevertheless, we can look for a "double" residue which means:
Given a point $P \in H$, then there exists $Q \in H$ such that $$P = 2Q$$
However, here we have a lot of possibilities compared with those ones of multiplicative groups. Indeed, knowing the parity of $n$ or $n_1, n_2$ we discover that: $$ | H / 2H | \in \{1,2,4 \} $$
Knowing this fact I ask myself (and you of course): is there an analogous of Reciprocity Law that allows us to detect in which class of $H/2H$ the point $P$ lies? If so, are there polynomial algorithms that allow us to make this computation?
Best Answer
You can define the same concept for any finite abelian group $G$ and any positive integer $n$.
Let $e$ be the exponent of $G$. For any $n \in \mathbf{N}$, let $n' = \mathrm{gcd}(n, e)$. Then $G/nG \cong G[n']$, where the latter is the $n'$ torsion of $G$, induced by the map $$G \to G[n']\\ g \mapsto (e/n')*g$$
In the case $G = \mathbf{F}_p^\times$ and $n = 2$, we have $e = p-1$ and recover the Legendre symbol $$x \mapsto \left ( \frac{x}{p} \right ) = x^{e/2} \in \{\pm 1\} = (\mathbf{F}_p^\times)[2].$$
Let $E/\mathbf{F}_p$ be an elliptic curve. Let $H = E(\mathbf{F}_p) \cong \mathbf{Z}_{n_1} \oplus \mathbf{Z}_{n_2}$ with $n_1 \mid n_2$ (if $H$ is cyclic, just take $n_1 = 1$) and $P \in H$. We assume $2 \mid n_2$, otherwise $H/2H$ is trivial.
Then the class of $P$ in $H/2H$ is determined entirely by $$(n_2/2) * P \in H[2] = E(\mathbf{F}_p)[2].$$ This, of course, can be computed in polynomial time.