Elliptische Kurven über $\mathbb{Z}_{n}\protect$

Der Begriff einer elliptischen Kurve über einem Ring $\mathbb{Z}_{n}\protect$ erweist sich als sehr nützlich. Doch auf den ersten Blick mag es verwunderlich erscheinen, elliptische Kurven über einem Ring zu betrachten, wo wir doch spätestens bei der Addition von Punkten sehr stark auf die Körperstruktur angewiesen waren. Deswegen sehen wir von der Gruppenstruktur ab, und betrachten eine elliptische Kurve über dem Ring $\mathbb{Z}_{n}\protect$ erstmal als eine Menge von Punkten, die einer bestimmten Gleichung genügen.

Definition 3.1   Sei $n$ eine positive ganze Zahl mit $\textrm{ggT}\left( n,6\right) =1$. Eine elliptische Kurve über $\mathbb{Z}_{n}\protect$ ist gegeben durch die Gleichung

$$E_{a,b}:\quad y^{2} = x^{3}+ax+b,$$ (3.1)

wobei $a,b\in \mathbb{Z}$ und $\textrm{ggT}\left( 4a^{2}+27b^{2},n\right) =1$. Die Menge der Punkte auf $E_{a,b}$ wird als $E_{a,b}\left( \mathbb{Z}_{n}\right)$ bezeichnet. Es sind die Lösungen der Gleichung 3.1 in $\mathbb{Z}_{n}\times \mathbb{Z}_{n}$ zusammen mit dem unendlich fernen Punkt $\O _{n}$.

Es sei nun $p$ ein Primteiler von $n$, und bezeichne $\bar{a}$ den Rest von $a$ modulo $p$. $E_{\bar{a},\bar{b}}$ ist dann die Gleichung einer elliptischen Kurve über dem Körper $\mathbb{F}_{p}$. Zu einem Punkt $P=\left( x,y\right) \in E_{a,b}\left( \mathbb{Z}_{n}\right)$ definieren wir $P_{p}:=\left( \bar{x},\bar{y}\right)$. Zu $\O _{n}$ definieren wir $\left( \O _{n}\right) _{p}$ als den unendlich fernen Punkt $\O _{p}$ in $E_{\bar{a},\bar{b}}\left( \mathbb{F}_{p}\right)$. Offenbar gilt $P_{p}\in E_{\bar{a},\bar{b}}\left( \mathbb{F}_{p}\right)$.

Wie am Anfang des Abschnittes angemerkt, wird es uns kaum gelingen eine Gruppenstruktur auf $E_{a,b}\left( \mathbb{Z}_{n}\right)$ zu bekommen. Trotz allem definieren wir eine Pseudo-Addition wie in der Definition 1.2. Wir werden versuchen Formel 1.2 anzuwenden, solange wir keinen undefinierten Ausdruck erhalten, d.h. solange der Fall $\textrm{ggT}\left( x_{2}-x_{1},n\right) \neq 1$ nicht eintritt. In diesem Fall ist unsere Pseudo-Addition nicht definiert.

Die folgenden Eigenschaften der Pseudo-Addition können nachgewiesen werden:

1. Für $P,Q\in E_{a,b}\left( \mathbb{Z}_{n}\right)$ und $P+Q$ nicht definiert, ergibt sich während der Berechnung ein nicht trivialer Teiler von $n$.
2. Ist $P,Q\in E_{a,b}\left( \mathbb{Z}_{n}\right)$ und $P+Q$ definiert durch die Pseudo-Addition, dann gilt
   $$\left( P+Q\right) _{p}=P_{p}+Q_{p}$$
   für alle Primteiler $p$ von $n$. (Beachte, daß die rechte Seite der Gleichung immer definiert ist.)
3. Insbesondere ist $P\in E_{a,b}\left( \mathbb{Z}_{n}\right) ,k\in \mathbb{Z}$ und $k\cdot P:=\underbrace{P+\ldots +P}_{k\textrm{ mal}}$ definiert durch wiederholte Anwendung der Pseudo-Addition, dann gilt
   $$\left( kP\right) _{p}=kP_{p}$$
   für alle Primteiler $p$ von $n$.

Angenommen $n$ ist das Produkt von zwei Primzahlen $p,q$. Setze

$$\tilde{E}_{a,b}\left( \mathbb{Z}_{n}\right) :=E_{a,b}\left( \mathbb{F}_{p}\right) \times E_{a,b}\left( \mathbb{F}_{q}\right)$$

Im Gegensatz zu $E_{a,b}\left( \mathbb{Z}_{n}\right)$ ist $\tilde{E}_{a,b}\left( \mathbb{Z}_{n}\right)$ eine Gruppe, da sie direktes Produkt von zwei Gruppen ist. Jeder Punkt $P$ auf $E_{a,b}\left( \mathbb{Z}_{n}\right)$ korrespondiert zu einem eindeutigen Punkt auf $\tilde{E}_{a,b}\left( \mathbb{Z}_{n}\right)$, nämlich zu $\left( P_{p},P_{q}\right)$. Punkte auf $\tilde{E}_{a,b}\left( \mathbb{Z}_{n}\right)$ von der Form $\left( \O _{p},Q\right)$ und $\left( P,\O _{q}\right)$ haben keine korrespondierenden Punkte auf $E_{a,b}\left( \mathbb{Z}_{n}\right)$. Wegen der obigen Eigenschaft $\left( 2\right)$ sehen wir, falls die Pseudo-Addition in $E_{a,b}\left( \mathbb{Z}_{n}\right)$ definiert ist, so ist diese identisch mit der Addition in $\tilde{E}_{a,b}\left( \mathbb{Z}_{n}\right)$, d.h. für $P,Q\in E_{a,b}\left( \mathbb{Z}_{n}\right)$ und $P+Q$ definiert, gilt:

$$\left( \left( P\underbrace{+}_{in\, E_{a,b}\left( \mathbb{Z}_{n}\... ...}_{in\, \tilde{E}_{a,b}\left( \mathbb{Z}_{n}\right) }\left( Q_{p},Q_{q}\right)$$

Das hat weitreichende Konsequenzen, wir können nämlich in der Gruppe $\tilde{E}_{a,b}\left( \mathbb{Z}_{n}\right)$ rechnen, ohne die Primfaktoren $p$ und $q$ tatsächlich zu kennen. Sollte die Anwendung der Gruppenoperationen fehlschlagen, so erhalten wir einen nicht trivalen Faktor von $n$. Sind $p$ und $q$ in der Größenordnung von 100 Dezimalstellen, so kann das Fehlschlagen der Pseudo-Addition als sehr unwahrscheinlich angenommen werden, da das Faktorisieren von solch großen Zahlen als sehr hart angesehen wird.