Eigenschaften von $E\left( \mathbb{F}_{q}\right) \protect$

Sei $E$ eine elliptische Kurve über $\mathbb{F}_{q}$ mit $q=p^{m}$, wobei $p$ (eine Primzahl) die Charakteristik von $\mathbb{F}_{q}$ ist. Wir bezeichnen die Zahl der Punkte auf $E\left( \mathbb{F}_{q}\right) \protect$ mit $\char93 E\left( \mathbb{F}_{q}\right)$. Wenn wir die Weierstraß Gleichung 2.1 betrachten, so sehen wir, daß für jedes feste $x\in \mathbb{F}_{q}$ die Gleichung höchstens zwei Lösungen hat (es bleibt ein quadratischen Polynom übrig), also muß die Abschätzung $\char93 E\left( \mathbb{F}_{q}\right) \leq 2q+1$ gelten ($q$ Möglichkeiten $x$ zu wählen und $\O$). Heuristisch gesehen würde man erwarten, daß bei nur der Hälfte der betrachteten $x$ eine Lösung in $\mathbb{F}_{q}$ existiert, also folgt daraus $\char93 E\left( \mathbb{F}_{q}\right) \approx q$. Der nachfolgende Satz bestätigt diese Vermutung.

Theorem 2.3 (Hasse)   Es sei $\char93 E\left( \mathbb{F}_{q}\right) =q+1-t$. Dann ist $\left\vert t\right\vert \leq 2\sqrt{q}$.

Wir sehen also, daß ein zufällig gewähltes Element $x_{0}\in \mathbb{F}_{q}$ mit der Wahrscheinlichkeit

$$\frac{\frac{1}{2}\left( \char93 E\left( \mathbb{F}_{q}\right) -1\... ...b{F}_{q}\right\Vert }\geq \frac{q-2\sqrt{q}}{2q}=\frac{1}{2}-\frac{1}{\sqrt{q}}$$

die $x$-Koordinate eines Punktes von $E\left( \mathbb{F}_{q}\right) \protect$ darstellt. Ist $x_{0}$ die $x$-Koordinate eines Punktes $P\in E\left( \mathbb{F}_{q}\right)$, dann können wir die zugehörige $y$-Koordinate durch Wurzelziehen in $\mathbb{F}_{q}$ finden, dazu existieren probabilistische Algorithmen. Wir bekommen automatisch einen zweiten Punkt, nämlich $-P$. Insgesamt haben wir einen probabilistischen Algorithmus zum Auffinden von Punkten auf $E\left( \mathbb{F}_{q}\right) \protect$, der in polynomieller Zeit arbeitet.

Auch von Interesse ist oft die tatsächliche Anzahl der Punkte auf einer elliptischen Kurve $E\left( \mathbb{F}_{q}\right) \protect$. 1985 hat Schoof einen polynomiellen Algorithmus für die Berechnung von $\char93 E\left( \mathbb{F}_{q}\right)$ angegeben. Eine Modifikation dieses Algorithmus haben Buchmann und Muller 1991 vorgestellt, um Ordnungen elliptischer Kurven über $\mathbb{F}_{p}$ zu berechnen. Eine Implementierung dieser Methode hat z.B. Ordnungen von Kurven über $\mathbb{F}_{p}$, wo $p\approx 10^{27}$ prim in ca. 4.5 Stunden auf einer SUN-1 SPARC-station berechnet.