Given an elliptic curve over $\mathbb Z_n$
Is it $\#P$ hard to compute $\# E(\mathbb Z_n)$?
Is it $PP$-hard to compute $\# E(\mathbb Z_n)\leq\frac n2$?
Is it $\oplus P$ hard to compute $\# E(\mathbb Z_n)\bmod 2$?
$\begingroup$
$\endgroup$
10
-
2$\begingroup$ Could you define what you call an elliptic curve over $\Bbb{Z}_n$? $\endgroup$– abxCommented Jul 10, 2020 at 14:22
-
$\begingroup$ Sorry I was thinking on this mathoverflow.net/questions/95408/elliptic-curves-over-rings. If not appropriate I can take it down or just use $\mathbb F_q$ since that does not change the nature of the question. $\endgroup$– VS.Commented Jul 10, 2020 at 14:24
-
1$\begingroup$ And even define $\mathbb{Z}_n$ as it's both used for $\mathbb{Z}/n\mathbb{Z}$ and for the $n$-adics (projective limit of $\mathbb{Z}/n^k\mathbb{Z}$). $\endgroup$– YCorCommented Jul 10, 2020 at 14:30
-
6$\begingroup$ For $n$ prime we have Schoof's algorithm which is polynomial in the number of bits, so all these problems are in $P$. For other $n$ the hardest step might be factoring, which is not believed to be polynomial time, but also not expected to be hard for any of these hardness classes. $\endgroup$– Will SawinCommented Jul 10, 2020 at 15:17
-
3$\begingroup$ For a reference, see the Wikipedia page on "Counting points on elliptic curves" en.wikipedia.org/wiki/Counting_points_on_elliptic_curves $\endgroup$– Will SawinCommented Jul 10, 2020 at 15:23
|
Show 5 more comments