Timeline for Counting points in elliptic curves
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 17, 2020 at 12:12 | history | undeleted | VS. | ||
| Jul 11, 2020 at 9:03 | history | deleted | VS. | via Vote | |
| Jul 10, 2020 at 16:38 | comment | added | VS. | I understand. I am asking converse question. | |
| Jul 10, 2020 at 16:31 | comment | added | Will Sawin | I'm just saying you could first factor and then count points on each prime. This means counting points can't be #P-hard unless factoring is. | |
| Jul 10, 2020 at 16:11 | comment | added | VS. | @willsawin Does counting points give factors? | |
| Jul 10, 2020 at 15:23 | comment | added | Will Sawin | For a reference, see the Wikipedia page on "Counting points on elliptic curves" en.wikipedia.org/wiki/Counting_points_on_elliptic_curves | |
| Jul 10, 2020 at 15:17 | comment | added | Will Sawin | 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. | |
| Jul 10, 2020 at 14:48 | comment | added | Chris Wuthrich | Thanks to the Chinese remainder theorem and the known structure of the formal group of elliptic curves, these questions all boil down to calculating group orders for elliptic curves over $\mathbb{F}_p$. In particular 2 should be easy and 3 is trivial as there is not problem checking if there are $2$-torsion points. | |
| Jul 10, 2020 at 14:37 | history | edited | VS. | CC BY-SA 4.0 |
deleted 56 characters in body
|
| Jul 10, 2020 at 14:35 | comment | added | VS. | I was just think $\mathbb Z/n\mathbb Z$. I doubt over infinite sets the problem makes sense. | |
| Jul 10, 2020 at 14:31 | history | edited | YCor | CC BY-SA 4.0 |
formatting
|
| Jul 10, 2020 at 14:30 | comment | added | YCor | 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}$). | |
| Jul 10, 2020 at 14:24 | comment | added | VS. | 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. | |
| Jul 10, 2020 at 14:22 | comment | added | abx | Could you define what you call an elliptic curve over $\Bbb{Z}_n$? | |
| Jul 10, 2020 at 14:11 | history | asked | VS. | CC BY-SA 4.0 |