Ciro Santilli @cirosantilli 35

mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/103415#103415 provides a specific single undecidable Diophantine equation.

Polynomial time for most inputs, but not for some very rare ones. TODO can they be determined?

But it is better in practice than the AKS primality test, which is always polynomial time.

Minimum number of elements in a generating set of a group.

One major difference between the elliptic curve over a finite field or the elliptic curve over the rational numbers the elliptic curve over the real numbers is that not every possible $x$ generates a member of the curve.

This is because on the Equation "Definition of the elliptic curves" we see that given an $x$, we calculate $x^3+ax+b$, which always produces an element $y^2$.

But then we are not necessarily able to find an $y$ for the $y^2$, because not all fields are not quadratically closed fields.

For example: with $a=1$ and $b=1$, taking $x=1$ gives:and therefore there is no $y\in \mathbb{Q}$ that satisfies the equation. So $x=1$ is not on the curve if we consider this elliptic curve over the rational numbers.

That $x$ would also not belong to Elliptic curve over the finite field ${\mathbb{F}}_4$, because doing everything $\mathrm{m}\mathrm{o}\mathrm{d}4$ we have:Therefore, there is no element $y\in {\mathbb{F}}_4$ such that $y\times y=2$ or $y\times y=3$, i.e. $2$ and $3$ don't have a multiplicative inverse.

For the real numbers, it would work however, because the real numbers are a quadratically closed field, and $\sqrt{3}\in \mathbb{R}$.

For this reason, it is not necessarily trivial to determine the number of elements of an elliptic curve.

The Equation "Definition of the elliptic curves" and definitions on elliptic curve point addition both hold directly.

The paper that states the BSD conjecture.

Likely paywalled at: www.degruyter.com/document/doi/10.1515/crll.1965.218.79/html. One illegal upload at: virtualmath1.stanford.edu/~conrad/BSDseminar/refs/BSDorigin.pdf.