Andreas Enge 
email: andreas.enge@math.u-bordeaux.fr
  
Komplexe Multiplikation: von numerisch bis symbolisch

Keywords: das dazu, daß sich algebraische, diskrete Objekte mit analytischen, numerischen Methoden berechnen lassen. Anwendungen Die Hauptanwendung der komplexen Multiplikation besteht darin, elliptische Kurven über einem endlichen Körper mit vorab folgenden sehen, wie sich eine solche Primzahlbeweise und -zertifikate (ECPP) nach [1], wie sie z.B. im Computeralgebrasystem MAGMA implementiert sind

Elliptische Kurven mit komplexer Multiplikation

Eine elliptische Kurve E ist eine affine Kurve der Gleichung Y 2 = X 3 + aX + b, wobei a, b Elemente eines Körpers sind. (Im folgenden ist dies C oder ein endlicher Körper F q ; für Körper der Charakteristik 2 oder 3 muß die Gleichung leicht angepaßt werden.) Die Punkte auf der Kurve zusammen mit einem "unendlich fernen" Punkt bilden eine algebraische abelsche Gruppe, in der die Summe zweier Punkte durch rationale Formeln in ihren Koordinaten und in a und b gegeben ist. Über C läßt sich dieses Gruppengesetz auch analytisch darstellen: Für ein Gitter a liefert die Differentialgleichung der Weierstraßschen Funktion ℘ a eine Parametrisierung (℘ a , ℘ ′ a /2) : C/a → E als Riemannsche Fläche; das Gruppengesetz entspricht der Addition in C/a.

Ein Multiplikator oder Endomorphismus von E ist dann ein α ∈ C mit αa ⊆ a. Neben dem trivialen Fall, in dem nur die ganzen Zahlen als Multiplikatoren auftreten, kann es vorkommen, daß der Endomorphismenring die Ordnung O D der Diskriminante D in einem imaginär-quadratischen Zahlkörper K = Q( √ D) ist; man spricht dann von komplexer Multiplikation. Dies ist genau dann der Fall, wenn a ein eigentliches Ideal von O D ist.

Eine elliptische Kurve ist bis auf Isomorphie durch ihre j-Invariante j(E) = 1728 4a 3 4a 3 +27b 2 charakterisiert. Im Fall komplexer Multiplikation läßt sich diese auch wie folgt darstellen: Sei

H = {z ∈ C : ℑz > 0}, und für ein Ideal a = A, -B+ √ D 2 von O D sei τ = -B+ √ D 2A
der Basisquotient in H. Dann gibt es eine meromorphe Funktion j :

H → C mit j(a) := j(τ ) = j(E). Die Funktion j ist modular für Γ = Sl 2 (Z)/{±1}: Für M = a b c d ∈ Γ gilt j(M z) := j az + b cz + d = j(z). (2) 
Dies zeigt, daß j(a) nur von a, nicht jedoch von der Wahl einer speziellen Basis und somit von τ abhängt. Fourier-transformierten Variablen q = e 2πiz betrachten. Dann gilt

j = q -1 + ∞ k=0 c k q k (3)
mit c k ∈ Z; mit anderen Worten, j ist eine meromorphe Funktion auf der Kompaktifizierung der Riemannschen Fläche Γ\H. Praktisch bedeutet (3), daß sich j in jedem Argument τ ∈ H numerisch mit beliebiger Genauigkeit berechnen läßt.

Elliptische Kurven über endlichen Körpern

Endomorphismen haben auch eine rein algebraische Interpretation. So entspricht die Multiplikation mit der vierten Einheitswurzel i auf der Kurve Y 2 = X 3 + X der Abbildung (x, y) → (-x, iy), die in der Tat nach viermaliger Anwendung zur Identität wird. Allgemeiner werden Endomorphismen algebraisch als rationale Abbildungen der elliptischen Kurve (gesehen über dem algebraischen Abschluß des Grundkörpers) auf sich selbst definiert, die gleichzeitig Gruppenhomomorphismen sind.

Über dem algebraischen Abschluß F q eines endlichen Grundkörpers F q spielt der Frobenius-Endomorphismus eine besondere Rolle. Er ist durch die rationale Abbildung π : (x, y) → (x q , y q ) gegeben, wobei der kleine Fermatsche Satz und a, b ∈ F q implizieren, daß das Bild eines Punktes auf E (mit Koordinaten in F q ) wieder auf E liegt. Ebenso zeigt die F q -Rationalität der Additionsformeln, daß π ein Gruppenhomomorphismus ist. Dabei läßt π die F q -rationalen Punkte auf E invariant, daß es sich nicht um die Multiplikation mit einer ganzen Zahl handeln kann; in diesem Sinne haben also alle elliptischen Kurven über F q komplexe Multiplikation. Falls F q = F p m mit p prim ist, besagt der Satz von Deuring genauer, daß "fast alle" elliptischen Kurven über F q sich durch Reduktion nach p einer Kurve über C mit komplexer Multiplikation ergeben, wobei der Endomorphismenring erhalten bleibt [START_REF] Deuring | Die Typen der Multiplikatorenringe elliptischer Funktionenkörper[END_REF]. (Davon ausgenommen sind die supersingulären Kurven, deren Anteil etwa 1/p beträgt.) Insbesondere kann π als ein Element der Norm q einer Ordnung O D betrachtet werden, woraus sich (1) ergibt.

Klassenkörpertheorie

Es muß noch geklärt werden, was genau mit der an sich unsinnigen Formulierung, "eine Kurve über C modulo einer Primzahl p zu reduzieren", gemeint ist. Seien 

K = Q( √ D), a i = A i , -B i + √ D 2 , i = 1, . . . , h D , ein Vertretersystem von Cl D und K D = K(j(
h D Werte von j-Invarianten in F q = F p m . Genauer sind die j(a i ) ganz-algebraisch, und j(O D ) ∈ K D ∩ R, wo- durch das Klassenpolynom H D (X) = h D i=1 X -j -B i + √ D 2A i (4)
in Z[X] liegt. Die j(a i ) mod P sind also schlicht die Nullstellen in F q von H D (X) mod p, womit die Berechnungen wieder auf symbolischer Ebene angelangt sind.

Algorithmus

Die obigen Ausführungen lassen sich direkt in einen Algorithmus übersetzen: 1) Wähle D und q = p m mit (1), so daß die Punktezahl N = q+1-t die gewünschten Eigenschaften hat.

2) Bestimme ein Vertretersystem von Cl D der Form

a i = A i , -B i + √ D 2 , i = 1, . . . , h D .
3) Berechne numerisch die Werte von j in den a i , z.B. mittels (3), und das Klassenpolynom H D wie in (4).

4) Runde die Koeffizienten von H D auf ganze Zahlen, reduziere modulo p und bestimme eine Nullstelle j ∈ F q .

5) Sei γ ein quadratischer Nichtrest in F q . Die beiden elliptischen Kurven E :

Y 2 = X 3 + aX + b und E ′ : Y 2 = X 3 +aγ 2 X +bγ 3 mit k = j 1728-j , a = 3k, b = 2k haben j-Invariante j, und eine hat q + 1 -t, die andere q + 1 + t Punkte.
In 1) wäre es wünschenswert, sowohl q als auch N festzulegen; dann gilt i.a. |D| ≈ q, was diesen Ansatz für größere Werte von q nicht praktikabel macht. Stattdessen hält man i.a. D fest und löst entweder die diophantische Gleichung (1) für verschiedene Werte von q oder wählt zufällige Werte t, v, bis q in (1) zu einer Primzahlpotenz wird. Alternativ kann man q fixieren und versuchen, (1) für kleine Werte von D zu lösen; oder man kann N festhalten, verliert dafür aber die Kontrolle über q.

Die Existenz zweier Kurven in 5) mit derselben j-Invariante, aber verschiedener Punktezahl scheint zunächst der Tatsache zu widersprechen, daß die j-Invariante elliptische Kurven bis auf Isomorphie charakterisiert. In der Tat gilt diese Charakterisierung nur über F q , und die beiden Kurven sind genauer über F p 

Numerische Betrachtungen

Der Algorithmus mit Gleitkommaberechnungen ist numerisch sehr stabil; für große Klassenzahlen reicht es in der Praxis, die Genauigkeit um 1% höher zu wählen als die erwartete Stellenzahl der Koeffizienten. Für die Auswertung von j läßt sich dies leicht plausibel machen. Anstelle von (3) geht man für kleinere Klassenzahlen von der Dedekindschen η-Funktion aus und verwendet die folgenden Formeln; der resultierende Algorithmus hat eine Komplexität von O˜ |D| 5/4 anstatt O˜(|D|): η(q) = q 1/24 ∞ k=-∞ (-1) k q k(3k-1)/2

(5)

f 1 (q) = η(q 1/2 ) η(q) , j = (f 24 1 + 16) 3 /f 24 1 .
Das quadratische Wachstum der Exponenten in (5) führt dazu, daß der absolute Fehler in den Potenzen von q sehr schnell abnimmt; die Kumulation von Fehlern durch die Additionen und Subtraktionen in (5) ist also praktisch vernachlässigbar, und der gesamte Rundungsfehler ist im wesentlichen durch die ersten beiden Terme 1 -q bestimmt. Ab einem Polynomgrad von etwa 100 000 ist der Algorithmus von [START_REF] Dupont | Fast evaluation of modular functions using Newton iterations and the AGM[END_REF] mit Komplexität in O˜(|D|) auch praktisch schneller. Das AGM zweier Zahlen a 0 , b 0 , gemeinsamer Grenzwert der beiden Folgen a i+1 = a i +b i 2 , b i+1 = √ a i b i , ist numerisch unkritisch, sobald die beiden Ausgangszahlen z.B. im selben Quadranten liegen; das weiterhin benutzte Newton-Verfahren stabilisiert die Auswertung zusätzlich.

Software

Die Arithmetik von komplexen Zahlen beliebiger Genauigkeit ist in der C-Bibliothek MPC implementiert und steht auf http://www.multiprecision. org/ unter der LGPL frei zur Verfügung. Dort findet sich auch ein unter der GPL stehendes Programm, das den oben beschriebenen Algorithmus zur komplexen Multiplikation implementiert.

Ausblick

Anstelle der Klassenpolynome (4) verwendet man in der Praxis Polynome zu alternativen Modulfunktionen, die asymptotisch um einen konstanten Faktor kleiner sind. Typischerweise liegt dieser Faktor zwischen 12 und 72. Für ausführlichere Abhandlungen sei auf das in Kürze erscheinende Buch [START_REF] Schertz | Complex Multiplikation[END_REF] und das erste Kapitel von [START_REF] Enge | Courbes algébriques et cryptologie[END_REF] hingewiesen.

Es soll nicht unerwähnt bleiben, daß neben dem hier dargestellten komplexen Lift auch ein p-adischer Lift des Klassenpolynomes möglich ist [START_REF] Couveignes | Action of modular correspondences around CM points[END_REF][START_REF] Bröker | Elliptic curves with a given number of points[END_REF]. Auch dieser ist quasilinear in der Ausgabegröße, so daß beide Algorithmen schließlich nicht durch ihre Laufzeit, sondern durch den verfügbaren Speicherplatz begrenzt sind: Das größte mit dem Gleitkommaalgorithmus berechnete Klassenpolynom hat einen Grad von h D = 100 000 und belegt etwa 5 GB im Hauptspeicher, wobei die Rechenzeit nur etwa 3 Tage beträgt und mögliche Parallelisierungen nicht implementiert wurden [START_REF] Enge | The complexity of class polynomial computation via floating point approximations[END_REF].

Vor Kurzem wurde ein ebenfalls quasilinearer, rein symbolischer Algorithmus entwickelt, der Koeffizient

  2 isomorph. (Für D = -4 und D = -3 gibt es nicht nur zwei, sondern vier bzw. sechs Möglichkeiten; dies entspricht der Anzahl der Einheitswurzeln in O D .) Beispiel Für D = -23 und p = 6427752177035949684186 306721878284835035747081564392976559049 ist (1) mit t = -5070602400912913102387185451082 und v = 1992 erfüllt; dann hat N = 4•16069380442589874 21046576680470838859359164998666695040502533 einen Primfaktor von 200 Bit, und die im folgenden berechnete Kurve kann in einem Kryptosystem mit einem Sicherheitsniveau von 100 Bit verwendet werden. Die Klassengruppe wird durch die drei Ideale 1zugehörigen Werte von j sind j 1 = -3493225, 6999699 . . . und j 2/3 = 737, 84998496668 . . . ± 1764, 0189386127 . . . i. Man berechnet H -23 (X) = X 3 + 3491749, 99 . . . X 2 -5151296875, 00 . . . + 0, 87 . . . • 10 -10 i X + 12771880859374, 90 . . . = X 3 + 3491750X 2 -5151296875X + 12771880859375. Modulo p erhält man die Nullstelle j = 270 22464776947513721864100007729950899118299475 70287185881304 und die Kurve Y 2 = X 3 +579798479 89453991104160798789265455110899542658590728 79574388X +348883774594671367325858145477016 7989955380608272899190630631 mit j-Invariante j und mit N Punkten. Komplexität Die Klassenpolynome H D zeichnen sich durch sehr große Koeffizienten aus, wie das obige Beispiel anschaulich illustriert: Schon das kleinste Polynom vom Grad 3 für D = -23 läßt sich nicht mehr mit dem Taschenrechner oder doppelter Genauigkeit bestimmen; denn es ist klar, daß die Anzahl der Gleitkommastellen mindestens der Anzahl n der Stellen des größten Koeffizienten entsprechen muß, um korrekt runden zu können. Man kann zeigen, daß n ∈ O˜ |D| und weiterhin h D ∈ O˜ |D| , so daß die Gesamtgröße von H D in O˜(|D|) liegt. Dabei sind die Konstanten und logarithmischen Faktoren in O˜explizit, siehe [9, 2]. Sei M (n) ∈ O˜(n) die Komplexität der Multiplikation zweier Zahlen mit n Stellen. In [9, 7] werden zwei Algorithmen beschrieben, mit denen sich die benötigten h D Werte von j mit einer amortisierten Komplexität von O˜(M (n)) pro Wert berechnen lassen, was zu einer Gesamtkomplexität des Algorithmus von O˜(|D|) führtdies ist quasilinear in der Ausgabegröße! Der erste Ansatz berechnet O˜(n) Terme von (3) und nutzt aus, daß sich mittels Algorithmen der modernen Computeralgebra ein Polynom vom Grad O˜(n) in O˜(n) Argumenten in derselben Zeit O˜(n M (n)) auswerten läßt wie in einem einzigen Argument [10, §10.1]. Das zweite Verfahren benutzt Newton-Iterationen auf einer Funktion, die als wesentlichen Baustein das arithmetisch-geometrische Mittel (AGM) enthältdieses läßt sich dank quadratischer Konvergenz in O˜(M (n)) berechnen.

  a 1 )). Der erste Hauptsatz der komplexen Multiplikation [6, §9] besagt, daß K D /K eine Galois-Erweiterung mit Gruppe Cl D ist. Die Reduktion findet daher nicht nach p, sondern nach einem Primideal P in K D statt, das über p liegt und Trägheitsgrad m hat; das Ergebnis sind dann

F. Vercauteren: Counting points on curves over finite fields, Computeralgebra-Rundbrief 43,

2008, S. 16-19 2 F. Heß: Kryptographie mit elliptischen Kurven, Computeralgebra-Rundbrief 39, 2006, S. 14-18