Timeline for Counting $\mathrm{mod}\:p$ solutions of Diophantine equation in two variables taking $O(p^2)$ time
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 17, 2021 at 5:55 | comment | added | Disen | The definition in en.wikipedia.org/wiki/Diophantine_equation requires it to be polynomial. I don't mean $\Theta(p^2)$ I mean $\Omega(p^2)$ in Knuth's sense but since there is ambiguity about $\Omega$ I didn't want to use it and instead opted for "requires $O(p^2)$ time." Sorry for any confusion. | |
| Sep 17, 2021 at 5:36 | answer | added | Steven Stadnicki | timeline score: 4 | |
| Sep 16, 2021 at 23:43 | comment | added | Steven Stadnicki | When you say 'diophantine equation' I presume you mean polynomial? (And presumably you mean $\Theta(p^2)$ rather than $O(p^2)$, since e.g. $\log p\in O(p^2)$). And for that matter, do you know of an example where the best known algorithms take even $\Omega(p)$ time? Elliptic curves, for instance, have much faster algorithms known... | |
| Sep 16, 2021 at 20:10 | history | edited | Disen | CC BY-SA 4.0 |
added 34 characters in body
|
| Sep 16, 2021 at 20:02 | history | edited | Disen | CC BY-SA 4.0 |
added 55 characters in body
|
| S Sep 16, 2021 at 19:55 | review | First questions | |||
| Sep 16, 2021 at 21:40 | |||||
| S Sep 16, 2021 at 19:55 | history | asked | Disen | CC BY-SA 4.0 |