Abschnitt 1: Ringe und Teilbarkeit.

1.1 Definition: Ring, Integritätsring, Körper 1.2 Beispiele von Ringen: Polynomringe, Matrixringe, Quaternionen 1.3 Direkte Summe 1.4 Ideal 1.5 Restklassenring 1.6 Homomorphismus 1.7 Homomorphiesatz 1.8 Einheiten, Atome und Primelemente 1.9 Euklidische Ringe, Hauptidealbereiche, faktorielle Ringe 1.10 Charakterisierung faktorieller Ringe 1.11 Definition: größter gemeinsamer Teiler 1.13 Euklidischer Algorithmus. (Vgl. MAPLE-Programme) 1.14 Verbesserungen Euklidischen Algorithmus für (große) ganze Zahlen.

1. Idee: Ist a = ∑_{j=1}^{n} a_{i}M^{i} und b = ∑_{j=1}^{n} b_{i}M^{i}, 0 ≤ a_{i}, b_{i} < M (mit M = 2^{15}, 2^{31} je nach Rechnerstruktur), so hängen die ersten Schritte des Euklidischen Algorithmus nur von a_{n} und b_{n} ab, da a/b ∼ a_{n}/b_{n}. Man führt den Euklidischen Algorithmus parallel für (a_{n} + 1, b_{n}) und (a_{n}, b_{n} + 1) durch. Macht man dabei dieselben Umformungen, so sind diese auch für (a, b) richtig. Sobald man eine Abweichung bekommt, rechnet man einmal mit den exakten Werten (a, b), bekommt neue Zahlen (a′, b′) mit ggT(a, b) =ggT(a′, b′) und rechnet dann mit den höchsten Ziffern von (a′, b′) weiter (vgl. Algorithmus 1.3.7 in H. Cohen).

2. Idee: Ersetze die Division mit Rest durch binäre shifts: Ist a = 2^{α}a′ und b = 2^{β}b′, mit ungeraden Zahlen a′, b′, so ist ggT(a, b) = 2^{min(α,β)}ggT(a′, b′). Setzt man t := a′ − b′ = 2^{γ}t′, so ist ggT(a′, b′) =ggT(t′, min(|a′|, |b′|)).

1.17 Der chinesische Restsatz. (Algorithmus: vgl. MAPLE-Programme)

Abschnitt 2: Invertieren von Matrizen und Determinanten. 2.1 Definition: Inverse, Determinante, Adjungierte 2.2 A · adj(A) = det(A) · I, det(A) · det(B) = det(A · B). 2.3 Formeln für det(A) und adj(A) nur von theoretischer Bedeutung. 2.4 Gauß Algorithmus (über Körpern)

2.5 Idee des Gauß Algorithmus: Finde elementare Matrizen U_{1}, …, U_{s} so dass U_{s} · . . . · U_{1} · A = D eine Dreiecksmatrix ist und berechne dann A^{−1} = D^{−1}U_{s} · . . . · U_{1}.

2.6 Gauß Algorithmus zum Berechnen von det(A).

2.7 Der Gauß Algorithmus ist schnell, hat aber den Nachteil, dass beim Rechnen mit rationalen Zahlen, Zähler und Nenner sehr schnell sehr groß werden. Fazit: Der Gauß Algorithmus ist ein sehr guter Algorithmus für endliche Körper.

2.9 Hadamard Schranke S für die Determinante

2.10 Berechnung der Determinante einer ganzzahligen Matrix A mit dem chinesischen Restsatz: Idee: Berechen d_{i} := det(A (mod p_{i})) für Primzahlen p_{1}, …, p_{k} und bestimme dann d ∈ ℤ |d| < S (aus 2.9) mit d ≡ d_{i} (mod p_{i}).

2.12 Im Prinzip kann man mit 2.10 auch die Adjungierte von A bestimmen. Zum Invertieren gibt es jedoch einen besseren Algorithmus:

2.13 Algorithmus (p-adisches Invertieren von Matrizen)

Eingabe: A ∈ ℤ^{n×n} ∩ GL_{n}(ℚ), λ ∈ ℤ mit λA^{−1} ∈ ℤ^{n×n}. Ausgabe: λA^{−1}. Idee: Wähle p > 2 Primzahl, mit p | λ̸. Berechne X ∈ ℤ^{n×n} mit X ≡ A^{−1} (mod p). (Arbeite immer mit dem betragsmäßig kleinsten Rest modulo p^{k}.) Setze B^{(0)} := λX (mod p). Bestimme induktiv B^{(k)} ∈ ℤ^{n×n} mit B^{(k)}A ≡ I_{n} (mod p^{k+1}): Ist B^{(k−1)} schon bestimmt so ist eine Matrix C^{(k)} gesucht, mit

B^{(k)} = B^{(k−1)} + p^{k}C^{(k)}.

Ist

B^{(k−1)}A = λI_{n} + p^{k}R^{(k−1)}

so ergibt sich

B^{(k)}A = (B^{(k−1)} + p^{k}C^{(k)})A = λI_{n} + p^{k}(R^{(k−1)} + C^{(k)}A).

Also ist

C^{(k)} ≡ −R^{(k−1)}X (mod p).

(Zum Algorithmus vgl. auch die MAPLE Programme.)

Kennt man in 2.13 die Zahl λ nicht, so kann man trotzdem den Algorithmus verwenden. Man rechnet dann aber rationale Zahlen (die Einträge von A^{−1}) modulo p^{k} aus. Zur Bestimmung kleiner a, b ∈ ℤ mit \frac{a}{b} ≡ c (mod p^{k}) benutzt man den folgenden Algorithmus:

2.15 Algorithmus zur rationalen Approximation einer Zahl modulo N. Eingabe: c ∈ ℤ, N ∈ ℕ. Ausgabe: a, b ∈ ℤ mit a ≡ cb (mod N) und a^{2} + b^{2} minimal. Idee: Sei L := {(a, b) ∈ ℤ^{2} | a ≡ cb (mod N)}. Dann ist L = ℤ(c, 1) ⊕ ℤ(N, 0) ein Gitter im Euklidischen Raum (ℝ^{2}, x^{2} + y^{2}). Gesucht ist ein kurzer Vektor in L. Zum Finden dieses Vektors benutzen wir die sogenannte Paarreduktion:

2.16 Paarreduktion:

Eingabe: L = ℤv_{1} ⊕ ℤv_{2} Gitter im Euklidischen Raum (ℝ^{2}, Φ). Ausgabe: 0 ≠ v ∈ L mit Φ(v, v) minimal. Algorithmus:

(1) Ist Φ(v_{1}, v_{1}) > Φ(v_{2}, v_{2}), so vertausche v_{1} und v_{2}.

(2) Ist |Φ(v_{1}, v_{2})| > \frac{1}{2}Φ(v_{1}, v_{1}), so setze k := ⌊\frac{Φ(v_{1},v_{2})}{Φ(v_{1},v_{1})}⌋ und v_{2} := v_{2} − kv_{1} und gehe zu Schritt (1). Sonst gibt v = v_{1} aus. (Zum Algorithmus vgl. auch die MAPLE Programme.)

Abschnitt 3: Gitter und der LLL-Algorithmus.

Generalvoraussetzung: (V, Φ) ist ein Euklidischer Vektorraum, d.h. V ≅ ℝ^{n} und Φ : V × V → ℝ positiv definite symmetrische Bilinearform.

3.1 Definition: Gitter, Gitterbasis

3.2 Basiswechsel in Gittern, Determinante eines Gitters.

3.3 Das Gram-Schmidt-Orthogonalisierungsverfahren: Eingabe: Eine Basis (b_{1}, …, b_{n}) von V. Ausgabe: Eine Orthogonalbasis B^{∗} := (b_{1}^{∗}, …, b_{n}^{∗}) von V. Algorithmus: Für i = 1, …, n berechne sukzessive

b_{i}^{∗} := b_{i} − ∑_{j=1}^{i−1} μ_{ij}b_{j}^{∗}

wo μ_{ij} = \frac{Φ(b_{i},b_{j}^{∗})}{Φ(b_{j}^{∗},b_{j}^{∗})}. Achtung, die μ_{ij} habe ich in der Vorlesung k_{ij} genannt! b_{i}^{∗} ist die Projektion von b_{i} auf ⟨b_{1}, …, b_{i−1}⟩^{⊥}. Die von B und B^{∗} erzeugten Gitter haben die gleiche Determinante, nämlich ∏_{j=1}^{n} Φ(b_{j}^{∗}, b_{j}^{∗}). Da Φ(b_{j}^{∗}, b_{j}^{∗}) ≤ Φ(b_{j}, b_{j}) ist, ergibt sich 3.4:

3.4 Folgerung: Die Hadamard Ungleichung:

Ist (b_{1}, …, b_{n}) eine Gitterbasis von L, so ist det(L) ≤ ∏_{j=1}^{n} Φ(b_{j}, b_{j}).

3.5 Satz: L_{≤S} := {v ∈ L | Φ(v, v) ≤ S} ist endlich. Zum Beweis:

3.6 Algorithmus zum Auflisten kurzer Vektoren in Gittern Idee: Sei B eine Gitterbasis von L und B^{∗}, μ_{ij} wie in (3.3). Ist v = ∑_{j=1}^{n} a_{j}b_{j} ∈ L, so ist v = ∑_{j=1}^{n} α_{j}b_{j}^{∗} mit α_{j} ∈ ℝ, α_{n} = a_{n}, α_{n−1} = a_{n−1} − μ_{n,n−1}a_{n}, … Aus

Φ(v, v) = ∑_{j=1}^{n} α_{j}^{2}Φ(b_{j}^{∗}, b_{j}^{∗}) ≤ S

folgt insbesondere a_{n}^{2}Φ(b_{n}^{∗}, b_{n}^{∗}) ≤ S. Also hat man nur endlich viele Möglichkeiten für a_{n} ∈ ℤ. Allgemein gilt

α_{j}^{2}Φ(b_{j}^{∗}, b_{j}^{∗}) = (a_{j} − ∑_{i=j+1}^{n} μ_{i,j}a_{i})^{2}Φ(b_{j}^{∗}, b_{j}^{∗}) ≤ S − ∑_{i=j+1}^{n} α_{i}^{2}Φ(b_{i}^{∗}, b_{i}^{∗})

woraus man sukzessiv nur endlich viele Möglichkeiten für a_{j} ∈ ℤ, j = n, n − 1, …, 1 erhält.

3.7 Algorithmus zum Auflisten kurzer Vektoren in Gittern Eingabe: Eine Gitterbasis B eines Gitters L in (ℝ^{n}, Φ) (oder Φ(B) eine Grammatrix von L) und Schranke S ∈ ℝ sowie Parameter ϵ := 0.0001 um Rundungsfehler zu vermeiden. Ausgabe: Liste K von Koordinatenvektoren (a_{1}, …, a_{n}) ∈ ℤ^{n}, so dass

L_{≤S} = {0} ∪ {±v | v = ∑_{i=1}^{n} a_{i}b_{i}, (a_{1}, …, a_{n}) ∈ K}.

Algorithmus:

(1) (Gram-Schmidt)

Berechne μ_{ij} (1 ≤ j < i ≤ n) und

g_{i} := Φ(b_{i}^{∗}, b_{i}^{∗}) (1 ≤ i ≤ n) wie in Lemma (3.3).

(2) (Initialisieren)

Setze k := n; f_{k} := 0;

(3) (Bestimme maximales a_{k}) u_{k} := ∑_{j=k+1}^{n} μ_{kj}a_{j}; h := round(u_{k}); while ((g_{k}(h − u_{k})^{2} ≤ S − f_{k} + ϵ) or ((h − u_{k}) < 0)) do

h := h + 1;

end while; a_{k} := h + 1;

(4) (Schleife über alle a_{k}) a_{k} := a_{k} − 1; if (g_{k}(a_{k} − u_{k})^{2} ≤ S − f_{k} + ϵ) then

if (k = 1) then
if ((a_{1}, …, a_{n}) = (0, …, 0)) then RETURN;
else Ausgabe von (a_{1}, …, a_{n}) =: v
und Φ(v, v) = f_{1} + g_{1}(a_{1} + u_{1})^{2}; goto (4);

end if; else f_{k−1} := f_{k} + g_{k}(a_{k} + u_{k})^{2}; k := k − 1; goto (3);

end if; else k:=k+1; goto (4); end if;

3.8 Satz (Hermite Ungleichung): Sei L ⊆ V ein Gitter. Dann gibt es eine Gitterbasis B = (b_{1}, …, b_{n}) von L so dass

∏_{i=1}^{n} Φ(b_{i}, b_{i}) ≤ \frac{4}{3}^{n(n−1)/2} det(L).

Beweisidee: Zeige zunächst

3.9 Lemma: Sei v ∈ L mit Φ(v, v) = min{Φ(l, l) | 0 ≠ l ∈ L} =: min(L) und π : V → v^{⊥} die Orthogonalprojektion auf v^{⊥}. Ist x ∈ π(L), so gibt es ein x_{1} ∈ L mit π(x_{1}) = x und Φ(x_{1}, x_{1}) ≤ 4/3Φ(x, x). Beweis: Sei x_{1} ∈ L so, dass x_{1} − π(x_{1}) = sv mit |s| ≤ 1/2. Dieses x_{1} erfüllt die Behauptung.

Beweis von 3.8 Induktion über n: n = 1 ist trivial. (n − 1) ⇒ n: Wähle b_{1} ∈ L mit Φ(b_{1}, b_{1}) = min(L). Sei π : V → b_{1}^{⊥} wie in (3.9) und L′ := π(L). Nach Induktion gibt es eine Gitterbasis (b′_{2}, …, b′_{n}) mit ∏_{i=2}^{n} Φ(b′_{i}, b′_{i}) ≤ \frac{4}{3}^{(n−1)(n−2)/2} det(L′). Für i = 2, …, n sei b_{i} ∈ L mit π(b_{i}) = b′_{i} und Φ(b_{i}, b_{i}) ≤ 4/3Φ(b′_{i}, b′_{i}). Dann ist (b_{1}, …, b_{n}) eine Gitterbasis von L (Übung 3, Aufgabe 11). Da det(L′)Φ(b_{1}, b_{1}) = det(L) (Übung 3, Aufgabe 11), erfüllt die Basis (b_{1}, …, b_{n}) die Behauptung von (3.8).

3.10 Definition: (vgl. Lenstra, Lenstra, Lovasz: Math. Annalen 261, 515-534 (1982)) Eine Gitterbasis B := (b_{1}, …, b_{n}) eines Gitters L heißt LLL-reduziert (zum Parameter \frac{3}{4}), falls für die μ_{ij} und b_{i}^{∗} aus (3.3) gilt:

(a) |μ_{ij}| ≤ 1/2 für alle 1 ≤ j < i ≤ n

(b) Φ(b_{i}^{∗}, b_{i}^{∗}) + μ_{i,i−1}^{2}Φ(b_{i−1}^{∗}, b_{i−1}^{∗}) ≥ \frac{3}{4}Φ(b_{i−1}^{∗}, b_{i−1}^{∗}) für alle i = 2, …, n.

(Die Bedingung (b) sagt aus, dass die Projektion von b_{i} auf ⟨b_{1}, …, b_{i−2}⟩^{⊥} nicht wesentlich kürzer ist als die Projektion von b_{i−1} auf denselben Raum.) Den Parameter 3/4 in (b) kann man durch eine beliebige reelle Zahl α ∈ (1/4, 1) ersetzen.

3.11 Satz: Sei B = (b_{1}, …, b_{n}) eine LLL-reduzierte Basis des Gitters L und (b_{1}^{∗}, …, b_{n}^{∗}) wie in (3.3). Dann gilt:

(i) Φ(b_{j}, b_{j}) ≤ 2^{i−1}Φ(b_{i}^{∗}, b_{i}^{∗}) für alle 1 ≤ j ≤ i ≤ n.

(ii) det(L) ≤ ∏_{i=1}^{n} Φ(b_{i}^{∗}, b_{i}^{∗}) ≤ 2^{n(n−1)/2} det(L).

(iii) Φ(b_{1}, b_{1}) ≤ 2^{(n−1)/2} det(L)^{1/n}.

Ersetzt man den Parameter 3/4 in (3.10) (b) durch ein α mit 1/4 < α < 1, so gelten analoge Aussagen zu (3.11) (i), (ii), (iii) in denen man 2 durch 4/(4α − 1) ersetzt. Beweis: (i)

Φ(b_{i}^{∗}, b_{i}^{∗}) ≥ 1/2Φ(b_{i−1}^{∗}, b_{i−1}^{∗})

für alle 2 ≤ i ≤ n nach (3.10) (a) und (b). Also folgt durch Induktion:

Φ(b_{j}^{∗}, b_{j}^{∗}) ≤ 2^{i−j}Φ(b_{i}^{∗}, b_{i}^{∗})

für alle 1 ≤ j ≤ i ≤ n. Daraus ergibt sich

Φ(b_{i}, b_{i}) = Φ(b_{i}^{∗}, b_{i}^{∗}) + ∑_{j=1}^{i−1} μ_{ij}^{2}Φ(b_{j}^{∗}, b_{j}^{∗}) ≤

Φ(b_{i}^{∗}, b_{i}^{∗})(1 + 1/4 ∑_{j=1}^{i−1} 2^{i−j}) = Φ(b_{i}^{∗}, b_{i}^{∗})(1 + 1/4 · (2^{i} − 2)) ≤ 2^{i−1}Φ(b_{i}^{∗}, b_{i}^{∗}).

Also Φ(b_{j}, b_{j}) ≤ 2^{j−1}Φ(b_{j}^{∗}, b_{j}^{∗}) ≤ 2^{i−1}Φ(b_{i}^{∗}, b_{i}^{∗}) für alle 1 ≤ j ≤ i ≤ n. (ii) Die linke Ungleichung ist die Hadamard Schranke (3.4). Die rechte ergibt sich aus (i):

det(L) = ∏_{j=1}^{n} Φ(b_{j}^{∗}, b_{j}^{∗}) ≥ ∏_{j=1}^{n} \frac{1}{2^{j−1}} Φ(b_{j}, b_{j}) = 2^{−n(n−1)/2} ∏_{j=1}^{n} Φ(b_{j}, b_{j}).

(iii) Folgt direkt aus (i), da

Φ(b_{1}, b_{1})^{n} ≤ ∏_{i=1}^{n} 2^{i−1}Φ(b_{i}^{∗}, b_{i}^{∗}) = 2^{n(n−1)/2} det(L).

3.12 Folgerung: Ist (b_{1}, …, b_{n}) eine LLL-reduzierte Basis des Gitters L, so ist

Φ(b_{1}, b_{1}) ≤ 2^{n−1}Φ(x, x)

für alle 0 ≠ x ∈ L. Beweis: Sei x = ∑_{i=1}^{n} a_{i}b_{i} = ∑_{i=1}^{n} α_{i}b_{i}^{∗} mit a_{i} ∈ ℤ, α_{i} ∈ ℝ (1 ≤ i ≤ n). Ist i maximal mit a_{i} ≠ 0, so ist α_{i} = a_{i} und Φ(x, x) ≥ a_{i}^{2}Φ(b_{i}^{∗}, b_{i}^{∗}) ≥ Φ(b_{i}^{∗}, b_{i}^{∗}) ≥ 1/2^{i−1}Φ(b_{1}, b_{1}) ≥ 1/2^{n−1}Φ(b_{1}, b_{1}).

3.13 Satz: Jedes Gitter L hat eine LLL-reduzierte Basis.

Zum Beweis:

3.14 Algorithmus: (LLL-Reduktion)

Eingabe: Gitterbasis (b′_{1}, …, b′_{n}) von L. Ausgabe: LLL-reduzierte Gitterbasis (b_{1}, …, b_{n}) von L und Transformationsmatrix T = (t_{ij}) ∈ GL_{n}(ℤ) mit b_{i} = ∑_{j=1}^{n} t_{ij}b′_{j}. Idee: Iteration über k: Im Schritt k gilt, dass (b_{1}, …, b_{k−1}) eine LLL-reduzierte Basis ist. Man startet mit k = 2. Ist k = n + 1, so ist man fertig. T_{k} bezeichne die k-te Zeile von T.

Algorithmus: T := I_{n}; b_{i} := b′_{i} (1 ≤ i ≤ n); k := 2; while (k ≤ n) do

if (k ≥ 2) then μ_{k,k−1} := Φ(b_{k}, b_{k−1}^{∗})/Φ(b_{k−1}^{∗}, b_{k−1}^{∗});

if (|μ_{k,k−1}| > 1/2) then r := round(μ_{k,k−1}); b_{k} := b_{k} − rb_{k−1};

T_{k} := T_{k} − rT_{k−1}; end if;

for j = 1, …, k − 2 do μ_{k,j} := Φ(b_{k}, b_{j}^{∗})/Φ(b_{j}^{∗}, b_{j}^{∗}); end for; b_{k}^{∗} := b_{k} − ∑_{j=1}^{k−1} μ_{k,j}b_{j}^{∗}; Teste Bedingung (3.10) (b) für i = k. Fall 1: nicht erfüllt

vertausche b_{k} und b_{k−1} und T_{k} und T_{k−1}; k := k − 1; end Fall 1; Fall 2: erfüllt

for j = k − 2, …, 1 do r := round(μ_{k,j}); b_{k} := b_{k} − rb_{j}; T_{k} := T_{k} − rT_{j}; μ_{k,j} := μ_{k,j} − r; for l = 1, …, j − 1 do μ_{k,l} := μ_{k,l} − rμ_{j,l}; end for;

end for; k:=k+1;

end Fall 2; else k:=k+1; end if;

k := k + 1; end while;

3.15 Bemerkung: Algorithmus (3.14) läßt sich so umformulieren, dass er nur mit Grammatrizen arbeitet.

3.16 Satz: Algorithmus (3.14) terminiert.

Beweis: Sei d_{k} := det(Φ(b_{i}, b_{j})_{1≤i,j≤k}) Setzt man L_{k} := ⟨b_{1}, …, b_{k}⟩_{ℤ} so ist d_{k} = det(L_{k}) = ∏_{j=1}^{k} Φ(b_{j}^{∗}, b_{j}^{∗}). Es gilt d_{0} = 1, d_{n} = det(L), d_{k} ∈ ℝ_{>0}. Ist m := min(L), so ist nach der Hermite Ungleichung (3.8) d_{k} ≥ \frac{3}{4}^{k(k−1)/2}m^{k} durch eine positive Zahl nach unten beschränkt. Sei D := ∏_{k=1}^{n−1} d_{k}. Dann ändert sich D nur dann, wenn sich ein Φ(b_{j}^{∗}, b_{j}^{∗}) ändert, also nur im Fall 1. Dann wird aber d_{k−1} mit einem Faktor < 3/4 multipliziert. d_{j} bleibt gleich für j ≠ k − 1 da die Menge {b_{1}, …, b_{j}} und damit auch L_{j} gleich bleibt. Also wird im Fall 1 die Zahl D mit einem Faktor < 3/4 multipliziert. D ist durch eine positive nach unten beschränkt, also tritt Fall 1 nur endlich oft auf und der Algorithmus terminiert.

3.17 MLLL-Algorithmus (=modifizierter LLL-Algorithmus (M. Pohst))

Algorithmus (3.14) kann so abgeändert werden, dass er mit linear abhängigen Vektoren arbeitet. Eingabe: Teilmenge (b′_{1}, …, b′_{m}) von V. Ausgabe: LLL-reduzierte Menge (b_{1}, …, b_{m}) mit L := ⟨b′_{1}, …, b′_{m}⟩_{ℤ} = ⟨b_{1}, …, b_{m}⟩_{ℤ} und eine Transformationsmatrix T = (t_{ij}) ∈ GL_{m}(ℤ) mit b_{i} = ∑_{j=1}^{m} t_{ij}b′_{j}. Idee: Verfahre wie in (3.14) mit dem folgenden Unterschied: Ist Φ(b_{k}^{∗}, b_{k}^{∗}) = 0 (also b_{k}^{∗} = 0, d.h. b_{k} ist ℝ-linear abhängig von b_{1}, …, b_{k−1}), so ist b_{k}^{∗} im Gram-Schmidt-Verfahren überflüssig. Setze also μ_{l,k} = 0 für alle l = k + 1, …, m. Algorithmus: Übung

3.18 Bemerkung: Der MLLL-Algorithmus terminiert.

Beweis: Analog zum Beweis von (3.16). Sei g_{i} := Φ(b_{i}^{∗}, b_{i}^{∗}) und

d_{k} := ∏_{i≤k,g_{i}≠0} g_{i}, D := ∏_{k≤m,g_{k}≠0} d_{k} ∏_{k≤m,g_{k}=0} 2^{k}.

D wird nur im Fall 1 verändert. Ist g_{k} ≠ 0, so wird D mit einem Faktor ≤ 3/4 multipliziert, wie in (3.16). Ist g_{k} = 0, so werden b_{k} und b_{k−1} vertauscht. d_{k−1} wird auf d_{k−2} gesetzt, d_{k} bleibt gleich und D wird insgesamt mit einem Faktor 2^{k−1}/2^{k} = 1/2 < 1 multipliziert. Wie in (3.16) ist D durch eine positive Zahl (min(L)^{dim(L)}2^{m−dim(L)}) nach unten beschränkt. Also tritt Fall 1 nur endlich oft ein und (3.17) terminiert.

3.19 Bemerkung: Sei n := dim(⟨b′_{1}, …, b′_{m}⟩_{ℝ}). Dann gilt für die in (3.17) berechneten Vektoren (b_{1}, …, b_{m}): b_{1} = … = b_{m−n} = 0 und (b_{m−n+1}, …, b_{m}) ist eine LLLreduzierte Gitterbasis von L.

3.20 Anwendung des LLL-Algorithmus: Bestimmen kurzer Vektoren in Gittern: z.B. Finden ℤ-linearer Abhängigkeiten komplexer Zahlen. Eingabe: z_{1}, …, z_{n} ∈ ℂ (bzw. gute Approximationen). Ausgabe: a_{1}, …, a_{n} ∈ ℤ mit ∑_{i=1}^{n} a_{i}z_{i} = 0. Idee: Formuliere das Problem so um, dass (a_{1}, …, a_{n}) ein kurzer Vektor in einem Gitter ist. Zunächst sei angenommen, dass z_{1}, …, z_{n} ∈ ℝ, z_{1} ≠ 0. Wähle N ∈ ℝ_{>0} groß und definiere

Φ : ℝ^{n} × ℝ^{n} → ℝ, Φ(x, y) := ∑_{j=2}^{n} x_{j}y_{j} + N(∑_{i=1}^{n} z_{i}x_{i})(∑_{i=1}^{n} z_{i}y_{i}).

Dann ist Φ positiv definit. Sei L = ℤ^{n}. Ist a = (a_{1}, …, a_{n}) ∈ L, mit Φ(a, a) klein, so gilt, falls N groß genug ist, dass ∑_{i=1}^{n} a_{i}z_{i} sehr nahe bei 0 ist. Falls ein z_{i}/z_{1} nicht in ℝ liegt, so nehmen wir an, dass z_{2}/z_{1} ∈ ℂ\ℝ. Dann definieren wir

Φ : ℝ^{n} × ℝ^{n} → ℝ, Φ(x, y) := ∑_{j=3}^{n} x_{j}y_{j} + NRe((∑_{i=1}^{n} z_{i}x_{i})(∑_{i=1}^{n} z̄_{i}y_{i}))

und verfahren wie eben.

3.21 Bemerkung: (3.20) kann man auch benutzen, um ℤ-lineare Abhängigkeit von Vektoren z_{1}, …, z_{n} ∈ ℂ^{k} zu finden.

3.22 Anwendung von (3.20): Faktorisieren von Polynomen.

Eingabe: f ∈ ℤ[x] Polynom und numerische Approximation einer komplexen Nullstelle z ∈ ℂ mit f(z) = 0.

Ausgabe: h, g ∈ ℤ[x] mit f = hg. Idee: In der obigen Faktorisierung gilt entweder h(z) = 0 oder g(z) = 0, d.h. die Koeffizienten von h oder g liefern eine ℤ-lineare Abhängigkeit der Potenzen von z. Solche Koeffizienten lassen sich also mit Algorithmus (3.20) bestimmen.

Abschnitt 4: Faktorisieren von Polynomen.

Fragestellung: Gegeben ist ein normiertes Polynom f = f(X) ∈ ℤ[X]. Gesucht sind irreduzible normierte Polynome p_{1}, …, p_{s} ∈ ℤ[X] mit f = p_{1} … p_{s}. Die grobe Strategie zum Faktorisieren von f besteht darin, zunächst f über einem endlichen Körper ℤ/pℤ zu faktorisieren (Abschnitt A), diese Faktorisierung zu einer Faktorisierung von f modulo p^{k} hochzuliften (Abschnitt B) und dann, z.B. mit Hilfe des LLL-Algorithmus, daraus eine Faktorisieung von f ∈ ℤ[X] herzustellen (Abschnitt C). Teil A: Endliche Körper. Sei p eine Primzahl und 𝔽_{p} := ℤ/pℤ.

4.1 Satz: Sei G eine endliche Gruppe, n := |G|. Ist a ∈ G, so gilt a^{n} = 1.

Beweis: U := {1, a, a^{2}, …} ⊂ G, also gibt es i < j mit a^{i} = a^{j} ⇔ a^{j−i} = 1. Sei e > 0 minimal mit a^{e} = 1. Dann ist |U| = e. Ist U ≠ G, so gibt es b := b_{1} ∈ G \ U. Dann gilt für bU := {b, ba, …, ba^{e−1}}, |bU| = e und bU ∩ U = ∅. Ist b_{2} ∈ G \ (bU ∪ U), so gilt b_{2}U ∩ (U ∪ b_{1}U) = ∅ etc. Erhalten so eine Menge {1 =: b_{0}, b_{1}, b_{2}, …, b_{s}} ⊂ G mit G =∪^{.}_{j=0}^{s} b_{s}U. Also ist n = (s + 1)e und a^{n} = (a^{e})^{s+1} = 1. Nun kommen wir zum Faktorisieren von Polynomen ∈ 𝔽_{p}[X].

4.2 Bemerkung: Sei f ∈ 𝔽_{p}[X]. Das Faktorisieren geschieht in 3 Schritten: (a) Quadratfreie Faktorisierung: Finde quadratfreie, paarweise teilerfremde Polynome f_{i} ∈ 𝔽_{p}[X] (1 ≤ i ≤ k), so dass

f = f_{1}f_{2}^{2}f_{3}^{3} … f_{k}^{k}.

(b) Verschiedene Grade: Finde Polynome f_{i,d} ∈ 𝔽_{p}[X], so dass

f_{i,d} = ∏{q | q ∈ 𝔽_{p}[X], Grad(q) = d, q ist irreduzibler Faktor von f_{i}}.

(c) Endgültige Faktorisierung: Faktorisiere f_{i,d} in Grad(f_{i,d})/d verschiedene irreduzible Faktoren vom Grad d.

(a) Quadratfreie Faktorisierung.

4.3 Lemma: Sei f = f_{1}f_{2}^{2} … f_{k}^{k} wie in (4.2) (a). Dann ist ggT(f, f′) = ∏_{p | i̸} f_{i}^{i−1} ∏_{p|i} f_{i}^{i}.

4.4 Bemerkung: Lemma (4.3) gilt analog über allen perfekten Körpern, also z.B. auch für ℚ[X], wo es dann keine Fallunterscheidung (p | i) gibt.

4.5 Strategie: (Quadratfreie Faktorisierung):

Setze T_{1} := ggT(f, f′), V_{1} := f/T_{1} = ∏_{p | i̸} f_{i}. Für m ≥ 2 sei V_{m} := ggT(V_{m−1}, T_{m−1}), falls p | m̸ und V_{m} := V_{m−1} sonst. Setze T_{m} := T_{m−1}/V_{m}. Dann gilt

V_{m} = ∏_{i≥m,p | i̸} f_{i}, T_{m} = ∏_{i>m,p | i̸} f_{i}^{i−m} ∏_{p|i} f_{i}^{i}.

Deshalb ist f_{m} = V_{m−1}/V_{m} für alle m mit p | m̸. Am Ende ist V_{k+1} konstant und T_{k−1} = ∏_{p|i} f_{i} eine p-te Potenz. Nun bestimmt man die p-te Wurzel aus T_{k−1}, was in 𝔽_{p}[X] ganz einfach geht:

4.6 Lemma: Die Abbildung F : 𝔽_{p}[X] → 𝔽_{p}[X], q ↦ q^{p} ist 𝔽_{p}-linear. Insbesondere ist q(X)^{p} = q(X^{p}). Beweis: Seien q_{1}, q_{2} ∈ 𝔽_{p}[X], a, b ∈ 𝔽_{p}. Dann ist (aq_{1}+bq_{2})^{p} = ∑_{j=0}^{p} \binom{p}{j}a^{j}q_{1}^{j}b^{p−j}q_{2}^{p−j} = a^{p}q_{1}^{p} + b^{p}q_{2}^{p} = aq_{1}^{p} + bq_{2}^{p} mit Satz (4.1). Ein expliziter Algorithmus zu (4.5) wird in der Übung entwickelt.

(b) verschiedene Grade:

4.7 Satz: Zu jedem d ∈ ℕ gibt es (bis auf Isomorphie) genau einen Körper 𝔽_{p^{d}} mit p^{d} Elementen, nämlich den Zerfällungskörper von ϕ_{d}(X) := X^{p^{d}} − X ∈ 𝔽_{p}[X] über 𝔽_{p}. Beweis: Sei K ein Körper, |K| = p^{d}. Dann gilt für alle a ∈ K, dass a^{p^{d}} = a. Dies ist klar für a = 0. Ist a ≠ 0, so ist a eine Einheit in K, also a ∈ K^{∗}. Die Einheitengruppe K^{∗} ist eine endliche Gruppe der Ordnung p^{d} − 1. Also gilt a^{p^{d}−1} = 1 nach Satz (4.1). Multiplikation mit a liefert a^{p^{d}} = a. Jetzt definieren wir einen Homomorphismus: ι : 𝔽_{p} = ℤ/pℤ → K, 1 + pℤ ↦ 1_{K}. Wir müssen zeigen, dass ι wohldefiniert ist. Dazu betrachten wir die additive Gruppe (K, +). Nach Satz (4.1) gilt |K|1 = 1 + … + 1 = 0 (|K| Summanden) also p^{d} · 1 = (p · 1) … (p · 1) = 0. Da K nullteilerfrei ist, folgt als p · 1 = 0 und ι ist wohldefiniert. Für das Polynom ϕ_{d}(X) ∈ 𝔽_{p}[X] gilt, dass ggT(ϕ_{d}(X), ϕ′_{d}(X)) = ggT(X^{p^{d}}−X, −1) = 1. Also hat ϕ_{d} in seinem Zerfällungskörper keine mehfachen Nullstellen und K besteht gerade aus den p^{d} verschiedenen Nulstellen von ϕ_{d}.

4.8 Folgerung: Sei f ∈ 𝔽_{p}[X] ein irreduzibles Polynom vom Grad d. Dann ist 𝔽_{p}[X]/(f(X)) ≅ 𝔽_{p^{d}}. Das Produkt aller irreduziblen Polynome in 𝔽_{p}[X] vom Grad d ist

ϕ_{d}(X)/ggT(ϕ_{d}(X), ∏_{j=1}^{d−1} ϕ_{j}(X)).

4.9 Algorithmus zur Bestimmung der f_{i,d} aus (4.2) (b):

Eingabe: quadratfreies Polynom f ∈ 𝔽_{p}[X]. Ausgabe: f_{1}, …, f_{k} mit f_{d} = ∏{q ∈ 𝔽_{p}[X] | q | f, q irreduzibel vom Grad d}. Algorithmus: for j from 1 to Grad (f) do

f_{j} := ggT(f, X^{p^{j}} − X);
f := f/f_{j};

end for;

(c) endgültige Faktorisierung:

4.10 Lemma: Sei p > 2, A ∈ 𝔽_{p}[X] Produkt von verschiedenen irreduziblen Polynomen von Grad d. Dann ist für alle T ∈ 𝔽_{p}[X]

A = ggT(A, T)ggT(A, T^{(p^{d}−1)/2} − 1)ggT(A, T^{(p^{d}−1)/2} + 1).

Beweis: In 𝔽_{p^{d}}[X] zerfällt A in Linearfaktoren. Ist α ∈ 𝔽_{p^{d}}, so ist auch T (α) ∈ 𝔽_{p^{d}} und deshalb

(T^{p^{d}} − T)(α) = T (α)^{p^{d}} − T (α) = 0

mit Satz (4.7). Also teilt jeder der Linearfaktoren von A ∈ 𝔽_{p^{d}}[X] genau einen der 3 paarweis teilerfremden Faktoren T, T^{(p^{d}−1)/2} − 1, T^{(p^{d}−1)/2} + 1 von T^{p^{d}} − T und deshalb teilt auch jeder irreduzible Faktor von A ∈ 𝔽_{p}[X] genau eines dieser drei Polynome. Da A quadratfrei ist, folgt die Behauptung. Ist A nicht irreduzibel, so ist die Wahrscheinlichkeit, dass ggT(A, T^{(p^{d}−1)/2} − 1) ein nichttrivialer Teiler von A ist, recht gross (∼ 1/2). Daraus ergibt sich folgender rekursiver, probabilistischer Algorithmus:

4.11 Algorithmus (Cantor, Zassenhaus) (p > 2)

Eingabe: A ∈ 𝔽_{p}[X] Produkt von mindestens zwei verschiedenen irreduziblen Polynomen vom Grad d. Ausgabe: Ein nichttrivialer Faktor B von A = B \frac{A}{B}. Algorithmus: k := Grad(A); while (TRUE) do

Wähle zufällig T ∈ 𝔽_{p}[X] mit Grad(T) ≤ 2d − 1;

Berechne B := ggT(T^{(p^{d}−1)/2}, A) mit dem Euklidischen Algorithmus; if k > Grad(B) > 0 then RETURN(B); end if;

end while; Einen analogen Algorithmus gibt es auch für p = 2. Für kleine Primzahlen ist jedoch der Berlekamp-Algorithmus besser:

4.12 Lemma:

Sei A ∈ 𝔽_{p}[X] quadratfrei, A = ∏_{i=1}^{r} A_{i} eine Zerlegung von A in irreduzible Faktoren. Dann ist

{T ∈ 𝔽_{p}[X] | T^{p} ≡ T (mod A)} = {T ∈ 𝔽_{p}[X] |

es gibt Konstanten s_{1}, …, s_{r} ∈ 𝔽_{p} mit T ≡ s_{i} (mod A_{i}) für alle 1 ≤ i ≤ r}.

Beweis: Nach dem chinesischen Restsatz ist der Ring

𝔽_{p}[X]/(A) ≅ ⨁_{i=1}^{r} 𝔽_{p}[X]/A_{i} ≅ ⨁_{i=1}^{r} 𝔽_{p^{d_{i}}}

wo d_{i} = Grad(A_{i}). Die Elemente T ∈ 𝔽_{p}[X]/(A) mit T^{p} = T sind nach Satz (4.7) genau die Elemente in ⊕_{i=1}^{r}𝔽_{p}.

4.13 Strategie: (Berlekamp Algorithmus)

Sei A ∈ 𝔽_{p}[X] quadratfrei, n := Grad(A). Bestimme zunächst eine 𝔽_{p}-Basis von M := {T ∈ 𝔽_{p}[X] | Grad(T) < n, T^{p} ≡ T (mod A)}: Ist T (X) = ∑_{j=0}^{n−1} t_{j}X^{j} ∈ M, so ist T^{p}(X) = T (X^{p}) = ∑_{j=0}^{n−1} t_{j}X^{pj}. Berechne also die Matrix Q = (q_{ji}) ∈ 𝔽_{p}^{n×n} mit

X^{pj} ≡ ∑_{i=0}^{n−1} q_{ji}X^{i} (mod A).

Dann gilt T^{p} ≡ T (mod A) ⇔ (t_{0}, …, t_{n−1}) ∈ Kern(Q − I_{n}). Bestimme also eine 𝔽_{p}-Basis von Kern(Q − I_{n}) mit dem Gauß Algorithmus. Da 1^{p} = 1 gilt 𝔽_{p} ⊂ M (d.h. (1, 0, …, 0) ∈ Kern(Q − I_{n})). Jeder von 1 l.u. Vektor t ∈ Kern(Q−I_{n}) entspricht aber einem nicht konstanten T ∈ M, für das Konstanten s_{i} ∈ 𝔽_{p} existieren mit T ≡ s_{i} (mod A_{i}). Die s_{i} ∈ 𝔽_{p} sind nicht alle gleich und

A = ∏_{s∈𝔽_{p}} ggT(T − s, A)

ist eine nichttriviale Faktorisierung von A. Daraus ergibt sich ein expliziter deterministischer Algorithmus, den wir in der Übung besprechen.

Teil B) Liften modulo p^{k}

4.14 Satz: (Hensel’sches Lemma)

Seien k ≥ 1, A, B_{k}, C_{k}, U, V ∈ ℤ[X] mit Grad(A) = Grad(B_{k}) + Grad(C_{k}), B_{k} normiert, Grad(U) < Grad(C_{k}), Grad(V) < Grad(B_{k}) die die Bedingungen

⋆_{k} : A ≡ B_{k}C_{k} (mod p^{k}), UB_{k} + V C_{k} ≡ 1 (mod p)

erfüllen. Dann gibt es (modulo p^{k+1} eindeutig bestimmte) Polynome B_{k+1}, C_{k+1} ∈ ℤ[X], B_{k+1} ≡ B_{k} (mod p^{k}), normiert, C_{k+1} ≡ C_{k} (mod p^{k}), Grad(B_{k}) = Grad(B_{k+1}), Grad(C_{k}) = Grad(C_{k+1}) die ⋆_{k+1} erfüllen. Beweis: Sei B_{k}C_{k} = A − R_{k}. Setzen an: B_{k+1} := B_{k} + p^{k}S, C_{k+1} := C_{k} + p^{k}T. Da

B_{k+1}C_{k+1} = (B_{k}+p^{k}S)(C_{k}+p^{k}T) ≡ C_{k}B_{k}+p^{k}(C_{k}S+B_{k}T) = A+p^{k}(C_{k}S+B_{k}T −R_{k})

modulo p^{2k}, sagt ⋆_{k+1}, dass C_{k}S + B_{k}T ≡ R_{k} (mod p) sein muss. Setzen also S := R_{k}V + W B_{k} (mod p) mit W ∈ ℤ[X], so dass Grad(S) < Grad(B_{k}) und T := R_{k}U − W C_{k} (mod p) (die Koeffizienten von S und T liegen in [−p/2, p/2]). Dann ist C_{k}S + B_{k}T ≡ R_{k} (mod p). Da Grad(R_{k}) ≤ Grad(A) = Grad(B_{k}) + Grad(C_{k}) ist, und Grad(S) < Grad(B) ist also Grad(T) ≤ Grad(R_{k}) − Grad(B_{k}) ≤ Grad(C_{k}) (da B_{k} normiert ist).

4.15 Bemerkung: Ersetzt man U, V in ⋆_{k} durch U_{k}, V_{k} mit U_{k}B_{k} + V_{k}C_{k} ≡ 1 (mod p^{k}), so kann man mit einer zum Beweis von (4.14) analogen Methode B_{k+1}, C_{k+1} finden, die ⋆_{2k} erfüllen (quadratische Konvergenz).

Teil C) Faktorisierung in ℤ[X] Problem: Gegeben f ∈ ℤ[X], f = ∑_{i=0}^{n} a_{i}X^{i}, primitiv (d.h. ggT(a_{0}, …, a_{n}) = 1) und quadratfrei (d.h. ggT(f, f′) = 1). Gesucht ist eine Faktorisierung von f in irreduzible Polynome in ℤ[X]. Das Faktorisieren geschieht in 3 Etappen: A) Suche eine Primzahl p mit ggT(f (mod p), f′ (mod p)) = 1 (in 𝔽_{p}[X]). Faktorisiere f (mod p), d.h. finde Polynome f_{1}, …, f_{s} ∈ ℤ[X] mit f_{i} (mod p) ∈ 𝔽_{p}[X] irreduzibel, normiert

f ≡ a_{n}f_{1} … f_{s} (mod p).

Dazu werden die Algorithmen aus Teil 4.A) benutzt. B) Lifte diese Faktorisierung zu einer Faktorisierung von f modulo p^{k}

f ≡ a_{n}f̃_{1} … f̃_{s} (mod p^{k})

mit dem Hensel’schen Lemma (4.14). Hier genügt es, zunächst einen irreduziblen Faktor (z.B. f_{1}) zu h = f̃_{1} zu liften. C) Bestimme mit Hilfe des irreduziblen Faktors h von f (mod p^{k}) aus B) einen Faktor h_{0} von f in ℤ[X]:

4.16 Satz:

Vor.: Sei f ∈ ℤ[X] primitiv, n := Grad(f) und h ∈ ℤ[X] normiert mit

(i) h (mod p) ∈ 𝔽_{p}[X] irreduzibel. (ii) (h (mod p))^{2} | f̸ (mod p) ∈ 𝔽_{p}[X]. (iii) h (mod p^{k}) | f (mod p^{k}) ∈ (ℤ/p^{k}ℤ)[X]. Beh.: Dann hat f genau einen irreduziblen Faktor h_{0} ∈ ℤ[X] mit h (mod p) | h_{0} (mod p). Für jeden Teiler g von f in ℤ[X] sind äquivalent: h (mod p) | g (mod p) ∈ 𝔽_{p}[X]. ⇔ h (mod p^{k}) | g (mod p^{k}) ∈ (ℤ/p^{k}ℤ)[X]. ⇔ h_{0} | g ∈ ℤ[X]. Beweis: einfaches Rechnen in faktoriellen Ringen, z.H.

4.17 Algorithmus: (finde das h_{0} aus Satz (4.16)) Idee: Die Bedingung h (mod p^{k}) | h_{0} (mod p^{k}) bedeutet, dass

h_{0} (mod p^{k}) = (h (mod p^{k}))(g (mod p^{k})) = g_{0}h+g_{1}Xh+…+g_{j}X^{j}h (mod p^{k})

mit g_{0}, …, g_{j} ∈ ℤ wo j = m − l, m := Grad(h_{0}), l := Grad(h). Anders ausgedrückt: h_{0} liegt in dem von h, Xh, …, X^{j}h, p^{k}, p^{k}X, …, p^{k}X^{j} erzeugten ℤ-Gitter L (der Dimension m + 1). Identifiziert man die Polynome ∈ ℤ[X] vom Grad ≤ m mit ihren Koeffiziententupel, also z.B. h =: ∑_{i=0}^{l} c_{i}X^{i} mit (c_{0}, …, c_{l}, 0 …, 0) und h_{0} =: ∑_{i=0}^{m} v_{i}X^{i} mit v = (v_{0}, …, v_{m}), so wird das Gitter L von (c_{0}, …, c_{l}, 0 …, 0), (0, c_{0}, …, c_{l}, 0 …, 0), …, (0, …, 0, c_{0}, …, c_{l}), (p^{k}, 0, …, 0), … (0, …, 0, p^{k}, 0, …, 0) erzeugt. Wir betrachten L als Gitter im ℝ^{m+1} mit Standardskalarproduct Φ. Sind die Koeffizienten von h_{0} im Vergleich zu p^{k} klein, so ist h_{0} ein kurzer Vektor in L.

(Vergleiche Algorithmus 3.22). Mit Hilfe des LLL-Algorithmus kann man so ganzzahlige Polynome (deterministisch in polynomialer Zeit) faktorisieren. Genau gilt folgender Satz:

4.18 Satz: (ohne Beweis) Mit den Bezeichnungen aus (4.16) und (4.17) sei l := Grad(h) und k so groß dass

p^{kl} > 2^{mn/2}\binom{2m}{n}^{n/2}(∑_{i=0}^{n} a_{i}^{2})^{(m+n)/2}

Sei (b_{1}, …, b_{m+1}) eine LLL-reduzierte Basis von L. Dann gilt:

Grad(h_{0}) ≤ m ⇔ (⋆) Φ(b_{1}, b_{1}) < (p^{2kl}/(∑_{i=0}^{n} a_{i}^{2})^{m})^{1/n}.

Genauer: Ist (⋆) erfüllt, so sei t das maximale j ∈ 1, …, m + 1, für welches

(⋆_{j}) Φ(b_{j}, b_{j}) < (p^{2kl}/(∑_{i=0}^{n} a_{i}^{2})^{m})^{1/n}

gilt. Dann ist Grad(h_{0}) = m + 1 − t, h_{0} = ggT(b_{1}, …, b_{t}) (∈ ℤ[X], die Vektoren von L werden mit Polynomen identifiziert) und (⋆_{j}) gilt für alle j = 1, …, t.

Abschnitt 5: Kryptographie.

Zunächst wollen wir die Struktur von (ℤ/mℤ)^{∗} untersuchen.

5.1 Definition: Die Eulersche φ-Funktion:

φ : ℕ → ℕ; φ(m) := |(ℤ/mℤ)^{∗}|

5.2 Bemerkung: (ℤ/mℤ)^{∗} ≡ {a ∈ {1, …, m−1} | ggT(a, m) = 1}. Ist also m = ∏_{j=1}^{s} p_{j}^{α_{j}} mit paarweise verschiedenen Primzahlen p_{j} und α_{j} ≥ 1, dann ist

φ(m) = ∏_{j=1}^{s} p_{j}^{α_{j}−1}(p_{j} − 1).

5.3 Lemma: ∑_{d|m} φ(d) = m.

Beweis: m = ∏_{j=1}^{s} p_{j}^{α_{j}}. Induktion über ∑_{j=1}^{s} α_{j} =: n. n = 1: Klar. Induktionsschritt:

∑_{d|m} φ(d) = ∑_{d|m/p_{1}} φ(d) + ∑_{d|m/(p_{1}^{α_{1}})} φ(p_{1}^{α_{1}}d) =

m/p_{1} + p_{1}^{α_{1}−1}(p_{1} − 1)p_{2}^{α_{2}} … p_{s}^{α_{s}} = m.

5.4 Bezeichnungen: Sei G eine endliche Gruppe, a ∈ G, n := |G|.

Ordnung von a, ord(a) := minimales m ∈ ℕ mit a^{m} = 1. Exponent von G, exp(G) := kgV(ord(a) | a ∈ G). G heißt zyklisch, falls ein a ∈ G existiert mit G = {1, a, …, a^{ord(a)−1}} =: ⟨a⟩. In Zeichen: ⟨a⟩ =: C_{ord(a)} die (bis auf Isomorphie eindeutig bestimmte) zyklische Gruppe der Ordnung ord(a). Klar: G zyklisch ⇒ |G| = exp(G) (Umkehrung gilt nicht). ord(a) = |⟨a⟩| = exp(⟨a⟩). a ∈ G ⇒ ord(a) | exp(G) | |G|.

5.5 Satz: p Primzahl ⇒ (ℤ/pℤ)^{∗} = 𝔽_{p}^{∗} ≅ C_{p−1}.

Beweis: Zeigen: Für jeden Teiler d von p−1 hat 𝔽_{p}^{∗} genau φ(d) Elemente der Ordnung d. Denn: Sei ψ(d) := {a ∈ 𝔽_{p}^{∗} | ord(a) = d}. Dann gilt d | p̸ − 1 ⇒ ψ(d) = 0. Ist a ∈ 𝔽_{p}^{∗}, ord(a) = d, so ist ⟨a⟩ die Menge der d verschiedenen Nullstellen von X^{d}−1. Die Anzahl der Elemente der Ordnung d in ⟨a⟩ ist φ(d). Also ist ψ(d) ≤ φ(d). Deshalb ist

p − 1 = |𝔽_{p}^{∗}| = ∑_{d|p−1} ψ(d) ≤ ∑_{d|p−1} φ(d) = p − 1.

Also ψ(d) = φ(d). Insbesondere ist ψ(p − 1) ≠ 0 und 𝔽_{p}^{∗} = ⟨a⟩ für jedes Element a ∈ 𝔽_{p}^{∗} mit ord(a) = p − 1.

5.6 Satz: Sei p eine Primzahl, α ≥ 1.

(a) Ist p > 2, so ist (ℤ/p^{α}ℤ)^{∗} ≅ C_{p^{α−1}(p−1)}.

(b) Ist α ≥ 2, so ist (ℤ/2^{α}ℤ)^{∗} ≅ C_{2} × C_{2^{α−2}}. Beweis: (a) Mit Hilfe der binomischen Formel zeigt man: Ist β ≥ 1, b ∈ ℤ, p | b̸, dann ist

(1 + p^{β}b)^{p} = (1 + p^{β+1}c)

für ein c ∈ ℤ mit p | c̸. Ist a ∈ ℤ mit ⟨(a+pℤ)⟩ = (ℤ/pℤ)^{∗}, so ist a^{p−1} = 1+pb. Gilt p | b̸, so ist ⟨a+p^{α}ℤ⟩ = (ℤ/p^{α}ℤ)^{∗}. Falls p | b, dann ist ⟨a + p + p^{α}ℤ⟩ = (ℤ/p^{α}ℤ)^{∗}.

(b) als Übung.

5.7 Folgerung: Ist m = ∏_{j=1}^{s} p_{j}^{α_{j}} ungerade, so ist (ℤ/mℤ)^{∗} ≅ ∏_{j=1}^{s} C_{p_{j}^{α_{j} −1}(p_{j}−1)} vom

Exponenten ∏_{j=1}^{s} p_{j}^{α_{j}−1}kgV(p_{j} − 1 | 1 ≤ j ≤ s).

Nun zur Kryptographie: Kryptographie dient zum einen zum abhörsicheren Austausch von Nachrichten über belauschte Kanäle, zum anderen aber auch zur Authentifikation, d.h. der Empfänger will prüfen können, dass die Nachricht unverändert vom Absender kommt. Man unterscheidet 2 wesentlich verschiedene Strategien, die private-key und die public-key Krytosysteme:

5.8 Private Key Kryptosysteme:

A und B einigen sich \underline{geheim} auf einen Schlüssel f (z.B. n zufällige bits (x_{1}, …, x_{n}) ∈ {0, 1}^{n}). Will A eine Nachricht an B schicken, so verschlüsselt A die Nachricht N zu f(N), welches er sendet. Mit dem gleichen Schlüssel (d.h. mit f^{−1}, das hier leicht aus f zu berechnen ist), kann B aus f(N) wieder die Nachricht N berechnen. (z.B. A konvertiert N als bit-string, den er in Stücke der Länge n unterteilt und sendet anstelle von (s_{1}, …, s_{n}) die bit-Folge (s_{1} +x_{1} (mod 2), …, s_{n} +x_{n} (mod 2)). B entschlüsselt durch Berechnen von s_{i} = (s_{i} + x_{i}) + x_{i} (mod 2).) Vorteil: Schnell und relativ sicher. Nachteil: Schlüsselaustausch muss geheim erfolgen. Wollen n Personen miteinander kommunizieren, so müssen insgesamt \binom{n}{2} Schlüssel je zweimal abgespeichert werden. Wir wollen uns hier nur mit dem Schlüsselaustausch beschäftigen:

5.9 Diffie-Hellman Schlüsselaustausch. A und B wollen einen gemeinsamen geheimen Schlüssel berechnen. Zur Kommunikation stehen ihnen jedoch nur belauschte Kanäle zur Verfügung. Sie wählen öffentlich eine große Primzahl p und g ∈ 𝔽_{p}^{∗}. A wählt geheim eine Zahl k_{A} < p. B wählt geheim eine Zahl k_{B} < p. A schickt g^{k_{A}} an B. B schickt g^{k_{B}} an A. Der gemeinsame Schlüssel ist g^{k_{A}k_{B}} = (g^{k_{A}})^{k_{B}} = (g^{k_{B}})^{k_{A}}. Ein Lauscher kennt p, g, g^{k_{A}} und g^{k_{B}}, kann aber daraus nicht (einfach) g^{k_{A}k_{B}} berechnen.

5.10 Bemerkung: Die Berechnung von g^{k} benötigt ∼ 2 log_{2}(k) Multiplikationen. Ist k = ∑_{i=0}^{n} k_{i}2^{i} mit k_{i} ∈ {0, 1}, so ist g^{k} = ∏_{k_{i}=1} g^{2^{i}}: Algorithmus: R := 1; F := g; while (k > 0) do

if (k (mod 2)) then R := RF; end if; k := k div 2; F := F^{2};

end while; RETURN(R);

5.11 Das Diskrete Logarithmen Problem:

Sei G eine Gruppe und g ∈ G. Man kennt g, h ∈ ⟨g⟩ und sucht a ∈ ℕ mit g^{a} = h. Methode: Shanks Baby-Step-Giant-Step Algorithmus: n := ord(g), m := ⌈\sqrt{n}⌉. Berechne h, hg^{−1}, hg^{−2}, …, hg^{−(m−1)} (baby-steps) und 1, g^{m}, g^{2m}, …, g^{m(m−1)} (giant-steps) Ist h = g^{im+j} mit 0 ≤ i, j < m, so ist hg^{−j} = g^{im}, d.h. ein Eintrag in der ersten Liste ist gleich einem Eintrag in der zweiten Liste. Zeit- und Platzbedarf: ∼ m ∼ \sqrt{n}. Kennt man Faktorisierung n = n_{1}n_{2} mit ggT(n_{1}, n_{2}) = 1, so kann man das DL-Problem reduzieren: Man berechnet j_{1}, j_{2} mit g^{n_{i}j_{i}} = h^{n_{i}} ∈ ⟨g^{n_{i}}⟩, und a_{1}, a_{2} mit a_{1}n_{1} + a_{2}n_{2} = 1. Dann ist h = h^{a_{1}n_{1}}h^{a_{2}n_{2}} = g^{a_{1}n_{1}j_{1}+a_{2}n_{2}j_{2}}. Ähnlich kann man Primzahlpotenzen ausnutzen: Ist n = p^{α}, und h = g^{a}, so kann man a = ∑_{i=0}^{α−1} a_{i}p^{i} mit a_{i} ∈ {0, …, p − 1} schreiben. Dann gilt h^{p^{α−1}} = (g^{p^{α−1}})^{a_{0}} ∈ ⟨g^{p^{α−1}}⟩. Daraus erhält man a_{0}. Setzt man h′ := hg^{−a_{0}}, so ist h′ ∈ ⟨g^{p}⟩ und man kann mit g^{p} weiterarbeiten. Für allgemeine zyklische Gruppen gibt es bisher keinen wesentlich besseren Algorithmus. Man kann jedoch den Platzbedarf durch einen einfachen probabilistischen Algorithmus stark reduzieren. Für das DL-Problem in 𝔽_{p}^{∗} gibt es jedoch bessere Algorithmen, die aus den Faktorisierungsalgorithmen in Abschnitt 7 entwickelt worden sind. Es scheint gleich schwer zu sein, das DL-Problem in 𝔽_{p}^{∗} zu lösen, wie eine Zahl N ∼ p zu faktorisieren. Der Diffie-Hellmann-Schlüsselaustausch scheint also zur Zeit sicher zu sein, falls p mehr als 250 Stellen hat, und p − 1 = 2q für eine Primzahl q ist.

5.12 Digital Signature Algorithm. (DSA)

Man kann das Rechnen in 𝔽_{p}^{∗} auch zum Unterschreiben von Nachrichten benutzen. Das folgende Verfahren ist 1991 von der US-Regierung als Standardverfahren vorgeschlagen worden: Will A die Nachricht N unterschreiben, so braucht A:

1) Primzahl q (ca. 50 Stellen) (öffentlich)

2) Primzahl p ≡ 1 (mod q) (ca. 250 Stellen) (öffentlich)

3) Einen Erzeuger g der Untergruppe C_{q} ≤ 𝔽_{p}^{∗} ≅ C_{p−1}. (öffentlich)

4) Eine zufällige Zahl 0 < x < q (geheim). Öffentlich bekannt: y = g^{x} (mod p). Sowie eine öffentlich bekannte hashfunktion H : { Nachrichten } → {1, …, q − 1} Zum Signieren der Nachricht N, berechnet A den Wert H := H(N) ∈ {1, …, q−1}, wählt zufälliges k ∈ {1, …, q − 1}, berechnet das r ∈ {0, …, p − 1} mit g^{k} ≡ r (mod p), sowie \overline{r} := r (mod q). Ist \overline{r} = 0 oder H + x\overline{r} ≡ 0 (mod q), so wählt A ein neues k, sonst bestimmt er s ∈ \{1, …, q − 1\} mit sk ≡ H + x\overline{r} (mod q). Die Unterschrift von A ist dann (\overline{r}, s) (ca. 100 Stellen). Der Empfänger B verifiziert die Unterschrift: Er berechnet H := H(N), u_{1} := s^{−1}H (mod q), u_{2} := s^{−1}\overline{r} (mod q), sowie g^{u_{1}}y^{u_{2}} ≡ g^{s^{−1}H}g^{xs^{−1}\overline{r}} ≡ g^{k} (mod p). Falls das Ergebnis ≡ \overline{r} (mod q), so ist die Nachricht N nicht verfälscht und stammt von A.

Wir kommen nun zu anderen Gruppen zum Schlüsselaustausch und Authentifikation: elliptische Kurven.

5.13 Definition: Sei p > 3 eine Primzahl, a, b ∈ 𝔽_{p} so dass X^{3} + aX + b keine mehrfachen Nullstellen hat, (also 4a^{3} + 27b^{2} ≠ 0).

E := E_{a,b}(𝔽_{p}) = {(x, y) ∈ 𝔽_{p}^{2} | y^{2} = x^{3} + ax + b} ∪ {O}

heißt elliptische Kurve über 𝔽_{p}. (besser: die Menge der 𝔽_{p}-rationalen Punkte auf E).

5.14 Definition: (Addition auf E := E_{a,b}(𝔽_{p})):

Ist P = (x, y) ∈ E, so ist −P := (x, −y). P + (−P) := O.

Ist P_{1} = (x_{1}, y_{1}), P_{2} = (x_{2}, y_{2}) ∈ E mit P_{1} ≠ −P_{2}, so gilt P_{1} + P_{2} =: P_{3} = (x_{3}, y_{3}) ∈ E mit

x_{3} = λ^{2} − x_{1} − x_{2}, y_{3} = λ(x_{1} − x_{3}) − y_{1},

wo λ := (y_{2} − y_{1})/(x_{2} − x_{1}), falls P_{1} ≠ P_{2} und λ := (3x_{1}^{2} + a)/(2y_{1}), falls P_{1} = P_{2}.

5.15 Bemerkung: Die obige Addition macht aus E eine kommutative Gruppe mit O als neutralem Element.

5.16 Beispiel: E : definiert durch Y^{2} = X^{3} − X, p = 7.

E(𝔽_{7}) = {O, (0, 0), (1, 0), (4, 2), (4, −2), (−1, 0), (−2, 1), (−2, −1)}.

5.17 Bemerkung: Es gibt einen sehr guten (probabilistischen) Algorithmus, um Punkte in E(𝔽_{p}) (E beliebige elliptische Kurve über 𝔽_{p}) zu finden: Sei f(X) := X^{3} +aX +b. Wähle x ∈ 𝔽_{p} zufällig. Teste, ob z := f(x) ein Quadrat in 𝔽_{p}^{∗} (oder = 0) ist. Beachte: z ∈ (F_{p}^{∗})^{2} ⇔ z^{(p−1)/2} = 1. Falls ja, so berechne y := \sqrt{z} ∈ 𝔽_{p}: Ist p ≡ 3 (mod 4), so ist y := z^{(p+1)/4}. Ist p ≡ 1 (mod 4), so sei p − 1 = 2^{s}t mit ungeradem t ∈ ℕ. Sei u ∈ 𝔽_{p}^{∗} \ (𝔽_{p}^{∗})^{2} und v := u^{t} (Element der Ordnung 2^{s}). Setze y_{1} := z^{(t+1)/2}. Dann ist y_{1}^{2} = zz^{t}. Da z^{t} ∈ ⟨v^{2}⟩ gibt es ein l mit z = v^{2l} (mit 5.11 zu bestimmen). Dann ist y := y_{1}v^{−l} eine Wurzel aus z.

5.18 Satz von Hasse (ohne Beweis, da sehr tiefliegend)

p + 1 − 2\sqrt{p} ≤ |E(𝔽_{p})| ≤ p + 1 + 2\sqrt{p}.

5.19 Schlüsselaustausch mit elliptischen Kurven:

Wie Diffie-Hellman (5.9) A und B wollen einen gemeinsamen geheimen Schlüssel berechnen. Sie wählen öffentlich eine große Primzahl p, elliptische Kurve E = E_{a,b}(𝔽_{p}) und P ∈ E. A wählt geheim eine Zahl k_{A} ∼ p. B wählt geheim eine Zahl k_{B} ∼ p. A schickt k_{A}P an B. B schickt k_{B}P an A. Der gemeinsame Schlüssel ist k_{A}k_{B}P Ein Lauscher kennt p, E, P, k_{A}P und k_{B}P, Die Berechnung von k_{A}k_{B}P scheint nicht leichter zu sein als das Lösen des DL-Problems für die Gruppe G = ⟨P ⟩. Im Gegensatz zu endlichen Körpern gibt es hierfür noch keine besseren Verfahren, als die in (5.11) vorgestellten.

5.20 Authentifikation mit elliptische Kurven.

Annahme: ord(P) = q ist eine Primzahl in der Größenordnung von p. Der Teilnehmer A kennt k_{A} und macht Q := k_{A}P öffentlich bekannt. A wählt zufällig k ∈ {2, …, q − 2}, berechnet kP = (x_{1}, y_{1}) ∈ E mit x_{1}, y_{1} ∈ {0, …, p − 1} sowie r := x_{1} (mod q) und s = k^{−1}(H(N) + xr) (mod q). Ist r = 0 oder s = 0, so wählt A ein neues k. Unterschrift: (r, s). B verifiziert die Unterschrift mit Hilfe einer authentifizierten Kopie von A’s öffentlichem Schlüssel Q. Er berechnet w = s^{−1} (mod q) und H(N). Dann u_{1} := H(N)w (mod q) und u_{2} := rw (mod q), sowie u_{1}P + u_{2}Q = (x_{0}, y_{0}) mit x_{0} ∈ {0, …, p − 1}. Er reduziert x_{0} modulo q und akzeptiert die Nachricht, falls x_{0} ≡ r (mod q).

5.21 Definition: Ein Public-Key-Kryptosystem mit Authentifikation besteht aus einer Menge von Teilnehmern T = {A, B, …}, einer Nachrichtenmenge N, einer öffentlich bekannten Hashfunktion: H : N → N sowie öffentlich bekannten bijektiven Funktionen f_{t} : N → N für alle t ∈ T. Jeder Teilnehmer t kennt sein f_{t}^{−1} (geheim). Will A an B eine Nachricht N ∈ N senden, so berechnet er f_{B}(N) und f_{B}(f_{A}^{−1}(H(N))) und sendet diese Daten über (belauschte) Kanäle an B. B berechnet f_{B}^{−1}(f_{B}(N)) = N (mit seinem geheimen Schlüssel f_{B}^{−1}) und H(N) (mit der öffentlichen Hashfunktion). B kann feststellen, dass die Nachricht N (unverfälscht) von A kommt, indem er H(N) mit f_{A}(f_{B}^{−1}(f_{B}(f_{A}^{−1}(H(N))))) vergleicht.

5.22 Das RSA-Verfahren. Empfänger B wählt 2 (große) Primzahlen p, q und eine Zahl v ∈ {3, …, (p − 1)(q − 1)} mit ggT(v, (p − 1)(q − 1)) = 1 und bestimmt e ∈ ℕ mit ve ≡ 1 (mod (p − 1)(q − 1)). B berechnet m := pq. Der öffentliche Schlüssel von B ist (m, v). Zur Veschlüsselung von N berechnet A zunächst die m-adische Entwicklung von N ∈ ℕ, N = ∑_{i=0}^{k} n_{i}m^{i} mit n_{i} ∈ {0, …, m − 1} und schickt die Ziffern n_{i} hintereinander. Ist n ∈ {0, …, m − 1}, so ist f_{B}(n) = n^{v} (mod m) ∈ {0, …, m − 1}, f_{B}(N) = f_{B}(n_{0}), …, f_{B}(n_{k}). Der Empfänger B berechnet die n_{i} aus den f_{B}(n_{i}) = n_{i}^{v} als n_{i} = (f_{B}(n_{i}))^{e} (mod m).

5.23 Lemma: Ist m = pq Produkt von 2 Primzahlen, und a ∈ ℕ mit a ≡ 1 (mod (p − 1)(q − 1)), so ist für alle n ∈ ℤ, n^{a} ≡ n (mod m).

5.24 Kosten von RSA:

Berechnung von n^{v} mit Algorithmus (5.10), ∼ log_{2}(v). Berechnung von f_{B}(n)^{e} (mod m) mit chinesischem Restsatz: genügt ev ≡ 1 (mod ggT(p− 1, q − 1)) bzw. zwei Zahlen e_{p}, e_{q} mit e_{p}v ≡ 1 (mod p − 1), e_{q}v ≡ 1 (mod q − 1). Berechne x_{p} := f_{B}(n)^{e_{p}} (mod p) und x_{q} := f_{B}(n)^{e_{q}} (mod q) und dann n ∈ {0, …, m − 1} mit n ≡ x_{p} (mod p) und n ≡ x_{q} (mod q) mit dem chinesischen Restsatz.

5.25 Bemerkung: Kann der Angreifer m faktorisieren, so kann er f_{B}^{−1} (also den Entschlüsselungsexponenten e) berechnen. Die Berechnung von e ist sogar äquivalent mit einer Faktorisierung von m, jedoch ist nicht bekannt, ob das v-te Wurzelziehen modulo m nicht leichter zu lösen ist. Damit das Faktorisieren von m schwierig ist, müssen p und q geeignete, in etwa 100-stellige Primzahlen sein.

Abschnitt 6: Zusammengesetzheitstests und Primzahlbeweise.

6.1 Satz: (Fermat-Test)

Sei N ∈ ℕ. Gibt es ein a ∈ ℤ mit ggT(a, N) = 1 und a^{N−1} ≢ 1 (mod N), so ist N \underline{keine} Primzahl.

6.2 Bemerkung: Die Umkehrung von (6.1) gilt nicht. Falls alle zu N teilerfremden a ∈ ℤ die Kongruenz a^{N−1} ≡ 1 (mod N) erfüllen, so folgt nur, dass der Exponent exp(ℤ/Nℤ^{∗}) ein Teiler von N − 1 ist. Zusammengesetze Zahlen N mit exp(ℤ/Nℤ^{∗}) | N −1 nennt man Carmichael-Zahlen. Beispiel: N = 561 = 3 · 11 · 17 ist eine Carmichael Zahl.

6.3 Bemerkung: N ist Carmichael Zahl ⇔ N ist zusammengesetzt, quadratfrei und p − 1 | N − 1 für alle Primteiler p von N.

6.4 Satz: Sei N ∈ ℕ ungerade, N − 1 = d2^{s} mit ungeradem d.

Genau dann ist N keine Primzahl, wenn es ein a ∈ ℤ gibt, ggT(a, N) = 1 welches nicht

⋆_{N} a^{d} ≡ 1 (mod N) oder a^{d2^{r}} ≡ −1 (mod N) für ein r = 0, 1, …, s − 1

erfüllt. Falls a die Bedingung ⋆_{N} erfüllt, so nennt man N eine Pseudoprimzahl zur Basis a. Beweis: \underline{⇐}: Sei N eine Primzahl, a ∈ ℤ, N | a̸. Dann ist a + Nℤ ∈ ℤ/Nℤ^{∗} und x := ord(a + Nℤ) ist ein Teiler von N − 1 = 2^{s}d. Also ist x von der Form x = 2^{t}d′ mit d′ | d und t ≤ s und a^{d2^{t−1}} ≡ 1 (mod N). \underline{⇒}: Angenommen für alle a ∈ ℤ mit ggT(a, N) = 1 gilt ⋆_{N}. Dann ist N eine Carmichael-Zahl, also insbesondere quadratfrei, N = p_{1} … p_{t} mit paarweise verschiedenen ungeraden Primzahlen p_{i}. Ist N zusammengesetzt, so ist nach dem chinesischen Restsatz

(ℤ/Nℤ)^{∗} ≅ (ℤ/p_{1}ℤ)^{∗} × (ℤ/p_{2} … p_{t}ℤ)^{∗}.

Sei α ∈ ℤ mit ⟨α + p_{1}ℤ⟩ = (ℤ/p_{1}ℤ)^{∗} und a ∈ ℤ mit a ≡ α (mod p_{1}) und a ≡ 1 (mod p_{2} … p_{t}). Dann hat a + Nℤ ∈ (ℤ/Nℤ)^{∗} gerade Ordnung, d.h. a^{d} ≢ 1 (mod N). Allerdings ist a^{n} ≡ 1 (mod p_{2} … p_{t}) für alle n ∈ ℕ, also gilt nie a^{n} ≡ −1 (mod N).

6.5 Algorithmus (Rabin-Miller Test)

Eingabe: N ∈ ℕ, ungerade. Ausgabe: N ist zusammengesetzt: Z oder N ist wahrscheinlich eine Primzahl: P. Algorithmus: Sei N − 1 = d2^{s} mit d ungerade.

1) for z from 0 to 50 do Wähle a ∈ {2, …, N − 2} zufällig. Sei g:= ggT(a,N). if g ≠ 1 then RETURN(Z) else

Berechne m := a^{d} (mod N). if m ≡ 1 (mod N) then goto 1) else

for i from 0 to s-1 do if m ≡ −1 (mod N) then goto 1) end if; m := m · m;

end for;

RETURN(Z); end if;

end if; end for; RETURN(P);

6.6 Bemerkung: Ist N zusammengesetzt, so ist N eine Pseudoprimzahl zur Basis a für höchstens die Hälfte der a ∈ (ℤ/Nℤ)^{∗}. Also ist die Wahrscheinlichkeit, dass Algorithmus (6.5) P ausgibt, obwohl N zusammengesetzt ist, kleiner als 2^{−50}. Es gibt nur 101 zusammengesetzte N ≤ 10^{12}, die Pseudoprimzahlen zu den Basen 2, 3, und 5 sind.

Wir kommen nun zu Primzahlbeweisen:

6.7 Satz:

Sei N ∈ ℕ, N −1 = ∏_{j=1}^{n} q_{j}^{β_{j}} mit paarweise verschiedenen Primzahlen q_{j}. Angenommen es gibt Zahlen a_{j} ∈ ℤ mit

a_{j}^{(N−1)/q_{j}} ≢ 1 (mod N), aber a_{j}^{N−1} ≡ 1 (mod N) (j = 1, …, n).

Dann ist N eine Primzahl. Beweis: Denn dann teilt q_{j}^{β_{j}} den Exponenten von ℤ/Nℤ^{∗} für alle j, also N − 1 | exp(ℤ/Nℤ^{∗}) | |ℤ/Nℤ^{∗}| ≤ N −1. Also ist |ℤ/Nℤ^{∗}| = N −1 und N ist eine Primzahl.

6.8 Bemerkung: Wir haben gezeigt, dass N geanu dann eine Primzahl ist, wenn exp(ℤ/Nℤ^{∗}) = N − 1.

6.9 Bemerkung: Um mit Satz (6.7) die Primzahleigenschaft von N zu beweisen, muss man N −1 faktorisieren, was i.a. nicht wesentlich einfacher ist, als N zu faktorisieren. Da zusammengesetzte Zahlen N ∈ ℕ aber immer einen Primfaktor p ≤ \sqrt{N} haben, kann man (6.7) verbessern:

6.10 Satz: Sei N ∈ ℕ, N − 1 = RF, F = ∏_{j=1}^{n} q_{j}^{β_{j}} > \sqrt{N} mit paarweise verschiedenen Primzahlen q_{j} und ggT(R, F) = 1. Angenommen es gibt Zahlen a_{j} ∈ ℤ mit

ggT(a_{j}^{(N−1)/q_{j}} − 1, N) = 1, aber a_{j}^{N−1} ≡ 1 (mod N) (j = 1, …, n).

Dann ist N eine Primzahl. Beweis: Sonst sei p ein Primteiler von N mit p ≤ \sqrt{N}. Die Bedingungen zeigen, dass die Ordnung von a_{j} + pℤ ∈ (ℤ/pℤ)^{∗} durch q_{j}^{β_{j}} teilbar ist. Also ist der Exponent von ℤ/pℤ^{∗} durch F teilbar, was ein Widerspruch zu F > \sqrt{N} ≥ p ist.

6.11 Definition: F_{n} := 2^{2^{n}} + 1 heißt die n-te Fermat-Zahl. F_{1}, …, F_{4} sind die einzigen bekannten Fermat-Primzahlen, F_{5}, …, F_{11} kann man voll faktorisieren, von F_{12}, …, F_{22} weiss man, dass sie zusammengesetzt sind.

6.12 Satz (Pépin): F_{n} ist Primzahl ⇔ 3^{2^{2^{n}−1}} ≡ −1 (mod F_{n}). Zum Beweis benötigen wir das quadratische Reziprozitätsgesetz:

6.13 Definition: (Legendre Symbol)

Sei p eine Primzahl, n ∈ ℤ.

(\frac{n}{p}) := \{ \begin{matrix}0 & p | n \\ 1 & n ∈ (ℤ/pℤ^{∗})^{2} \\ −1 & n ∈ (ℤ/pℤ^{∗}) \ (ℤ/pℤ^{∗})^{2} \end{matrix}

Klar: p ungerade ⇒ (\frac{n}{p}) ≡ n^{(p−1)/2} (mod p).

(\frac{n}{p}) hängt nur von n + pℤ ab.

6.14 Bemerkung: (\frac{a}{p}) (\frac{b}{p}) = (\frac{ab}{p})

6.15 Satz: Sei p ungerade Primzahl.

(i) (\frac{1}{p}) = 1.

(ii) (\frac{−1}{p}) = (−1)^{(p−1)/2}.

(iii) (\frac{2}{p}) = (−1)^{(p^{2}−1)/8}. Beweis: (i) und (ii) sind klar. (iii) Sei α primitive 8-te Einheitswurzel in \overline{𝔽_{p}}. Dann erfüllt y := α+α^{−1} die Gleichung y^{2} = 2. Außerdem ist y^{p} = α^{p} + α^{−p}. Ist p ≡ ±1 (mod 8), so ist y^{p} = y, also 2^{(p−1)/2} ≡ y^{p−1} ≡ 1 (mod p). Ist p ≡ ±5 (mod 8), so ist y^{p} = −y, also 2^{(p−1)/2} ≡ y^{p−1} ≡ −1 (mod p).

6.16 Satz (Quadratisches Reziprozitätsgesetz) (Gauß) Sind p ≠ q zwei ungerade Primzahlen, so gilt

(\frac{q}{p}) (\frac{p}{q}) = (−1)^{(p−1)(q−1)/4}.

Beweis: Sei w primitive q-te Einheitswurzel in \overline{𝔽_{p}} und

y := ∑_{a∈ℤ/qℤ} (\frac{a}{q}) w^{a}

\underline{1. Behauptung:} y^{2} = (−1)^{(q−1)/2}q. Denn: y^{2} = ∑_{a,b∈ℤ/qℤ} (\frac{ab}{q}) w^{a+b} = ∑_{c∈ℤ/qℤ} ∑_{a∈ℤ/qℤ} (\frac{a(c−a)}{q}) w^{c}. Ist a ≠ 0, dann

ist (\frac{a(c−a)}{q}) = (\frac{−a^{2}}{q} ) (\frac{1−ca^{−1}}{q} ) = (−1)^{(q−1)/2} (\frac{1−ca^{−1}}{q} ). Für a = 0 ist (\frac{a(c−a)}{q}) = 0.

Also ist (−1)^{(q−1)/2}y^{2} = ∑_{c∈ℤ/qℤ} S(c)w^{c} mit S(c) := ∑_{a∈(ℤ/qℤ)^{∗}} (\frac{1−ca^{−1}}{q} ) w^{c}. Ist c = 0, so ist S(c) = q − 1. Ist c ≠ 0, so durchläuft 1 − ca^{−1} alle Elemente von ℤ/qℤ ungleich 1. Also ist S(c) = ∑_{b∈ℤ/qℤ} (\frac{b}{q} ) − (\frac{1}{q}) = 0 − 1 = −1. Deshalb ist (−1)^{(q−1)/2}y^{2} = − ∑_{c∈ℤ/qℤ} w^{c} + q = q. \underline{2. Behauptung:} y^{p−1} = (\frac{p}{q}).

Denn: y^{p} = ∑_{a∈ℤ/qℤ} (\frac{a}{q}) w^{pa} = ∑_{b∈ℤ/qℤ} (\frac{bp^{−1}}{q} ) w^{b} = (\frac{p^{−1}}{q} ) y = (\frac{p}{q}) y, woraus Behauptung 2 durch Multiplikation mit y^{−1} folgt. Also ist insgesamt (\frac{p}{q}) = y^{p−1} = (y^{2})^{(p−1)/2} = ((−1)^{(q−1)/2}q)^{(p−1)/2}

= (−1)^{(p−1)(q−1)/4}q^{(p−1)/2} ≡ (−1)^{(p−1)(q−1)/4} (\frac{q}{p}) (mod p). Da beide Seiten ∈ \{±1\} sind, folgt daraus die Gleichheit in ℤ. \underline{Beweis von (6.12)} ⇐: folgt aus Satz (6.7). ⇒: Sei F_{n} Primzahl. Zu zeigen: (\frac{3}{F_{n}} ) = −1. Nach (6.16) ist (\frac{3}{F_{n}} ) = (\frac{F_{n}}{3} ) = −1 da F_{n} ≡ −1 (mod 3) ist. Letzteres sieht man wie folgt ein: Es gilt für alle ungeraden Zahlen u, dass X +1 | X^{u}+1 in ℤ[X]. Also ist F_{n}+1 = 2(2^{2^{n}−1}+1) durch (2+1) = 3 teilbar.

6.17 Definition: M_{p} := 2^{p} − 1 heißt Mersenne Zahl.

6.18 Bemerkung: d | p ⇒ X^{d} − 1 | X^{p} − 1 in ℤ[X]. Ist also M_{p} eine Primzahl, so ist p eine Primzahl. Man kennt die ersten 37 Primzahlen p, für die M_{p} eine Primzahl ist, p = 2, 3, 5, 7, …, 3.021.377. Die größte und vermutlich 38-te Mersenne Primzahl ist M_{p} mit p = 6.972.593 und mehr als 2 Mio. Dezimalstellen. I.a. kann man nicht M_{p} − 1 faktorisieren, d.h. Satz (6.10) ist nicht anwendbar, um M_{p} auf Primzahleigenschaft zu testen. Wir benötigen eine Strategie, die eine Faktorisierung von N + 1 ausnutzt:

6.19 Definition: Sei A eine kommutative Gruppe, U ≤ A eine Untergruppe. Dann wird

A/U := {aU | a ∈ A}

durch (aU)(bU) := abU zu einer Gruppe, die Faktorgruppe von A nach U. Es gilt für |A| < ∞: |A| = |U||A/U|.

6.20 Bemerkung: Sei p eine ungerade Primzahl, (\frac{D}{p} ) = −1. Dann ist 𝔽_{p^{2}} ≅ 𝔽_{p}[\sqrt{D}] ≅ 𝔽_{p}[X]/(X^{2} − D). Wie Satz (5.5) zeigt man 𝔽_{p^{2}}^{∗} ≅ C_{p^{2}−1}. Also ist (𝔽_{p^{2}}^{∗})/(𝔽_{p}^{∗}) ≅ C_{p+1}.

6.21 Definition: Sei N ungerade, ggT(D, N) = 1. Definiere Q := ℤ/Nℤ[\sqrt{D}] = \{a + b\sqrt{D} | a, b ∈ ℤ/Nℤ\} ≅ ℤ/Nℤ[X]/(X^{2}−D). Sei σ : Q → Q, (a+b\sqrt{D}) ↦ (a−b\sqrt{D}). Klar: σ ist ein Ringautomorphismus und für α ∈ Q gilt α ∈ ℤ/Nℤ ⇔ σ(α) = α. Insbesondere ist für α = a + b\sqrt{D} ∈ Q N(α) := ασ(α) = a^{2} − b^{2}D ∈ ℤ/Nℤ und α ∈ Q^{∗} ⇔ N(α) ∈ (ℤ/Nℤ)^{∗}.

6.22 Satz: Sei N = ∏_{j=1}^{s} p_{j}^{α_{j}} mit paarweise verschiedenen Primzahlen p_{j} > 2, D ∈ N mit ggT(D, N) = 1. Betrachte den Ring Q := ℤ/Nℤ[\sqrt{D}]. Dann gilt

|Q^{∗}| = φ(N) ∏_{j=1}^{s} p_{j}^{α_{j}−1}(p_{j} − (\frac{D}{p} ))

und exp(Q^{∗}/(ℤ/Nℤ)^{∗}) teilt ∏_{j=1}^{s} p_{j}^{α_{j}−1}kgV\{(p_{j} − (\frac{D}{p_{j}} )) | j = 1, …, s\}. Beweis: Q ≅ ⊕_{j=1}^{s}(ℤ/p_{j}^{α_{j}}ℤ)[X]/(X^{2} − D), nach dem chinesischen Restsatz, also genügt es, die Behauptung für Primzahlpotenzen N = p^{α} zu zeigen. Dann gilt Q^{∗} = \{a + b\sqrt{D} | a, b ∈ ℤ/Nℤ, p | a̸^{2} − b^{2}D\}. Unterscheide 2 Fälle:

(i) (\frac{D}{p} ) = −1. Dann gilt p | a̸^{2} − b^{2}D, für alle (a, b) ∈ (ℤ/Nℤ)^{2} \ p(ℤ/Nℤ)^{2}. Also ist |Q^{∗}| = p^{2α} − p^{2α−2} = p^{α−1}(p − 1)p^{α−1}(p + 1). (ii) (\frac{D}{p} ) = 1. Dann ist |\{(a, b) ∈ ℤ/pℤ | a^{2} = b^{2}D\}| = 1 + 2(p − 1). Also ist |Q^{∗}| = p^{2α} − p^{2α−2}(2p − 1) = p^{α−1}(p − 1)p^{α−1}(p − 1).

6.23 Folgerung: Sei N ungerade. exp((ℤ/Nℤ)[\sqrt{D}]^{∗}/(ℤ/Nℤ)^{∗}) = N+1 ⇔ N ist Primzahl und (\frac{D}{N} ) = −1. Also kann man eine Faktorisierung von N + 1 ausnutzen, um zu beweisen, dass N eine Primzahl ist, wenn man in der Gruppe (ℤ/Nℤ)[\sqrt{D}]^{∗}/(ℤ/Nℤ)^{∗}) rechnen kann. Dies geschieht mit Lucas-Folgen:

6.24 Definition: Sei α ∈ (ℤ/Nℤ)[\sqrt{D}]^{∗}, β := σ(α) ≠ α. Dann heißt ((U_{n})_{n∈ℕ}, (V_{n})_{n∈ℕ})

mit

U_{n} := \frac{α^{n} − β^{n}}{α − β} , V_{n} := α^{n} + β^{n}

die Lucas Folge zu α.

6.25 Bemerkung:

(i) U_{n} = 0 ⇔ α^{n} ∈ (ℤ/Nℤ)^{∗}. (ii) U_{n+m} = U_{m}V_{n} − (αβ)^{n}U_{m−n}. Insbesondere ist U_{2n} = U_{n}V_{n}. (iii) V_{2n} = V_{n}^{2} − 2(αβ)^{n}.

6.26 Satz: Sei N ungerade, N+1 = ∏_{j=1}^{n} q_{j}^{β_{j}}·R mit paarweise verschiedenen Primzahlen q_{j} und q_{j} | R̸ (j = 1, …, n), F := ∏_{j=1}^{n} q_{j}^{β_{j}} > \sqrt{N}+1. Gibt es D ∈ ℕ mit ggT(D, N) = 1 und für alle j = 1, …, n Zahlen α_{j} ∈ ℤ/Nℤ[\sqrt{D}]^{∗} so dass für die Lucas Folge U^{(j)} zu α_{j} gilt:

ggT(U_{(N+1)/q_{j}}^{(j)}, N) = 1, U_{N+1}^{(j)} ≡ 0 (mod N)

so ist N eine Primzahl. Beweis: Wie Satz (6.10).

6.27 Satz: Sei p ungerade und (v_{n})_{n∈ℕ_{0}} die durch v_{0} := 4, v_{s} := v_{s−1}^{2} −2 (s ≤ 1) definierte Folge. Dann ist M_{p} = 2^{p} − 1 eine Primzahl, genau dann wenn v_{p−2} ≡ 0 (mod M_{p}). Beweis: Wähle D := 3, α := (2 + \sqrt{3}) = \frac{1}{2}(1 + \sqrt{3})^{2} ∈ ℤ/M_{p}ℤ[\sqrt{D}]. Dann ist ασ(α) = 1. Für die Lucas Folge (U_{n}, V_{n}) zu α gilt dann V_{1} = α + σ(α) = 4. Also ist V_{2^{s}} = v_{s} nach (6.25) (iii). \underline{⇒:} Sei also M_{p} eine Primzahl. Da M_{p} ≡ 1 (mod 3) und M_{p} ≡ −1 (mod 8) ist, gilt

(\frac{3}{M_{p}} ) = − (\frac{M_{p}}{3} ) = − (\frac{1}{3}) = −1

und (\frac{2}{M_{p}} ) = 1. Also ergibt sich v_{p−2} = V_{(M_{p}+1)/4} = α^{(M_{p}+1)/4} + α^{−(M_{p}+1)/4} = α^{−(M_{p}+1)/4}(1 + α^{(M_{p}+1)/2}) = α^{−(M_{p}+1)/4}(1 + (1 + \sqrt{3})^{M_{p}+1}/(2 · 2^{(M_{p}−1)/2})). Da (1 + \sqrt{3})^{M_{p}+1} = (1+\sqrt{3})^{M_{p}}(1+\sqrt{3}) ≡ (1+\sqrt{3}^{M_{p}})(1+\sqrt{3}) ≡ (1+3^{(M_{p}−1)/2}\sqrt{3})(1+\sqrt{3}) ≡ 1 − 3 ≡ −2 (mod M_{p}), folgt v_{p−2} = 0 in ℤ/M_{p}ℤ[\sqrt{D}]. \underline{⇐:} Dann gilt also V_{(M_{p}+1)/4} = 0. Daher ist U_{(M_{p}+1)/4} ≠ 0 und U_{(M_{p}+1)/2} = 0. Also ist der Exponent e von (ℤ/M_{p}ℤ[\sqrt{D}])^{∗}/(ℤ/M_{p}ℤ)^{∗} durch (M_{p} + 1)/2 = 2^{p−1} teilbar. Sei M_{p} = ∏_{j=1}^{s} p_{j}^{α_{j}} eine Primfaktorisierung. Dann gilt nach Satz (6.22), dass e ein Teiler von ∏_{j=1}^{s} p_{j}^{α_{j}−1}kgV_{j}(p_{j} − (\frac{D}{p_{j}} )) ist, d.h. M_{p} hat einen Primteiler p_{j} mit p_{j} + 1 ≥ 2^{p−1} > M_{p}/3. Da M_{p} ungerade ist, folgt daraus p_{j} = M_{p} und M_{p} ist eine Primzahl.

Analog kann man auch 2^{n}h − 1 auf Primzahleigenschaft testen. Neben einer Faktorisierung von N − 1 oder N + 1 (oder einer Kombination aus beiden) kann man auch Faktorisierungen von N^{2} + N + 1,... benutzen. Problem: Zahlen werden größer und sind unwahrscheinlicher zu faktorisieren. Für allgemeines N wird man zum Beweis der Primzahleigenschaft einen der folgenden beiden Tests benutzen:

6.28 Definition: Sei N ∈ ℕ, ggT(6, N) = 1, a, b ∈ ℤ, ggT(N, 4a^{3} + 27b^{2}) = 1. Dann heißt

E := E_{a,b}(ℤ/Nℤ) := {(x, y) ∈ (ℤ/Nℤ)^{2} | y^{2} = x^{3} + ax + b} ∪ {O}

elliptische Kurve modulo N. Idee: Ist N eine Primzahl, so ist E eine Gruppe (Gruppenoperationen wie in (5.14)). Also rechnen wir in E wie in einer Gruppe. Ist eine Gruppenoperation nicht ausführbar, so haben wir einen nichttrivalen Teiler von N gefunden. Dann soll jeder Algorithmus hier abbrechen und N ist zusammengesetzt ausgeben.

6.29 Satz (Goldwasser-Kilian Test)

Sei E wie in (6.28). Gibt es P = (x_{0}, y_{0}) ∈ E\{O} und eine Primzahl q > (N^{1/4}+1)^{2} mit [q] · P = O, dann ist N eine Primzahl. Beweis: Angenommen, N ist keine Primzahl. Dann gibt es einen Primteiler p von N mit p ≤ \sqrt{N}. Betrachten E_{p} := E_{a,b}(ℤ/pℤ). Dann ist E_{p} eine elliptische Kurve und \overline{P} := (x_{0} (mod p), y_{0} (mod p)) ∈ E_{p} \ \{O\}. Da [q] · \overline{P} = O für eine Primzahl q, ist ord(\overline{P}) = q. Also ist |E_{p}| ≥ q > (N^{1/4} + 1)^{2} ≥ (\sqrt{p} + 1)^{2} = p + 2\sqrt{p} + 1, was in Widerspruch zum Satz von Hasse steht.

6.30 Bemerkung: (a) Vorteil: man kann E variieren.

(b) Schwierigkeit: Man muss schnell |E| bestimmen und einen großen Primteiler q von |E| finden.

(c) Die Primzahleigenschaft von q testet man wieder mit (6.29). Man erhält so ein Primzahlzertifikat: (E_{a,b}, P, q, N), (E_{a_{1},b_{1}}, P_{1}, q_{1}, q), …, (E_{a_{n},b_{n}}, P_{n}, q_{n}, q_{n−1}) mit dem man die Primzahleigenschaft von N leicht überprüfen kann. Damit q_{n} kleine Primzahl ist, ist n ∼ log(N).

(d) Zur Bestimmung von |E| gibt es 3 Methoden: Ein Analogon zu Shanks baby-step-giant-step-Methode: O(N^{1/4}), also zu schlecht.

Einen bemerkenswert schnellen Algorithmus von R. Schoof mit O(ln(N)^{8}) auf den ich hier nicht eingehen will. Geeignete Wahl von E, so dass man |E| aus der Theorie kennt:

6.31 Satz (Ohne Beweis): Sei E elliptische Kurve (über ℂ) mit a, b ∈ ℤ, Δ := 4a^{3}+27b^{2} ≠ 0 mit komplexer Multiplikation, d.h. es gibt Gruppenhomomorphismus φ : E → E mit φ^{2} = [−D], D ∈ ℕ quadratfrei. Sei p > 3 eine Primzahl mit p | Δ̸D und E_{p} die Reduktion von E modulo p. Dann gilt:

(i) Ist (\frac{−D}{p} ) = −1, dann ist |E_{p}| = p + 1. (ii) Gibt es α, β ∈ \frac{1}{2}ℤ mit α ≡ β (mod ℤ) und ⋆ α^{2} + Dβ^{2} = p, so ist |E_{p}| = p + 1 − 2α für eine geeignete Lösung (α, β) von ⋆. Beispiel: E : Y^{2} = X^{3}−X. φ : E → E : (x, y) ↦ (−x, iy) erfüllt φ^{2} = [−1]. Also gilt für p ≡ 3 (mod 4) (also (\frac{−1}{p}) = −1) dass |E_{p}| = p + 1 ist. Für p = 5 = (−1)^{2} + 2^{2} ist |E_{p}| = 5 + 1 − (−2) = 8. (vgl. Übung).

6.32 Bemerkung: Man kann allgemeine Formeln für solche Kurven E (für jede Lösung von ⋆) angeben. Das macht den Goldwasser-Kilian-Test zu einem probabilistischen Primzahltest dessen erwartete Laufzeit polynomial in ln(N) ist. Wir kommen abschließend zum APRCL-Test (Adleman, Pomerance, Rumely, Cohen, Lenstra).

6.33 Definition: Seien p, q Primzahlen mit p | q − 1, ζ_{p}, ζ_{q} primitive p-te bzw. q-te Einheitswurzeln in ℂ und C := ⟨ζ_{p}⟩ ≤ ℂ^{∗}. Sei χ : (ℤ/qℤ)^{∗} → C ein surjektiver (also nichttrivialer) Gruppenhomomorphismus. Dann heißt

τ(χ) := ∑_{a∈(ℤ/qℤ)^{∗}} χ(a)ζ_{q}^{a}

die Gauß-Summe zu χ. (Beispiel: p = 2, q ungerade Primzahl, χ(a) := (\frac{a}{q}) ∈ \{±1\}.)

6.34 Lemma: Sei χ wie in (6.33). Dann gilt τ(χ)τ(χ^{−1}) = qχ(−1).

Beweis: Wie der von der 1. Behauptung im quadratischen Reziprozitätsgesetz: Alle Summen laufen über (ℤ/qℤ)^{∗}. τ(χ)τ(χ^{−1}) = ∑_{a,b} χ(a)χ(b)^{−1}ζ_{q}^{a+b} = ∑_{c,b} χ(cb)χ(b^{−1})ζ_{q}^{cb+b} = ∑_{c} χ(c)(∑_{b} ζ_{q}^{(c+1)b}). Ist c ≡ −1 (mod q), so ist ∑_{b} ζ_{q}^{(c+1)b} = q − 1 sonst ist ∑_{b} ζ_{q}^{(c+1)b} = ∑_{a} ζ_{q}^{a} = −1. Also ist τ(χ)τ(χ^{−1}) = − ∑_{c} χ(c) + qχ(−1) = qχ(−1).

6.35 Lemma: Seien p, q, χ wie in (6.33). Ist N eine Primzahl, N | q̸p, so ist

τ(χ)^{N^{p−1}−1} ≡ χ(N) (mod Nℤ[ζ_{p}, ζ_{q}]).

Beweis: (vgl. 2. Behauptung im Beweis des quadratischen Reziprozitätsgesetzes) τ(χ)^{N^{p−1}} ≡ ∑_{a}(χ(a)ζ_{q}^{a})^{N^{p−1}} (mod N), da wir üeber einem Körper der Charakteristik N arbeiten. Weiter ist N^{p−1} ≡ 1 (mod p). Da χ(a) eine p-te Einheitswurzel ist, gilt also χ(a)^{N^{p−1}} = χ(a) für alle a ∈ (ℤ/qℤ)^{∗}. Sei b ∈ (ℤ/qℤ)^{∗} mit bN^{p−1} ≡ 1 (mod q). Dann ist

τ(χ)^{N^{p−1}} = ∑_{a} χ(a)ζ_{q}^{aN^{p−1}} = ∑_{a} χ(ab)ζ_{q}^{a} = χ(b)τ(χ).

Nun ist χ(b) = χ(N)^{1−p} = χ(N), da χ(N)^{p} = 1, also folgt

τ(χ)^{N^{p−1}} ≡ χ(N)τ(χ) (mod N).

Jetzt müssen wir nur noch durch τ(χ) teilen, um die Behauptung zu erhalten. Das machen wir mit Lemma 6.34, durch Multiplikation mit τ(χ^{−1})χ(−1)q^{−1}, das in ℤ/Nℤ[ζ_{p}, ζ_{q}] liegt.

6.36 Lemma: Sind r ≠ p Primzahlen, so sind die p-ten Einheitswurzeln modulo r verschieden: ζ_{p}^{i} ≡ ζ_{p}^{j} (mod r) ⇒ ζ_{p}^{i} = ζ_{p}^{j}. Beweis: X^{p} − 1 ∈ 𝔽_{r}[X] hat p verschiedene Nullstellen in seinem Zerfällungskörper.

6.37 Satz: (Rohform des APRCL-Tests)

Sei P eine endliche Menge von Primzahlen und Q ⊆ {q ∈ ℕ | q ist Primzahl und q− 1 ist Produkt von verschiedenen Primzahlen in P }. Sei z := ∏_{p∈P} p, w := ∏_{q∈Q} q und N ∈ ℕ ungerade ggT(N, wz) = 1. Angenommen, die folgenden beiden Bedingungen sind erfüllt:

(1) Für alle q ∈ Q, p ∈ P mit p | q − 1 gibt es einen Gruppenepimorphismus χ := χ_{p,q} : (ℤ/qℤ)^{∗} → ⟨ζ_{p}⟩ mit τ(χ)^{N^{p−1}−1} ≡ χ(N) (mod N).

(2) Für alle p ∈ P und alle Primteiler r von N gilt p^{e} | N^{p−1} − 1 ⇒ p^{e} | r^{p−1} − 1. Dann erfüllt jeder Primfaktor r von N, dass r ≡ N^{i} (mod w) für ein i ∈ {0, …, z− 1}. Beweis: Sei r ein Primfaktor von N. Wegen Bedingung (2), gibt es für alle p ∈ P Zahlen a_{p}(r), b_{p}(r), l_{p}(r) ∈ ℤ, mit p | b̸_{p}(r), so dass

\frac{r^{p−1} − 1}{N^{p−1} − 1} = \frac{b_{p}(r)}{a_{p}(r)} ≡ l_{p}(r) (mod p).

Sei l(r) ∈ {0, …, z − 1} mit l(r) ≡ l_{p}(r) (mod p) für alle p ∈ P. Zeigen nun, dass r ≡ N^{l(r)} (mod w) gilt. Dazu genügt es zu zeigen, dass χ_{p,q}(rN^{z−l(r)}) = 1 ist für alle q ∈ Q, p ∈ P mit p | q − 1. Sei also q ∈ Q, p ∈ P mit p | q − 1 und χ := χ_{p,q}. Dann gilt χ(r)^{a_{p}(r)} ≡ τ(χ)^{(r^{p−1}−1)a_{p}(r)} ≡ τ(χ)^{(N^{p−1}−1)b_{p}(r)} ≡ χ(N)^{b_{p}(r)} (mod r) mit Lemma 6.35. Also folgt mit Lemma 6.36, dass χ(r)^{a_{p}(r)} = χ(N)^{b_{p}(r)}, also χ(r) = χ(N)^{l(r)}.

6.38 Bemerkung:

(a) Zum Primzahlbeweis wählt man Q so, dass w > \sqrt{N}. Dann muss man nur noch überprüfen, ob x_{i} := N^{i} (mod w) ∈ {0, …, w − 1}, i = 0, …, z − 1 kein echter Teiler von N ist.

(b) In der Regel ist P klein (z.B. P = {2, 3, 5, 7, 11, 13, 17}), jedoch enthält Q dann große Primzahlen (z.B. 2 · 3 · 7 · 11 · 13 · 17 + 1 = 102103). Das macht das Berechnen von τ(χ) ∈ ℤ[ζ_{p}, ζ_{q}] sehr teuer. Abhilfe: Idee von Cohen/Lenstra: Rechne nur in ℤ[ζ_{p}].

(c) Bedingung (2) in (6.37) scheint sehr schwer nachzuprüfen. Sie ist aber trivialerweise erfüllt, wenn p^{2} | N̸^{p−1} − 1. Auch sonst gibt es hier leichter nachprüfbare Ersatzbedingungen.

(d) Für eine Beschreibung eines praktikablen Algorithmus sei auf Cohen, S. 438-458 verwiesen.

Abschnitt 7: Faktorisierungsalgorithmen.

7.1 Algorithmus: (Sieb des Eratosthenes) Eingabe: S ∈ ℕ. Ausgabe: ℙ_{≤S} := {p | p ≤ S, p ist Primzahl }. Algorithmus: Sei L := (2, 3, 4, …, S), s := ⌊\sqrt{S}⌋ und P := ∅. while L[1] ≤ s do

P := P ∪ {L[1]};

L := L\ Vielfache von L[1]; end while; P := P ∪ L; RETURN(P);

7.2 Algorithmus: (Probedivision, Trial Division) Eingabe: N, S ∈ ℕ. Ausgabe: {p^{α} | p ∈ ℙ_{≤S}, p^{α} || N}. Algorithmus: T := ∅. Bestimme ℙ_{≤S} mit Algorithmus (7.1). Für alle p ∈ ℙ_{≤S} bestimme maximales α mit p^{α} | N. P := P ∪ {p^{α}}. RETURN(P).

7.3 Bemerkung:

Probedivision wird bei vielen Faktorisierungsmethoden benutzt, um zunächst kleine Primteiler von N abzuspalten, meist noch vor einem Zusammengesetztheitstest. Nach dem Primzahlsatz (1896 Hadamard und gleichzeitig de la Vallée Poussin) ist |ℙ_{≤S}| ∼ S/ ln(S). Will man also N mit (7.2) vollständig faktorisieren, so müßte man zusätzlich zur Bestimmung von ℙ_{≤S} (für S = ⌊\sqrt{N}⌋) im schlimmsten Fall ca. 2\sqrt{N}/ ln(N) mal Dividieren. Die meisten Divisionen sind nutzlos, deshalb besser: P_{i} := ∏{p ∈ ℙ_{≤S} | 100(i − 1) < p < 100i} und ggT(N, P_{i}) berechnen. Sieb des Eratosthenes ist auch teuer, anstelle von ℙ_{≤S} kann man auch {2, 3}∪{6k+1 | k = 1, …, ⌊(S − 1)/6⌋} benutzen. Ein besserer Algorithmus zum Abspalten kleiner Primteiler ist der folgende Pollardρ-Algorithmus, ein probabilistischer Algorithmus mit erwarteter Laufzeit O(N^{1/4}).

7.4 Lemma: Sei f : ℤ/Nℤ → ℤ/Nℤ, x_{0} ∈ ℤ/Nℤ, x_{i} := f(x_{i−1}) für i = 1, 2, . . .. Dann gibt es m > n mit x_{i+n} = x_{i+m} für alle i ∈ ℕ, wobei man erwarten kann, dass man m, n so finden kann, dass |m − n| < 2\sqrt{N} gilt. Beweis: (vgl. Cohen S. 423).

7.5 Algorithmus: (Pollard ρ).

Eingabe: N ∈ ℕ, S ∈ ℕ Ausgabe: Mit großer Wahrscheinlichkeit alle (Prim)Teiler p von N mit \sqrt{p} < S. Algorithmus: Sei f ∈ ℤ[X], F := ∅.

(1) Wähle x = y ∈ {0, …, N − 1}. for i from 0 to S do

x := f(x) (mod N); y := f(y) (mod N); y := f(y) (mod N); d := ggT(x − y, N); if d = N then goto (1); end if; if d > 1 then N := N/d; F := F ∪ {d}; end if;

end for; RETURN(F); Idee: Ist p | N, p << N, so wird die Folge (x_{n} (mod p)) sehr viel eher periodisch mit einer kürzeren Periode m als modulo N, d.h. es gilt p | (x_{i} − x_{i+m}) für alle geügend großen i. Insbesondere teilt p den ggT(x_{kn} − x_{2kn}, N) für genügend großes k.

7.6 Bemerkung:

(a) Um nicht zu oft ggT(x_{n} −x_{2n}, N) zu berechnen, kann man z.B. l Schritte zusammenfassen und zunächst P := ∏_{j=kl}^{(k+1)l−1}(x_{j} − x_{2j}) und dann ggT(P, N) berechnen.

(b) Offensichtlich schlechte Wahlen von f: f(X) = X + 1, f(X) = X^{2}, u.ä.

(c) Der Algorithmus benötigt wenig Speicher, sehr gut um kleine Primteiler zu finden, schnell in MAPLE programmiert (Ausprobieren!).

(d) Die Werte x_{2i} mit 2i < S werden doppelt berechnet. Folgende Modifikation bringt 25 Prozent Zeitersparnis: Man testet nur die x_{j} − x_{2^{k}} mit 3 · 2^{k−1} < j ≤ 2^{k+1}, k = 0, 1, 2, . . .. Man muss also zunächst y := x_{2^{k}} berechnen, dann die Werte x_{2^{k}+1}, …, x_{2^{k}+2^{k−1}} wegschmeißen und für die x = x_{j} mit 3 · 2^{k−1} < j ≤ 2^{k+1} den ggT(x − y, N) berechnen. Den Wert x_{2^{k+1}} speichert man dann wieder als neues y.

Einschub: Faktorisieren von F_{n} = 2^{(2^{n})} + 1.

1. spektakuläre Anwendung von Pollard-ρ: 1980: 16-stelligen Primteiler von F_{8} in wenigen Stunden Rechenzeit.

7.7 Satz: (Legendre)

Sei n ∈ ℕ, a, b ∈ ℤ mit ggT(a, b) = 1, N := a^{n} + b^{n} und p > 2 ein Primteiler von N. Dann gilt entweder p | a^{d} + b^{d} für einen echten Teiler d von n oder p = 2kn + 1 für ein k ∈ ℕ. Beweis: p | a^{n} + b^{n} ⇒ p | a̸b und c := \frac{a}{b} ist eine Einheit modulo p, die c^{n} ≡ −1 (mod p) erfüllt. Sei d := ord(c + (pℤ)) die Ordnung von c in (ℤ/pℤ)^{∗}. Dann ist d gerade und d/2 ein Teiler von n. Da p | (a^{d/2} + b^{d/2}) können wir annehmen, dass d/2 = n. Also ist d = 2n ein Teiler von p − 1 und damit p = 2kn + 1 für ein k in ℕ.

7.8 Lemma F_{n} := 2^{(2^{n})} + 1. Dann gilt F_{n+1} = 2 + F_{0}F_{1} ⋯ F_{n}. Beweis: Nachrechnen.

7.9 Folgerung: (a) Die Fermat Zahlen sind paarweise teilerfremd. (b) Jeder Primteiler p von F_{n} erfüllt p = 2^{n+1}k + 1 für ein k ∈ ℕ. Ist n > 1, so gilt sogar p = 2^{n+2}k + 1 für ein k ∈ ℕ. Beweis: Aus (7.7) folgt 2^{2^{n}} ≡ −1 (mod p), d.h. ord(2) teilt 2^{n+1} teilt p − 1. Ist n > 1, so ist p damit kongruent zu 1 modulo 8, also ist 2 ein Quadrat modulo p. D.h. die Ordnung von 2 ∈ (ℤ/pℤ)^{∗} teilt sogar (p − 1)/2.

7.10 Bemerkung: Um Primfaktoren der Form 2kn + 1 mit k ∈ ℕ zu finden, wählt man im Pollard ρ Algorithmus f = X^{n} + a. Dann hat nämlich x_{i} − x_{j} = x_{i−1}^{n} − x_{j−1}^{n} viele Primfaktoren der Form 2kn + 1.

7.11 Definition: Sei B ∈ ℕ.

(i) n ∈ ℕ heißt B-glatt, falls alle Primteiler von n kleiner oder gleich B sind. (ii) n ∈ ℕ heißt B-potenzglatt, falls alle Primzahlpotenzen, die n teilen, kleiner oder gleich B sind.

7.12 Lemma: Sei p eine Primzahl, so dass p − 1 eine B-potenzglatte Zahl ist. Sei M := kgV{n ∈ ℕ | n ≤ M} = ∏{p^{s} | p ist Primzahl und s maximal mit p^{s} ≤ M}. Dann gilt p | a^{M} − 1 für alle a ∈ ℕ mit p | a̸.

7.13 Algorithmus (Pollard (p − 1), Schritt 1)

Eingabe: N ∈ ℕ, Schranke B. Ausgabe: Wahrscheinlich einen Primteiler p | N für den p − 1 eine B-potenzglatte Zahl ist. Algorithmus: Bestimme ℙ_{≤B} = {p_{1}, …, p_{s}} (mit (7.1)) und für jedes p_{i} das maximale α_{i} ∈ ℕ mit p_{i}^{α_{i}} ≤ B. Wähle c ∈ {2, …, N − 2} zufällig. z:=0; for i from 1 to s do

for j from 1 to α_{i} do c := c^{p_{i}} (mod N); z:=z+1;

end for;

if (z ≥ 200) then z:=0; g:=ggT(c-1,N); if (g = N) then RETURN(FAIL); end if; if (g > 1) then RETURN(g); end if;

end if; end for; g:=ggT(c-1,N); if ((g=1) or (g=N)) then RETURN(FAIL); end if; RETURN(g);

7.14 Bemerkung: Es gibt verschiedene Gründe, weshalb (7.13) versagt:

(i) In c − 1 gehen alle Primteiler von N auf. Dann lohnt es sich, die Suche zu verfeinern, also den ggT-Test nach jedem Potenzieren zu machen, oder auch das Potenzieren in einer anderen Reihenfolge durchzuführen. Beispiel: N = 23 · 89, B = 11. Dann ist c − 1 erst nach Potenzieren mit 11 durch eine der beiden Primzahlen teilbar, dann aber auch gleich durch N. Abhilfe: Am Ende die 2-Potenzen behandeln. (ii) Weitaus häufiger tritt der Fall auf, dass N keine Primteiler p hat, für die p − 1 eine B-potenzglatte Zahl ist. Dann ist der \underline{Schritt 2} hilfreich: Sei c das Endergebnis des 1. Schrittes, also eine ∏_{i=1}^{s} p_{i}^{α_{i}}-te Potenz. Für eine Schranke B′ > B seien q_{1} < q_{2} < …, < q_{t} die Primzahlen q mit B < q ≤ B′. Speichere q_{1}, d_{2} := q_{2} − q_{1}, d_{3} := q_{3} − q_{2}, …, d_{t} := q_{t} − q_{t−1} und berechne c^{q_{1}}, c^{q_{i+1}} = c^{q_{i}}c^{d_{i+1}} für i = 1, …, t − 1. und teste, ob ggT(c^{q_{i}} − 1, N) > 1 für ein i = 1, …, t.

7.15 Bemerkung: Analog zur Glattheit von p − 1 kann man auch die von p + 1 benutzen, indem man in (ℤ/Nℤ[\sqrt{D}])^{∗}/(ℤ/Nℤ^{∗}) rechnet. Allerdings ist es nicht so klar, wie man ein D findet, das kein Quadrat modulo dieser (unbekannten) Primteiler von N ist. Mit elliptischen Kurven kann man solche p finden, für die in der Nähe von p eine glatte Zahl existiert. Das führt zu einem der wichtigsten modernen Faktorisierungsverfahren:

7.16 Beispiel: N = 1098413 = 563 · 1951, E : Y^{2} = X^{3} − X + 1. Dann ist |E(𝔽_{563})| = 560 = 2^{4} · 5 · 7 und |E(𝔽_{1951})| = 1948 = 2^{2} · 487. Mit einem Analogon zum Pollard (p − 1)-Algorithmus wird man P_{0} := (0, 1) ∈ E(ℤ/Nℤ) potenzieren bis man [560]P_{0} z.B. als

[560]P_{0} = [640]P_{0} + [−80]P_{0} = (289957, 901426) ⊕ (590036, −204995)

ausrechnen muss. Die Formeln für die Addition benutzen die Berechnung von λ = (y_{2} − y_{1})/(x_{2} − x_{1}). Also muss man x_{2} − x_{1} = 590036 − 289957 = 300079 modulo N invertieren (mit dem erweiterten Euklidischen Algorithmus zur Berechnung des ggT). Dabei findet man ggT(N, 300079) = 563 also einen nichttrivialen Teiler von N.

7.17 Algorithmus: (ECM, Elliptische Kurven Methode)

Eingabe: N ∈ ℕ, Schranken B, B′ (für Glattheit), S (Anzahl der Kurven). Ausgabe: Wahrscheinlich einen nichttrivialen Teiler von N. Algorithmus: (vgl. Pollard-(p − 1)) Bestimme ℙ_{≤B} = {p_{1}, …, p_{s}} (mit (7.1)) und für jedes p_{i} das maximale α_{i} ∈ ℕ mit p_{i}^{α_{i}} ≤ B. Bestimme {B < q ≤ B′ | q ist Primzahl } = {q_{1} < q_{2} < … < q_{t}} und speichere (q_{1}, d_{2} := q_{2} − q_{1}, d_{3} = q_{3} − q_{2}, …, d_{t} = q_{t} − q_{t−1}). for a from 0 to S do

if g := ggT(N, 4a^{3} + 27) > 1 then RETURN(g) end if; E : Y^{2} = X^{3} + aX + 1; (elliptische Kurve modulo N) P := (0, 1) ∈ E; for i from 1 to s do

for j from 1 to α_{i} do P := [p_{i}] · P;

end for; end for; Q := [q_{1}] · P; for i from 2 to t do

Q := Q + [d_{i}] · P; end for;

end for; Dabei ist die Abbruchbedingung in dem Befehl P := [p_{i}] · P versteckt. Kann man eine Rechnung nicht durchführen, so hat man einen nichttrivialen Teiler von N gefunden.

7.18 Bemerkung: (a) Die ECM ist der einzige moderne Faktorisierungsalgorithmus, dessen Laufzeit wesentlich von der Größe des kleinsten Primteilers von N abhängt und nicht von der von N. Mit ihr kann man ca. 50-stellige Primfaktoren von mehr als 1000-stelligen Zahlen bestimmen.

(b) Wie auch die anderen modernen Faktorizierungsmethoden ist die ECM sehr leicht parallelisierbar: Man kann verschiedene Rechner, verschiedene elliptische Kurven ausprobieren lassen.

(c) Die aktuellen Rekorde der ECM sind z.B.: 54-stelligen Primteiler von (6^{43} − 1)^{42} + 1 ∼ 0.2 · 10^{1406} sowie 54-stelligen Primteiler von (3^{64} − 1)^{63} + 1 ∼ 0.6 · 10^{1924}.

(d) Die ECM ist ein subexponentieller Algorithmus, d.h. die erwartete Laufzeit wächst langsamer als jede positive Potenz von N: (erw. Laufzeit)/N^{c} → 0 für jedes c > 0. Genauer sei L_{M}(v, c) := exp(c · ln(M)^{v} ln ln(M)^{1−v}). Dann ist die erwartete Laufzeit von ECM in etwa L_{p}(1/2, 2+o(1)) wo p den kleinsten Primteiler von N bezeichnet.

Jetzt kommen wir zur zweiten Sorte von Faktorisierungsalgorithmen, deren Laufzeit im wesentlichen von der Größe von N abhängt und nicht von der des zweitgrößten Primteilers von N. Die Ideen der modernen Methoden findet man schon in den klassischen Algorithmen, die ich deshalb vorstellen möchte, obwohl sie zum Faktorisieren keine große Rolle mehr spielen. Wir nehmen an, dass N keine kleinen Primteiler mehr hat (also insbesondere ungerade ist) und auch kein Quadrat oder eine andere Potenz einer kleineren Zahl ist.

7.19 Algorithmus (Fermat)

Idee: Sei N = a·b ungerade. Dann ist N = (\frac{a+b}{2})^{2}−(\frac{a−b}{2})^{2} = x^{2}−y^{2} = (x−y)(x+y) die Differenz von 2 Quadraten. Dabei gilt x ≥ \sqrt{N}.

Eingabe: N ∈ ℕ ungerade, zusammengesetzt. Ausgabe: a, b ∈ ℕ_{>1} mit N = a · b. Algorithmus: x := ⌈\sqrt{N}⌉; z := x^{2} − N; while x < N do

if (z = y^{2} für ein y ∈ ℕ) then

RETURN ((x-y),(x+y) ); end if; z:=z+2x+1; x:=x+1;

end while;

7.20 Bemerkung: (7.19) findet die Faktoren a ∼ b ∼ \sqrt{N} recht schnell, die für Trial Division den worst case darstellen. Im Fall, dass z kein Quadrat ist, wird Information weggeschmissen: z ≡ x^{2} (mod N) ⇒ z ≡ □ (mod p) für jeden Primteiler p von N. Findet man also z.B. z ≡ 2 ≡ x^{2} (mod N), so weiss man, dass die Primteiler von N kongruent ±1 modulo 8 sind. Gauss und Legendre erzeugten systematisch kleine quadratische Reste modulo N z.B. mit der Kettenbruchentwicklung von \sqrt{kN} (k ∈ ℕ).

7.21 Definition: Eine Kettenbruchentwicklung ist ein Ausdruck der Form

b_{0} + \frac{a_{1}}{b_{1} + _{\frac{a_{2}}{b_{2}+_{\frac{a_{3}}{b_{3}+ \frac{a_{4}}{...}}}}}} = b_{0} + \frac{a_{1} |}{| b_{1}} + \frac{a_{2} |}{| b_{2}} + \frac{a_{3} |}{| b_{3}} + ….

Sie heißt regulär, falls a_{i} = 1 und b_{i} ∈ ℤ_{≥0} für alle i > 0 gilt. Die reguläre Kettenbruchentwicklung einer Zahl x = x_{0} ∈ ℝ berechnet man, indem man für i = 0, 1, … b_{i} := ⌊x_{i}⌋, x_{i+1} := \frac{1}{x_{i}−b_{i}} setzt. Wir nennen auch die Folge (x_{i}, b_{i}) die reguläre Kettenbruchentwicklung von x. Vergleichen Sie die reguläre Kettenbruchentwicklung einer rationalen Zahl mit dem Euklidischen Algorithmus.

7.22 Satz: Seien A_{n}, B_{n} ∈ ℕ mit ggT(A_{n}, B_{n}) = 1, so dass \frac{A_{n}}{B_{n}} = b_{0} + \frac{1|}{|b_{1}} + … + \frac{1|}{|b_{n}} die n-te Partialsumme einer regulären Kettenbruchentwicklung ist. Dann gilt:

(a) A_{0} = b_{0}, B_{0} = 1, A_{1} = b_{1}A_{0} + 1, B_{1} = b_{1}B_{0}, und für n ≥ 2: A_{n} = b_{n}A_{n−1} + A_{n−2}, B_{n} = b_{n}B_{n−1} + B_{n−2}.

(b) A_{n}B_{n−1} − A_{n−1}B_{n} = (−1)^{n−1}. Beweis: (a) Induktion über n. n = 0, 1 Klar. Induktionsschluss:

\frac{A_{n+1}}{B_{n+1}} = \frac{b_{n+1}A_{n} + A_{n−1}}{b_{n+1}B_{n} + B_{n−1}} = \frac{(b_{n} + b_{n+1}^{−1})A_{n−1} + A_{n−2}}{(b_{n} + b_{n+1}^{−1})B_{n−1} + B_{n−2}} = b_{0} + \frac{1 |}{| b_{1}} + … + \frac{1 |}{| b_{n} + \frac{1}{b_{n+1}}}

wobei wir im letzten Schrit die Induktionsvoraussetzung benutzen.

(b) Folgt aus (a) mit Induktion über n.

7.23 Satz: Sei x = b_{0} + \frac{1|}{|b_{1}} + … ∈ ℝ_{>0} eine reguläre Kettenbruchentwicklung. Dann ist 0 ≤ (−1)^{n}(x − \frac{A_{n}}{B_{n}}) < \frac{1}{B_{n}^{2}} .

Beweis:

x = lim_{n→∞} \frac{A_{n}}{B_{n}} = \frac{A_{n}}{B_{n}} + (\frac{A_{n+1}}{B_{n+1}} − \frac{A_{n}}{B_{n}}) + (\frac{A_{n+2}}{B_{n+2}} − \frac{A_{n+1}}{B_{n+1}} ) + …

= \frac{A_{n}}{B_{n}} + ((−1)^{n} \frac{1}{B_{n}B_{n+1}} ) − (−1)^{n}(\frac{1}{B_{n+1}B_{n+2}} − \frac{1}{B_{n+2}B_{n+3}} + …).

Also ist

0 ≤ (−1)^{n}(x − \frac{A_{n}}{B_{n}}) = \frac{1}{B_{n}B_{n+1}} − (\frac{1}{B_{n+1}B_{n+2}} − \frac{1}{B_{n+2}B_{n+3}} + …) <= \frac{1}{B_{n}^{2}}

da B_{n} monoton steigend ist.

7.24 Satz: Sei N ∈ ℕ kein Quadrat, (x_{i}, b_{i}) die reguläre Kettenbruchentwicklung von \sqrt{N} =: x_{0}. Definieren Q_{0} := 1, P_{1} := b_{0}, und für n ≥ 1:

Q_{n} := \frac{N − P_{n}^{2}}{Q_{n−1}} , P_{n+1} := b_{n}Q_{n} − P_{n}

Dann gilt für alle n ≥ 1:

(a) x_{n} = \frac{Q_{n−1}}{\sqrt{N}−P_{n}} = b_{n} + \frac{\sqrt{N}−P_{n+1}}{Q_{n}}.

(b) P_{n}, Q_{n} ∈ ℤ_{≥0}, P_{n} ≤ \sqrt{N}, Q_{n} ≤ 2\sqrt{N}.

(c) A_{n−1}^{2} − NB_{n−1}^{2} = (−1)^{n}Q_{n}. Die (−1)^{n}Q_{n} sind also kleine quadratische Reste modulo N. Beweis als Übung.

7.25 Beispiel (Legendre):

N = 333667, x_{0} = \sqrt{N}, b_{0} = 577, x_{1} = 1 + \frac{\sqrt{N}−161}{738}, x_{2} = 1 + \frac{\sqrt{N}−256}{417}, x_{3} = 1 + \frac{\sqrt{N}−387}{643}, x_{4} = 3 + \frac{\sqrt{N}−471}{286}, …. Also sind −738 = −2 · 3^{2} · 41, 417 = 3 · 139, −643 = −643, 286 = 2 · 11 · 13, … 69 = 69, −288 = −2^{5} · 3^{4}, …, 10 = 2 · 5 Quadrate modulo N. Z.B. folgt aus der vorletzten Gleichheit, dass für jeden Primteiler p von N gilt: −2 ≡ □ (mod p) also p = 8m + 1 oder p = 8m + 3 mit m ∈ Z. Insgesamt findet Legendre genügend Kongruenzen um die Menge der Primteiler p von N mit p < \sqrt{N} als Teilmenge von \{83, 107, 163, 401, 409, 467, 569\} zu erkennen und durch Dividieren festzustellen, dass N eine Primzahl ist. Aus der Idee, Kettenbrüche zur Erzeugung kleiner quadratischer Reste modulo N zu benutzen, entstand die erste moderne Methode zum Faktorisieren grosser Zahlen, CFRAC (1975). Sie beruht, wie auch die folgenden Methoden auf der folgenden Beobachtung:

7.26 Beobachtung: Angenommen, es gibt x, y, k ∈ ℤ mit

x^{2} − y^{2} = kN also x^{2} ≡ y^{2} (mod N).

Dann gilt kN = (x − y)(x + y) und ggT(x − y, N) ist mit grosser Wahrscheinlichkeit ein nichttrivialer Teiler von N.

7.27 Algorithmus (CFRAC) (Morrison, Brillhardt, 1975) Eingabe: N ∈ ℕ ungerade, keine Potenz Ausgabe: (nichttrivialer) Teiler von N. Algorithmus:

(0) Wähle Schranke S und bestimme ℙ_{≤S} = {p_{1}, …, p_{s}} mit dem Sieb des Eratosthenes.

(1) Wähle k ∈ ℕ geeignet.

(2) Bestimme die Kettenbruchentwicklung von \sqrt{kN} und damit R_{n} := (−1)^{n}Q_{n} ≡ A_{n−1}^{2} (mod N). Speichere nur die S-(semi)-glatten R_{n}, also solche R_{n}, mit

R_{n} = (−1)^{e_{n,0}}p_{1}^{e_{n,1}} … p_{s}^{e_{n,s}} · P_{n}

mit p_{i} | P̸_{n} und S < P_{n} < S^{2}. als Zeile einer Exponentenmatrix:

E, P, X := ( \begin{matrix}⋮ & ⋮ & ⋮ & ⋮ \\ e_{n,0} & e_{n,1} & … & e_{n,s} \\ ⋮ & ⋮ & ⋮ & ⋮ \end{matrix} ) , ( ⋮ ; P_{n} ; ⋮ ) , ( ⋮ ; A_{n−1} ; ⋮ )

(3) Verkleinere E: Ist P_{n} ≠ 1, so addiere erste Zeile, in der P_{n} auftaucht zu allen anderen Zeilen mit gleichem P_{n} (und multipliziere die entsprechenden Einträge in P, X) und streiche dann diese erste Zeile (in E, P und X).

(4) Bestimme Vektoren aus dem Kern von E (mod 2), also k := (k_{1}, …, k_{l}) ∈ {0, 1}^{l} mit kE =: (a_{1}, …, a_{l}) ∈ 2ℤ^{l}.

(5) Ausgabe: Setze

y := ∏_{j=1}^{l} P_{j}^{k_{j}} · ∏_{i=1}^{s} p_{i}^{a_{i}/2}, x := ∏_{j=1}^{l}(X[j])^{k_{j}}.

RETURN(ggT(x − y, N))

7.28 Beispiel: (Morrison, Brillhardt)

N = 13 290 059 alle Primteiler p von R_{i} erfüllen p ≤ 113

\begin{matrix}i & A_{i} mod N & R_{i} \\ 5 & 171 341 & −1 · 2 · 5^{2} · 41 \\ 10 & 6 700 527 & 31 · 43 \\ 22 & 5 235 158 & 41 · 113 \\ 23 & 1 914 221 & −1 · 2 · 113 \\ 26 & 11 455 708 & 2 · 31 · 53 \\ 31 & 1 895 246 & −1 · 2 · 5^{2} · 113 \\ 40 & 3 213 960 & 2 · 43 · 53 \end{matrix}

−1 2 5 31 41 43 53 113
v(5) 1 1 2 . 1 …
v(10) … 1 . 1 . .
v(22) …. 1 . . 1
v(23) 1 1 . . . . . 1
v(26) . 1 . 1 . . 1 .
v(31) 1 1 2 …. 1
v(40) . 1 … 1 1 .
(1, 0, 1, 1, 0, 0, 0) ∈ Kern ⇒ y^{2} = R_{5} · R_{22} · R_{23}
y = 2 · 5 · 41 · 113, x = A_{5} · A_{22} · A_{23}

liefert

ggT(x − y, N) = 4261 und N = 3119 · 4261.

7.29 Bemerkung: Teuer bei CFRAC: häufiges vergebliches Faktorisieren der Q_{n}. Neue Idee: Anstelle von Q_{n} Werte eines Polynoms f ∈ ℤ[X] betrachten: p | f(m) ⇒ p | f(m + lp) für alle l ∈ ℤ. Dadurch kann man eine Siebstrategie einsetzen:

7.30 Algorithmus: (Quadratisches Sieb, Pomerance 1982)

Eingabe: N ∈ ℕ ungerade, keine Potenz Ausgabe: (nichttrivialer) Teiler von N. Algorithmus:

(1) m := ⌊\sqrt{N}⌋; f(X) := (X + m)^{2} − N;

(2) F := {q_{1}, …, q_{s}} Menge von paarweise teilerfremden Zahlen, die sogennante factor base (z.B. F = ℙ_{≤S}, wobei es sinnvoll ist, die kleinen Primzahlen durch geeignete Potenzen zu ersetzen).

(3) Bestimme z_{i} = f(i), i = 0, ±1, ±2, … und speichere log(z_{i}) =: t_{i} (Logarithmus zu einer geeigneten Basis).

(4) Für q ∈ F bestimme i_{q}, j_{q} ∈ {0, …, q − 1} mit q | f_{(}i_{q}), q | f(j_{q}) (falls solche Zahlen existieren). Dann gilt q | f(i_{q} + ql) für alle l ∈ ℤ. Setze also

t_{i_{q}+ql} := t_{i_{q}+ql} − log(q), t_{j_{q}+ql} := t_{j_{q}+ql} − log(q) für alle l ∈ ℤ

Philosophie: Ist t_{i} am Ende klein, so faktorisiert z_{i} über F (mit eventuellem kleinen Rest). Weiter wie bei CFRAC:

(5) Faktorisiere die z_{i} mit t_{i} klein über ℙ_{≤S}:

z_{n} = (−1)_{n,0}^{e} ∏_{j=1}^{s} p_{j}^{e_{nj}}P_{n}

E, P, X := ( \begin{matrix}⋮ & ⋮ & ⋮ & ⋮ \\ e_{n,0} & e_{n,1} & … & e_{n,s} \\ ⋮ & ⋮ & ⋮ & ⋮ \end{matrix} ) , ( ⋮ ; P_{n} ; ⋮ ) , ( ⋮ ; m + n ; ⋮ )

(6), (7) wie bei CFRAC (3), (4).

7.31 Bemerkung: Ist |F| groß, so braucht man viele Werte z_{i}. Also wird |i| und damit |z_{i}| groß, d.h. man findet weniger glatte z_{i}. Als Abhilfe benutzt man anstelle von einem Polynom eine ganze Familie von Polynomen: a, b, c ∈ ℤ, b^{2} − N = a^{2}c. U(X) := a^{2}X + b, V (X) := a, W (X) := a^{2}X^{2} + 2bX + c. Dann ist

U(X)^{2} ≡ V (X)^{2}W (X) (mod Nℤ[X]).

Man siebt die Werte W (i) (jedesmal neu für unterschiedliche Wahlen der a, b, c.). Dann nennt man das Verfahren das MPQS: multiple polynomial quadratic sieve

7.32 Bemerkung: Das MPQS ist ein sehr guter general purpose Algorithmus für Zahlen N < 10^{80} (Laufzeit im Stundenbereich). Die Laufzeit von MPQS ist O(L_{N}(1/2, c)) für eine Konstante c. Rekorde:

# Stellen Jahr # MIPS Jahre Algorithmus
116  1990  275  MPQS
120  1993  830  MPQS
129  1994  5000  MPQS
130  1996  1000  NFS
140  1999  2000  NFS
155  1999  8000  NFS

Die Laufzeit von NFS ist O(L_{N}(1/3, c)) für eine Konstante c.

7.33 Grobe Idee des Zahlkörpersiebs (NFS) (Pollard, 1988)

(1) Wähle f ∈ ℤ[X] irreduzibel, m ∈ ℤ mit f(m) ≡ 0 (mod N) und α ∈ ℂ mit f(α) = 0. Dann ist

Φ : ℤ[α] → ℤ/Nℤ; α ↦ m + Nℤ

ein Ringhomomorphismus. Der Einfachheit halber nehmen wir an, dass f normiert ist. Sei n :=Grad(f). \underline{Ziel:} Suche (a_{i}, b_{i}) ∈ ℤ^{2}, ggT(a_{i}, b_{i}) = 1 so dass

(⋆) ∏(a_{i} − b_{i}α) = γ^{2}, γ ∈ ℤ[α]
∏(a_{i} − b_{i}m) = x^{2}, x ∈ ℤ

Schreibt man γ = ∑_{j=0}^{n−1} c_{j}α^{j} mit c_{j} ∈ ℤ, so ist y := ∑_{j=0}^{n−1} c_{j}m^{j} ≡ Φ(γ) (mod N) mit x^{2} ≡ y^{2} (mod N). Dazu siebe die (a − bα) und (a − bm). Eine notwendige Bedingung für (⋆) ist, dass ∏ Norm(a_{i} − b_{i}α) = Norm(γ)^{2} ein Quadrat in ℤ ist. Dabei ist P_{b}(a) := Norm(a − bα) = b^{n}f(a/b) für festes b ein Polynom in a. Siebe also die P_{b}(a) für die verschiedenen b über ℙ_{≤S}. Beim Aufstellen der Matrix ist zu beachten, dass es in ℤ[α] mehrere Primideale ℘_{j} mit gleicher Primzahlnorm p geben kann. Von ihnen teilt aber höchstens eines das Ideal (a−bα), je nach Wert a/b (mod p). Also braucht man die Primideals ℘_{j} nicht auszurechnen und kann die Matrix aufstellen, ohne in ℤ[α] wirklich zu rechnen.

Ein Element im Kern der Matrix entspricht einem Ideal Γ⊴ℤ[α] mit ∏(a_{i}−b_{i}α) = Γ^{2}. Auch für ℤ brauchten wir noch eine zusätzliche Spalte für die Einheiten ±1. In ℤ[α] gibt es i.a. mehr Einheiten. Außerdem ist Γ nicht notwendig ein Hauptideal. Also braucht man weitere notwendige Bedingungen dafür, dass die linke Seite von (⋆) ein Quadrat eines Elements in ℤ[α] ist. Dazu wählt man weitere Primideale 𝔮_{j} mit Norm(𝔮_{j}) = q_{j} ∈ ℙ_{>S}. Dann ist ℤ[α]/𝔮_{j} ≅ 𝔽_{q_{j}}. Für jedes diese 𝔮_{j} bekommt E eine zusätzliche Spalte, in die man eine 0 einträgt, falls (a_{i} − b_{i}α) + 𝔮_{j} ∈ (𝔽_{q_{j}}^{∗})^{2} und eine 1 sonst. Jetzt entspricht einem Element im Kern(E (mod 2)) mit großer Wahrscheinlichkeit einer Lösung von (⋆).

7.34 Beispiel: te Riele et alii (Februar 1999) RSA-140 = 21290 24631 82587 57547 49788 20162 71517 49780 67039 63277 21627 82333 83215 38194 99840 56495 91136 65738 53021 91831 67831 07387 99531 72308 89569 23087 34419 36471 = 33987 17423 02843 85545 30123 62761 38758 35633 98649 59695 97423 49092 93027 71479 × 62642 00187 40128 50961 51654 94826 44422 19302 03717 86235 09019 11166 06539 46049

f(t) =  43 96820 82840 t^{5}
+ 39031 56785 38960 t^{4}
– 7387 32529 38929 94572 t^{3}
– 19 02715 324374 29887 14824 t^{2}
– 6 34410 25694 46461 79139 30613 t

+ 31855 39170 71474 35039 22235 07494

m= 3 44356 57809 24253 69517 79007. Insgesamt ca. 9 CPU-Jahre Rechenzeit: 2000 h zur Auswahl von f. Seiben: 185 Rechner insgesamt 8,9 CPU-Jahre, Schranke ∼ 12 Mio. Matrix: 5 Mio. Zeilen und Spalten, 100 h zum Finden von Elementen im Kern. Wurzelziehen: 14-20 h.

7.35 Bemerkung:

\underline{Vorteil des NFS}: Freiheit der Wahl von f. Wahrscheinlichkeit, dass a − bα glatt ist, ist sehr viel größer als bei MPQS. \underline{Preis}: Rechnen in ℤ[α] kompliziert und wird bis auf das Wurzelziehen vermieden. E hat mehr Spalten: Für die a_{i} − b_{i}m: ℙ_{≤S}, Für die a_{i} − b_{i}α: Primideale mit Norm in ℙ_{≤S} (eventuell mehr als eins pro Primzahl) (zum Sieben) und Primideale mit größerer Norm, um sicherzustellen, dass ein Element im Kern von E (mod 2) auch wirklich einem Quadrat eines Elements in ℤ[α] entspricht und nicht nur einem Quadrat eines Ideals. Bisher größte Zahl, die mit dem Zahlkörpersie faktorisiert wurde: N = (10^{211} − 1)/9 = 111111111 … 11111111 (211 Einsen). Die spezielle Form von N wurde zur Wahl von f und m ausgenutzt: f(X) = 10X^{6} − 1, m = 10^{35}. Insgesamt fast 11 CPU-Jahre Rechenzeit.

Abschnitt 8: Gröbnerbasen.

Situation: K Körper (K = ℚ, ℝ, 𝔽_{p}, …) und R := K[x_{1}, …, x_{n}] der Polynomring über K in n Unbestimmten. Ist I ⊴ R, so stellen sich folgende algorithmische Probleme: Rechnen in R/I. Berechne dim_{K}(R/I). f ∈ R, entscheide ob f ∈ I. Ist n = 1, so kann man diese Probleme mit dem Euklidischen Algorithmus angehen. Sei V (I) := {a := (a_{1}, …, a_{n}) ∈ K^{n} | f(a) = 0 für alle f ∈ I}. Entscheide ob V (I) = ∅. Ist V (I) endlich? Bestimme Elemente aus V (I). Ist I von linearen Polynomen erzeugt, so kann man diese Probleme mit dem Gauß-Algorithmus lösen. Das Ziel dieses Abschnittes ist, ein schönes Erzeugendensystem für I anzugeben, mit dessen Hilfe man diese Probleme algorithmisch lösen kann, indem man Gauß- und Euklidischen Algorithmus gleichzeitig verallgemeinert.

8.1 Satz (Hilbertscher Basissatz) (i) I ⊴ R ⇒ Es gibt f_{1}, …, f_{s} ∈ R mit I = (f_{1}, …, f_{s}). (ii) R ist Noethersch, d.h. ist I_{1} ⊂ I_{2} ⊂ … eine aufsteigende Kette von Idealen in R, so gibt es ein N mit I_{N} = I_{N+1} = . . ..

8.2 Lemma:

Sei S irgendein kommutativer Ring. S ist Noethersch ⇔ Jedes Ideal von S ist endlich erzeugt. Beweis: “⇒”: Sei I ⊴ S. Sei 0 ≠ f_{1} ∈ I, I_{1} := (f_{1}), f_{2} ∈ I \ I_{1}, I_{2} := (f_{1}, f_{2}), . . .. Ist I nicht endlich erzeugt so definiert dies eine unendlich aufsteigende Kette von Idealen in S. “⇐”: Ist I_{1} ⊂ I_{2} ⊂ … aufsteigende Kette von Idealen in S. Definiere I := ⋃_{j=1}^{∞} I_{j}. Dann ist I ⊴ S. Da S Noethersch ist, gibt es f_{1}, …, f_{s} ∈ I mit I = (f_{1}, …, f_{s}). Dann gibt es aber ein N mit f_{1}, …, f_{s} ∈ I_{N}, also ist I = I_{N} = I_{N+1} = . . ..

8.3 Lemma:

Ist S ein kommutativer Noetherscher Ring, so ist S[x] Noethersch. Beweis: Sei J ⊴ S[x]. Zeigen, J ist endlich erzeugt. Für n ∈ ℕ sei I_{n} := {r ∈ S | rx^{n} + ∑_{j=0}^{n−1} a_{j}x^{j}(a_{j} ∈ S) ∈ J}. Klar: I ⊴ S, I_{n} ⊂ I_{n+1} ⊂ . . .. Da S Noethersch ist, gibt es ein N mit I_{N} = I_{N+1} = . . .. Außerdem ist I_{j} endlich erzeugt, also I_{j} := (r_{j1}, …, r_{jt_{j}}). Sei f_{ji} ∈ J mit f_{ji} = r_{ji}x^{j} + . . .. Dann ist J = (f_{ji} | 0 ≤ j ≤ N, 1 ≤ i ≤ t_{j}) =: J′. Denn: Klar ist J′ ⊆ J. Umgekehrt sei J_{n} := {f ∈ J | Grad(f) = n}. Per Induktion über n zeigen wir, dass J_{n} ⊂ J′. n = 0 klar, da I_{0} = (r_{01}, …, r_{0t_{0}}) = J_{0}. n ⇒ n + 1: f ∈ J_{n+1} ⇒ f = rx^{n+1} + ∑_{i=0}^{n} a_{i}x^{i}. Sei m := min(N, n + 1) und d := n + 1 − m. Dann ist r ∈ I_{m}, r = ∑_{j=1}^{t_{m}} a_{j}r_{m,j}. Sei g := ∑_{j=1}^{t_{m}} a_{j}f_{m,j} ∈ J′. Dann ist Grad(f − gx^{d}) ≤ n, also f − gx^{d} ∈ J′ nach IV. Da g ∈ J′ folgt also auch f ∈ J′. Aus (8.3) ergibt sich nun der Hilbertsche Basissatz durch Induktion über n.

8.4 Definition:

(a) 𝕄 := {x_{1}^{α_{1}} … x_{n}^{α_{n}} =: x^{α} | α_{1}, …, α_{n} ∈ ℕ_{0}} ist die Menge der Monome in R.

(b) Eine Monomordnung < ist eine Totalordnung auf 𝕄 mit 1 < x^{β} für alle x^{β} ∈ 𝕄, x^{β} ≠ 1. x^{α} < x^{β} ⇒ x^{α}x^{γ} < x^{β}x^{γ} für alle x^{γ} ∈ 𝕄.

8.5 Beispiel: (Monomordnungen)

x_{1} > x_{2} > … > x_{n}.

(a) Die lexikographische Ordnung “lex”: x^{α} < x^{β} ⇔ es gibt i ∈ {1, …, n} mit α_{i} < β_{i} und α_{j} = β_{j} für alle j < i.

(b) Die Grad-lexikographische Ordnung “deglex”: x^{α} < x^{β} ⇔ entweder ∑_{i=1}^{n} α_{i} < ∑_{i=1}^{n} β_{i} oder ∑_{i=1}^{n} α_{i} = ∑_{i=1}^{n} β_{i} und es gibt i ∈ {1, …, n} mit α_{i} < β_{i} und α_{j} = β_{j} für alle j < i.

(c) Die Grad-anti-lexikographische Ordnung “degrevlex”: x^{α} < x^{β} ⇔ entweder ∑_{i=1}^{n} α_{i} < ∑_{i=1}^{n} β_{i} oder ∑_{i=1}^{n} α_{i} = ∑_{i=1}^{n} β_{i} und es gibt i ∈ {1, …, n} mit α_{i} > β_{i} und α_{j} = β_{j} für alle j < i.

8.6 Bermerkung: Ist < eine Monomordnung, so gilt x^{α} | x^{β} ⇒ x^{α} ≤ x^{β}.

8.7 Satz: Jede Monomordnung ist eine Wohlordnung, d.h. für alle ∅ ≠ A ⊂ 𝕄 gibt es x^{α} ∈ A so dass x^{β} ≥ x^{α} für alle x^{β} ∈ A. Beweis: Angenommen nicht, dann sei x^{α_{1}} > x^{α_{2}} > … mit x^{α_{i}} ∈ A. Das definiert eine unendliche echt aufsteigende Kette von Idealen (x^{α_{1}}) ⊂ (x^{α_{1}}, x^{α_{2}}) ⊂ . . .. Es gilt x^{α_{i+1}} ∉ (x^{α_{1}}, …, x^{α_{i}}), da sonst x^{α_{i+1}} = ∑_{j=1}^{i} p_{j}x^{α_{j}} = ∑_{l=1}^{m} a_{l}x^{β_{l}} mit p_{j} ∈ R, a_{l} ∈ K. Da 𝕄 eine K-Basis von R ist, folgt durch Koeffizientenvergleich, dass m = 1, a_{1} = 1, β_{1} = α_{i+1} ist. Also teilt eines der x_{j}^{α} das x_{i+1}^{α} j ≤ i, d.h. mit 8.6 ist x^{α_{j}} ≤ x^{α_{i+1}} was ein Widerspruch ist.

8.8 Definition:

Sei < eine Monomordnung un f ∈ R. Schreibe f = a_{1}x^{α_{1}} + a_{2}x^{α_{2}} + … + a_{r}x^{α_{r}} mit a_{j} ∈ K \ {0}, x^{α_{1}} > x^{α_{2}} > … > x^{α_{r}}. lm(f) := x^{α_{1}} heißt das Leitmonom von f. lc(f) := a_{1} heißt der Leitkoeffizient von f. lt(f) := a_{1}x^{α_{1}} heißt das Leitterm von f. lm(0) := lc(0) := lt(0) := 0.

8.9 Definition: Seien f, g, h ∈ R, g ≠ 0. f reduziert zu h mod g in einem Schritt, f →^{g} h :⇔ lm(g) teilt einen Term X ≠ 0 von f und h = f − \frac{X}{lt(g)}g.

8.10 Definition: Seien f, h, f_{1}, …, f_{s} ∈ R, f_{i} ≠ 0, F := {f_{1}, …, f_{s}}.

(a) f reduziert zu h modulo F in Zeichen: f →^{F}_{+} h, falls es i_{1}, …, i_{t} ∈ {1, …, s} gibt und h_{1}, …, h_{t−1} ∈ R mit

f →^{f_{i_{1}}} h_{1} →^{f_{i_{2}}} h_{2} →^{f_{i_{3}}} … →^{f_{i_{t−1}}} h_{t−1} →^{f_{i_{t}}} h.

(b) f heißt reduziert modulo F, falls entweder r = 0 oder kein Monom von f ist durch ein lm(f_{i}) (1 ≤ i ≤ s) teilbar.

(c) Ist f →^{F}_{+} r und r reduziert modulo F, so heißt r ein Rest von f modulo F.

8.11 Algorithmus (Divisionsalgorithmus)

Eingabe: f, f_{1}, …, f_{s} ∈ R, f_{i} ≠ 0. Ausgabe: u_{1}, …, u_{s}, r ∈ R mit f = u_{1}f_{1} + … + u_{s}f_{s} + r, r reduziert modulo {f_{1}, …, f_{s}} und lm(f) = max_{i} lm(u_{i}f_{i}). Algorithmus u_{1} := 0; … u_{s} := 0; r := 0; h := f; while h ≠ 0 do

if (es gibt i mit lm(f_{i}) | lm(h)) then wähle minimales solches i u_{i} := u_{i} + lt(h)/lt(f_{i}); h := h − lt(h)/lt(f_{i}) · f_{i};

else

r := r + lt(h); h := h − lt(h); end if;

end while; Beispiel: (a) f = x, f_{1} = x^{2}, f_{2} = x^{2} − x. Dann ist f reduziert modulo {f_{1}, f_{2}} aber f ∈ (f_{1}, f_{2}) = (x).

(b) f := y^{2}x − x, f_{1} := yx − y, f_{2} := y^{2} − x mit deglex, y > x. Dann gilt f →^{f_{1}} y^{2} − x →^{f_{2}} 0 aber f →^{f_{2}} x^{2} − x was reduziert ist modulo {f_{1}, f_{2}}.

8.12 Definition: 0 ∉ G = {g_{1}, …, g_{t}} ⊂ I ⊴ R heißt Gröbnerbasis für I, falls für alle f ∈ I, f ≠ 0 ⇒ es gibt i ∈ {1, …, t} mit lm(g_{i}) | lm(f). Für S ⊂ R definiere Lt(S) := (lt(s) | s ∈ S) ⊴ R.

8.13 Satz: Sei 0 ∉ G = {g_{1}, …, g_{t}} ⊂ I ⊴ R. Äquivalent sind:

(i) G ist Gröbnerbasis für I.

(ii) f ∈ I ⇔ f →^{G}_{+} 0.

(iii) f ∈ I ⇔ f = ∑_{i=1}^{t} h_{i}g_{i} mit lm(f) = max_{i} lm(h_{i})lm(g_{i}). (iv) Lt(G) = Lt(I). Beweis: (i) ⇒ (ii): Sei f ∈ R. Alg. (8.11) liefert f →^{G}_{+} r mit r reduziert modulo G. Ist r = 0, so ist f ∈ I. Umgekehrt ist f ∈ I, so auch r ∈ I. Angenommen r ≠ 0, dann gibt es ein i mit lm(g_{i}) | lm(r), also ist r nicht reduziert modulo G. (ii) ⇒ (iii): Algorithmus 8.11 liefert eine solche Darstellung. (iii) ⇒ (iv): Sei f ∈ I. Dann ist f = ∑_{i=1}^{s} h_{i}g_{i} mit lm(f) = max_{i} lm(h_{i})lm(g_{i}) ∈ Lt(G). (iv) ⇒ (i): Sei f ∈ I. Dann ist lt(f) ∈ Lt(I) = Lt(G), d.h. es gibt h_{i} ∈ R mit lt(f) = ∑_{i=1}^{t} h_{i}lt(g_{i}). Die rechte Seite ist ein Term, auf der linken Seite kommen nur Terme vor, die durch ein lt(g_{i}) teilbar sind. Koeffizientenvergleich liefert lt(f) ist durch ein lt(g_{i}) teilbar. Also G ist Gröbnerbasis.

8.14 Folgerung: G Gröbnerbasis für I ⇒ (G) = I.

8.15 Lemma: Sei S ⊂ 𝕄, I = (S) ⊴ R, f ∈ R.

(a) f ∈ I ⇔ jedes Monom, das in f vorkommt ist durch ein s ∈ S teilbar.

(b) Es gibt eine endliche Teilmenge S_{0} ⊂ S mit I = (S_{0}). Beweis: (a) Ist f = ∑_{i=1}^{l} h_{i}X_{i} mit X_{i} ∈ S, h_{i} ∈ R so ist jeder Term von f durch eines der X_{i} teilbar.

(b) I hat endliches Erzeugendensystem nach dem Hilbertschen Basissatz, I = (f_{1}, …, f_{s}). Nach (a) ist jeder Term der f_{i} teilbar durch ein X_{j} ∈ S. Ist S_{0} die Menge dieser Terme X_{j} so ist (S_{0}) = I.

8.16 Folgerung: 0 ≠ I ⊴ R ⇒ I hat eine endliche Gröbnerbasis.

Beweis: Lt(I) hat endliches Erzeugendensystem S_{0} aus Monomen. Ist S_{0} = {lm(g_{1}), …, lm(g_{t})}, so ist {g_{1}, …, g_{t}} eine Gröbnerbasis für I.

8.17 Satz: G = {g_{1}, …, g_{t}} ⊂ R \ {0}. G ist Gröbnerbasis ⇔ für alle f ∈ R ist der Rest der Division von f durch G eindeutig. Beweis: ⇒: Seien r_{1}, r_{2} Reste von f modulo G. Dann ist r_{1} − r_{2} ∈ I reduziert, also r_{1} − r_{2} = 0 nach (8.11) (ii). ⇐: Zeigen (8.11) (ii). Sei also f ∈ I mit f →^{G}_{+} r, r reduziert modulo G. Wissen: r ist eindeutig. Müssen zeigen: r = 0. Dazu zeigen wir folgende \underline{Behauptung:} Sei 0 ≠ c ∈ K, X ∈ 𝕄, g ∈ R mit g →^{G}_{+} r, r reduziert. Dann gilt für

alle i ∈ {1, …, t} g − cXg_{i} →^{G}_{+} r.

Denn: Sei h := g−cXg_{i}. Dann kommt Xlm(g_{i}) nur in g oder nur in h oder in beiden vor, also gilt entweder g →^{g_{i}} h oder h →^{g_{i}} g oder es gibt g̃ mit g →^{g_{i}} g̃ und h →^{g_{i}} g̃. Da der Rest eindeutig ist folgt die Behauptung. Damit ergibt sich der Satz, denn da f ∈ I ist, ist f = ∑_{ν=1}^{t} c_{ν}X_{ν}g_{i_{ν}} mit X_{ν} ∈ 𝕄.

f →^{G}_{+} r ⇒ f − c_{1}X_{1}g_{i_{1}} →^{G}_{+} r ⇒ … f − ∑_{ν=1}^{t} c_{ν}X_{ν}g_{i_{ν}} →^{G}_{+} r d.h. r = 0.

8.18 Bemerkung: (a) Mit einer Gröbnerbasis G von I kann man in R/I rechnen, es gibt eindeutige Normalformen, die Reste. Z.B. bilden die Monome, die nicht durch ein lm(g_{i}) teilbar sind eine Basis von R/I.

(b) Gröbnerbasen haengen von der gewählten Monomordnung ab.

(c) Wir wollen nun Bedingung (8.13)(ii) abschwächen um daraus einen Algorithmus zur Berechnung von Gröbnerbasen herzuleiten:

8.19 Definition: Seien 0 ≠ f, g ∈ R, L := kgV(lm(f), lm(g)). Dann heißt

S(f, g) := \frac{L}{lt(f)}f − \frac{L}{lt(g)}g

das S-Polynom von f, g.

8.20 Beispiel: f := 2yx − y, g := 3y^{2} − x, R = ℚ[x, y] mit deglex, y > x. S(f, g) = 1/3x^{2} − 1/2y^{2}.

Ist h →^{f_{1}} h_{1} und h →^{f_{2}} h_{2} so ist h_{2} − h_{1} = S(f_{1}, f_{2}).

8.21 Hauptsatz: Sei G := {g_{1}, …, g_{t}} ⊂ R\{0}. G ist eine Gröbnerbasis ⇔ für alle i ≠ j

S(g_{i}, g_{j}) →^{G}_{+} 0.

8.22 Lemma: Sei {f_{1}, …, f_{s}} ⊂ R so dass lm(f_{i}) = X für alle i = 1, …, s. Ist f = ∑_{j=1}^{s} c_{j}f_{j} mit c_{j} ∈ K und lm(f) < X, so ist f eine K-Linearkombination der S(f_{i}, f_{j}). Beweis: Sei f_{i} = a_{i}X+ kleinere Terme. Dann ist f = ∑_{j=1}^{s} c_{j}f_{j} = ∑_{j=1}^{s}(a_{j}c_{j})X+ kleinere Terme. Also ∑_{j=1}^{s} a_{j}c_{j} = 0. Weiter ist S(f_{i}, f_{j}) = \frac{1}{a_{i}} f_{i} − \frac{1}{a_{j}} f_{j} und f = c_{1}a_{1}(\frac{1}{a_{1}} f_{1}− \frac{1}{a_{2}} f_{2})+(c_{1}a_{1}+c_{2}a_{2})(\frac{1}{a_{2}} f_{2}− \frac{1}{a_{3}} f_{3})+…++(c_{1}a_{1}+…+c_{s−1}a_{s−1})(\frac{1}{a_{s−1}} f_{s−1}− \frac{1}{a_{s}} f_{s}) + (c_{1}a_{1} + … + c_{s}a_{s})\frac{1}{a_{s}} f_{s}. Beweis von (8.21): “⇒” Klar, da S(g_{i}, g_{j}) ∈ I. “⇐” Zeigen (8.14) (iii): Sei f ∈ I und f = ∑_{i=1}^{t} h_{i}g_{i} mit minimalem X = max_{i}(lm(h_{i})lm(g_{i})). Zu zeigen: X = lm(f). Angenommen X > lm(f). Dann sei S := {i | lm(h_{i}g_{i}) = X}. Für i ∈ S schreibe h_{i} = c_{i}X_{i}+ kleinere Terme mit c_{i} ∈ K. Sei g := ∑_{i∈S} c_{i}X_{i}g_{i}. Dann ist lm(X_{i}g_{i}) = X, lm(g) < X. Aus Lemma (8.21) folgt dann, dass g = ∑_{i,j} d_{ij}S(X_{i}g_{i}, X_{j}g_{j}), wo S(X_{i}g_{i}, X_{j}g_{j}) = \frac{X}{lt(X_{i}g_{i})}X_{i}g_{i} − \frac{X}{lt(X_{j}g_{j})}X_{j}g_{j} = \frac{X}{lt(g_{i})}g_{i} − \frac{X}{lt(g_{j})}g_{j} = \frac{X}{X_{ij}} S(g_{i}, g_{j}), wo X_{ij} = kgV(lm(g_{i}), lm(g_{j})). Nach Voraussetzung reduziert

S(g_{i}, g_{j}) →^{G}_{+} 0, also auch S(X_{i}g_{i}, X_{j}g_{j}) →^{G}_{+} 0, d.h. S(X_{i}g_{i}, X_{j}g_{j}) = ∑_{ν=1}^{t} h_{ijν}g_{ν} mit

max_{ν}(lm(h_{ijν})lm(g_{ν})) = lm(S(X_{i}g_{i}, X_{j}g_{j})) < X. Also ist auch g = ∑_{i=1}^{t} h̃_{i}g_{i} mit h̃_{i} ∈ R, max_{i}lm(h̃_{i}g_{i}) = lm(g) < X. Definiert man h′_{i} := h_{i} − c_{i}X_{i} + h̃_{i}, so ist f = ∑_{i=1}^{t} h′_{i}g_{i} mit kleinerem max_{i}(lm(h′_{i}g_{i})), was ein Widerspruch ist.

8.23 Folgerung: G = {g_{1}, …, g_{t}} ⊂ R\{0}. G ist Gröbnerbasis ⇔ S(g_{i}, g_{j}) = ∑_{ν=1}^{t} h_{ijν}g_{ν} mit max_{ν}(lm(h_{ijν})lm(g_{ν})) = lm(S(g_{i}, g_{j})) < X für alle 1 ≤ i < j ≤ t.

8.24 Beispiel: f_{1} = xy−x, f_{2} = x^{2}−y, R = ℚ[x, y] mit deglex, x < y. S(f_{1}, f_{2}) →^{f_{2}} y^{2}−y =: f_{3}. Also ist {f_{1}, f_{2}} noch keine Gröbnerbasis. Indem man die 3 S-Polynome reduziert findet man, dass {f_{1}, f_{2}, f_{3}} eine Gröbnerbasis ist.

8.25 Algorithmus: (Buchberger Algorithmus)

Eingabe: F = {f_{1}, …, f_{s}} ⊂ R \ {0}. Ausgabe: G = {g_{1}, …, g_{t}} Gröbnerbasis für (F). Algorithmus: G := F; G := {{f_{i}, f_{j}} | f_{i} ≠ f_{j} ∈ G}; while G ≠ ∅ do

wähle {f, g} ∈ G;

G := G \ {{f, g}};
S(f, g) →^{G}_{+} h; (mit h reduziert modulo G)
if (h ≠ 0) then
G := G ∪ {{f, h} | f ∈ G};
G := G ∪ {h};

end if; end while;

8.26 Satz: Algorithmus (8.25) terminiert.

Beweis: Im Schritt G := G ∪ {h} wird G vergrößert durch ein h, mit lt(h) ∉ Lt(G). Also konstrieren wir eine aufsteigende Kette von Idealen Lt(G_{1}) ⊂ Lt(G_{2}) ⊂ Lt(G_{3}) ⊂ …, die nach dem Hilbertschen Basissatz stationär wird. Also wird dieser Schritt nur endlich oft durchgeführt, d.h. der Algorithmus terminiert.

8.27 Definition: Sei G = {g_{1}, …, g_{t}} eine Gröbnerbasis. G heißt minimal, falls für alle i lc(g_{i}) = 1 und für i ≠ j lm(g_{i}) | l̸m(g_{j}).

8.28 Bemerkung: Sei G = {g_{1}, …, g_{t}} eine Gröbnerbasis für I und M := {g_{i} ∈ G | es gibt i ≠ j mit lm(g_{j}) | lm(g_{i})}. Dann ist G \ M eine minimale Gröbnerbasis für I. Beweis: Lt(G) = Lt(G \ M).

8.29 Lemma: Seien F = {f_{1}, …, f_{s}} und G = {g_{1}, …, g_{t}} zwei minimale Gröbnerbasen für I (bzgl. derselben Monomordnung). Dann ist s = t und nach eventuellem Umordnen lt(f_{i}) = lt(g_{i}) für alle i. Beweis: f_{1} ∈ I, G Gröbnerbasis, also existiert ein i mit lt(g_{i}) | lt(f_{1}). Sei Œi = 1. g_{1} ∈ I, F Gröbnerbasis, also existiert ein j mit lt(f_{j}) | lt(g_{1}) | lt(f_{1}). Aus der Minimalität von F folgt j = 1 und lt(g_{1}) = lt(f_{1}). ...

8.30 Definition: Sei G = {g_{1}, …, g_{t}} eine Gröbnerbasis. G heißt reduziert, falls g_{i} reduziert ist modulo G \ {g_{i}} und lc(g_{i}) = 1 für alle i. Klar: Reduzierte Gröbnerbasen sind minimal.

8.31 Algorithmus:

Eingabe: G = {g_{1}, …, g_{t}} minimale Gröbnerbasis. Ausgabe: H = {h_{1}, …, h_{t}} reduzierte Gröbnerbasis. Algorithmus:

g_{1} →^{H_{1}}_{+} h_{1}, h_{1} reduziert modulo H_{1} := {g_{2}, …, g_{t}}

g_{2} →^{H_{2}}_{+} h_{2}, h_{2} reduziert modulo H_{2} := {h_{1}, g_{3}, …, g_{t}}

⋮

g_{t} →^{H_{t}}_{+} h_{t}, h_{t} reduziert modulo H_{t} := {h_{1}, …, h_{t−1}}

Bemerkung: H = {h_{1}, …, h_{t}} ist reduzierte Gröbenerbasis von (G). Beweis: lt(h_{j}) = lt(g_{j}) für alle j. Also ist h_{j} reduziert modulo H \ {h_{j}}, da h_{j} reduziert modulo H_{j} und beide Mengen die gleiche lt haben.

8.32 Satz (Buchberger)

Sei 0 ≠ I ⊴ R und < eine Monomordnung. Dann gibt es genau eine reduzierte Gröbnerbasis für I. Beweis: Existenz ist klar. Zur Eindeutigkeit: Seien G = {g_{1}, …, g_{t}} und H = {h_{1}, …, h_{s}} zwei reduzierte Gröbnerbasen für I. Dann gilt nach (8.29) t = s und lt(g_{i}) = lt(h_{i}) (nach Umordnen). Angenommen g_{i} ≠ h_{i}. Dann ist g_{i} − h_{i} ∈ I. Also gibt es ein j mit lt(h_{j}) = lt(g_{j}) | lm(g_{i} − h_{i}) < lm(h_{i}). Also i ≠ j und lm(h_{j}) = lm(g_{j}) teilt einen Term vom g_{i} oder h_{i}, was ein Widerspruch dazu ist, dass G und H reduziert sind.

Abschnitt 9: Anwendungen.

Situation: Wie in Abschnitt 8, insbesondere K Körper (K = ℚ, ℝ, 𝔽_{p}, …), R := K[x_{1}, …, x_{n}], I ⊴ R. Weiter sei G := {g_{1}, …, g_{s}} eine Gröbnerbasis für I.

9.1 Rechnen in R/I:

(i) Die Reste modulo G sind nach Satz (8.17) eindeutige Vertreter der Restklassen modulo I und können mit Algorithmus (8.11) berechnet werden. Also kann man Addieren, Multiplizieren und entscheiden, ob f + I = 0. (ii) f + I invertierbar in R/I ⇔ die reduzierte Gröbnerbasis für (g_{1}, …, g_{s}, f) ist {1}. Algorithmus (8.25) kann so ergänzt werden, dass man sich die Transformation F → G merkt. Schreibt man dann 1 = ∑_{j=1}^{s} u_{j}g_{j} + uf, so ist u + I = (f + I)^{−1}. (iii) K-Basis von R/I ⟶ Monome die durch kein lm(g_{j}) teilbar sind. Also z.B. dim_{K}(R/I) < ∞ ⇔ für alle i ∈ {1, …, n} gibt es ein j ∈ {1, …, s} und ν ∈ ℕ_{0} mit lm(g_{j}) = x_{i}^{ν}. In diesem Fall kann man V (I) mit Hilfe von Gröbnerbasen explizit bestimmen:

9.2 Beispiel: Das 3 Farben Problem: Man will einen Graphen Γ so mit 3 Farben färben, dass je 2 benachbarte Ecken nie die gleiche Farbe bekommen. (Problem: Landkarte mit 3 Farben färben). Ist Γ 3-färbbar und wenn ja, bestimme eine (oder alle) Färbung.

[figure: 8; 3; 2; 5; 1; 7; 6; 4]

Die 3 Farben werden durch die 3 Nullstellen von X^{3} − 1 dargestellt. Variablen: x_{1}, …, x_{n}, für jede der n-Ecken in Γ. Gleichungen: x_{i}^{3} − 1 = 0 (i = 1, …, n) und falls (i, j) eine Kante von Γ ist, so soll x_{i} ≠ x_{j} sein, also x_{i}^{2} + x_{i}x_{j} + x_{j}^{2} = 0. Also ist I := (x_{i}^{3} − 1, x_{i}^{2} + x_{i}x_{j} + x_{j}^{2} | 1 ≤ i ≤ n, (i, j) Kante in Γ). Dann bestimmt man eine Gröbnerbasis G für I bezüglich lex mit x_{1} > x_{2} > … > x_{n}. In unserem Beispiel ist G := {x_{1} − x_{7}, x_{2} + x_{7} + x_{8}, x_{3} − x_{7}, x_{4} − x_{8}, x_{5} + x_{7} + x_{8}, x_{6} − x_{8}, x_{7}^{2} + x_{7}x_{8} + x_{8}^{2}, x_{8}^{3} − 1}. Also überblickt man leicht alle Färbungen von Γ: Farbe 1: 8, 6, 4, Farbe 2: 7, 1, 3, Farbe 3: 2, 5. Bis auf Permutation der Farben hat man genaus eine Möglichkeit.

9.3 Definition: I heißt 0-dimensional, falls dim_{K}(R/I) < ∞.

Für 0-dimensionale Ideale kann man mit Hilfe von Gröbnerbasen die Lösungsmenge V (I) ausrechnen:

9.4 Satz: Sei R ≠ I ⊴ R ein 0-dimensionales Ideal und G = {g_{1}, …, g_{s}} die reduzierte Gröbnerbasis für I bzgl. lex mit x_{1} < … < x_{n}. Dann kann G so umgeordnet werden, dass g_{j} ein Polynom in den Variablen x_{1}, …, x_{j} ist (j = 1, …, n). Beweis: (9,1) (iii) sagt, dass für alle l ein j existiert mit x_{l}^{ν} = lm(g_{j}) für ein geeignetes ν. Wegen lex ist g_{j} ∈ K[x_{1}, …, x_{l}] \ K[x_{1}, …, x_{l−1}]. Bemerkung: Mit G kann man V (I) bestimmen, sobald man Nullstellen von Polynomen in einer Variable berechnen kann. Man berechnet alle Nullstellen α von g_{1} (Polynom in x_{1}), setzt diese in g_{2}, …, g_{n} ein, berechnet für alle α die Nullstellen von g_{2}(α, x_{2}), setzt wieder ein, usw. Am Ende muss man noch testen, welche der endlich vielen Lösungen g_{n+1}, …, g_{s} erfüllen. Wir kommen nun zur Variablenelimination.

9.5 Definition: Eine Eliminationsordnung für die Variablen x_{i} ist eine Monomordnung <= E(<_{x}, <_{y}) auf R := K[x_{1}, …, x_{n}, y_{1}, …, y_{m}] die aus zwei Monomordnungen <_{x} bzw. <_{y} auf K[x_{1}, …, x_{n}], bzw. K[y_{1}, …, y_{m}] zusammengesetzt ist. Sind die X_{i} Monome in den x_{j} und Y_{i} Monome in den y_{j} (i = 1, 2), so definiert man

X_{1}Y_{1} < X_{2}Y_{2} ⇔ X_{1} <_{x} X_{2} oder X_{1} = X_{2} und Y_{1} <_{y} Y_{2}.

Beispiel: lex = E(lex,lex) (aber lex ist sehr schlecht bei Rechnungen).

9.6 Satz: Sei 0 ≠ I ⊴ K[x_{1}, …, x_{n}, y_{1}, …, y_{m}] und < eine Eliminationsordnung für die x_{i}. Ist G eine Gröbnerbasis für I, so ist G̃ := G ∩ K[y_{1}, …, y_{m}] eine Gröbnerbasis für Ĩ:= I ∩ K[y_{1}, …, y_{m}]. Beweis: Sei f ∈ Ĩ. Dann ist f ∈ I. Da G eine Gröbnerbasis für I ist, gibt es ein g ∈ G mit lm(g) | lm(f).‘ Da lm(f) nur y_{j} enthält, kommt also auch in lm(g) kein x_{i} vor und damit g ∈ K[y_{1}, …, y_{m}]. Also ist g ∈ G̃ und damit G̃ Gröbnerbasis für Ĩ.

9.7 Bemerkung: Sind I, J ⊴ K[x_{1}, …, x_{n}] und y eine neue Variable, so ist I ∩ J = (yI, (1 − y)J) ∩ K[x_{1}, …, x_{n}]. Beweis: Sei Ĩ:= (yI, (1 − y)J) ∩ K[x_{1}, …, x_{n}]. Dann gilt für f ∈ I ∩ J, dass f = yf + (1 − y)f ∈ Ĩ.

Umgekehrt sei f ∈ Ĩ. Dann ist f ein Polynom in den x_{1}, …, x_{n}, also konstant in y. Schreibt man f als Summe der Erzeuger und setzt in dieser Darstellung y = 1, so findet man f ∈ I, bei y = 0, f ∈ J. Also ist f ∈ I ∩ J.

9.8 Beispiel: Polynomringe sind faktorielle Ringe, also ist ggT, kgV wohldefiniert. Gröbnerbasen verallgemeinern den Euklidischen Algorithmus insofern, dass man mit Bemerkung (9.7) ggT und kgV von Polynomen in mehreren Variablen berechnen kann:

(f) ∩ (g) = (kgV(f, g)), ggT(f, g) = fg/kgV(f, g).

Abschnitt 10: Involutive Basen.

Situation: Wie in Abschnitt 8, insbesondere K Körper (K = ℚ, ℝ, 𝔽_{p}, …), R := K[x_{1}, …, x_{n}], I ⊴ R. Ein Problem beim Berechnen von und Rechnen mit Gröbnerbasen ist, dass zwar die Normalform eines Elementes eindeutig ist, nicht aber der Reduktionsweg selbst. Dabei kann man weite Umwege gehen. Das macht Gröbnerbasisberechnungen und auch das spätere Berechnen von Normalformen langsam. In diesem Abschnitt möchte ich eine Idee vorstellen, die auf Janet (1920) zurückgeht, also wesentlich älter ist als der Buchberger Algorithmus, um bessere Gröbnerbasen zu definieren. Die Idee hierbei ist, nicht jede Division in Algorithmus (8.11) zuzulassen, sondern nur sogenannte Janet-Divisionen, die von dem aktuellen Idealerzeugensystem U abhängen. Das führt dazu, dass jedes Monom höchstens einen Janet-Teiler in U hat. Janet hat seine Ideen zum Lösen von Differentialgleichungssystemen benutzt. Man kann diese Ideen axiomatisieren und so verschiedene zulässige Divisionen betrachten. Wir wollen hier nur den wichtigsten Spezialfall der Janet-Division betrachten, die zu (i.a. nicht reduzierten) Gröbnerbasen führt.

10.1 Definition: (Janet 1920) Sei U ⊂ 𝕄 endlich und [d_{1}, …, d_{i}] := {u ∈ U | Grad_{x_{j}} = d_{j}, j = 1, …, i}, [] := U.

(a) Eine Variable x_{j} heißt multiplikativ für u ∈ U x_{j} ∈ M(u, U) :⇔ Grad_{x_{j}}(u) = max{Grad_{x_{j}}(v) | v ∈ [Grad_{x_{1}}(u), …, Grad_{x_{j−1}}(u)]}. Die Menge der nichtmultiplikativen Variablen ist NM(u, U) := {x_{1}, …, x_{n}} \ M(u, U).

(b) Sei m ∈ 𝕄. Dann ist u ∈ U ein Janet-Teiler von um: u |_{U} um, genau dann, wenn alle in m vorkommenden Variablen in M(u, U) sind.

10.2 Satz: Die Janet Division erfüllt die folgenden Bedingungen (u, u_{1} ∈ U ⊂ 𝕄, v, w ∈ 𝕄):

(i) u |_{U} w ⇒ u | w. (ii) u |_{U} u für alle u ∈ U. (iii) u |_{U} (uw) und u |_{U} (uv) ⇔ u |_{U} (uvw). (iv) u |_{U} w und u_{1} |_{U} w ⇒ u = u_{1}.

(v) V ⊂ U, u ∈ V. Dann gilt u |_{U} w ⇒ u |_{V} w Beweis: (i),(ii),(iii) und (v) folgen direkt aus der Definition. Zu (iv): Seien u ≠ u_{1} ∈ U und k maximal mit d_{i} := Grad_{x_{i}}(u) = Grad_{x_{i}}(u_{1}) für alle 1 ≤ i < k. Also u, u_{1} ∈ [d_{1}, …, d_{k−1}]. ŒGrad_{x_{k}}(u) > Grad_{x_{k}}(u_{1}) (also x_{k} nicht multiplikativ für u_{1}). Schreibe w = mu = m_{1}u_{1}. Da u_{1} |_{U} m_{1}u_{1}, kommt x_{k} in m_{1} nicht vor. Also ist Grad_{x_{k}}(w) = Grad_{x_{k}}(u_{1}) < Grad_{x_{k}}(u), was ein Widerspruch ist.

10.3 Folgerung: Jedes w ∈ 𝕄 hat höchstens einen Janet Teiler in U.

10.4 Definition: U ⊂ 𝕄 heißt involutiv (vollständig), :⇔ für alle u ∈ U, für alle w ∈ 𝕄

gibt es ein v ∈ U mit

v |_{U} uw.

10.5 Lemma: w = x_{j} Variable in (10.4). Seien u, v ∈ U mit v |_{U} ux_{j}. Dann ist v ≥ u bzgl. lex mit x_{1} > … > x_{n}. Beweis: Ist x_{j} ∈ M(u, U), dann gilt u |_{U} ux_{j}, also (10.3) u = v. Ist x_{j} ∈ NM(u, U), so sei d_{i} := Grad_{x_{i}}(u), i = 1, …, n. Sei i minimal mit Grad_{x_{i}}(v) ≠ d_{i}. Angenommen Grad_{x_{i}}(v) < d_{i}. Dann gilt wegen v |_{U} ux_{j}, dass x_{i} ∈ M(v, U). Da u, v ∈ [d_{1}, …, d_{i−1}], folgt Grad_{x_{i}}(v) ≥ Grad_{x_{i}}(u) was ein Widerspruch ist.

10.6 Lemma: U ⊂ 𝕄 ist involutiv ⇔ für alle u ∈ U, für alle x_{j} ∉ M(u, U) gibt es ein v ∈ U mit v |_{U} ux_{j}. Beweis: ⇒: Klar. ⇐: Sei w ∈ 𝕄. Suchen v ∈ U mit v |_{U} uw. Falls u |_{U} wu, so sind wir fertig. Sonst gibt es x_{j_{1}} ∈ NM(u, U) mit x_{j_{1}} | w. Nach Voraussetzung existiert ein v_{1} ∈ U mit v_{1} |_{U} ux_{j_{1}}. Falls v_{1} |_{U} uw, so sind wir fertig, sonst gibt es x_{j_{2}} ∈ NM(v_{1}, U) mit x_{j_{2}} | (uw)/v_{1}. Nach Voraussetzung existiert ein v_{2} ∈ U mit v_{2} |_{U} v_{1}x_{j_{2}}. Falls v_{2} |_{U} uw, so sind wir fertig, sonst . . .. So konstruieren wir eine Folge u = v_{0}, v_{1}, v_{2}, … von Monomen mit v_{i} | uw und v_{i+1} > v_{i} bzgl. lex (nach (10.5)). Also gibt es nur endlich viele v_{i}, d.h. eines der v_{j} Janet-teilt uw.

10.7 Satz: Für alle U ⊂ 𝕄 endlich, gibt es Ũ ⊂ 𝕄 endlich, mit U ⊂ Ũ, Ũ ist involutiv und (U) = (Ũ). Ũ kann mit folgendem Algorithmus konstruiert werden. Eingabe: U ⊂ 𝕄 endlich. Ausgabe: Ũ ⊇ U endlich, involutiv, (U) = (Ũ). Algorithmus: Ũ := U; while (es gibt ein u ∈ Ũ, x ∈ NM(u, Ũ) so dass u · x keine Janet-Teiler in Ũ hat) do Ũ := Ũ ∪ {ux}; end while; Beweis: Wir zeigen, dass der angegebene Algorithmus terminiert mit einer endlichen involutiven Menge Ũ. Klar Ũ ist am Ende involutiv. endlicher Algorithmus: Sei h_{j} := max_{u∈U} Grad_{x_{j}}(u). Dann ist h_{j} = max_{u∈Ũ} Grad_{x_{j}}(u), denn falls x_{j} ∈ NM(u, Ũ), so ist Grad_{x_{j}}(u) < h_{j} also auch Grad_{x_{j}}(x_{j}u) ≤ h_{j}. Wir kommen übertragen jetzt alle Begriffe für Polynome.

10.8 Definition:

Sei F ⊂ K[x_{1}, …, x_{n}] endlich und > eine feste Monomordnung kompatibel mit x_{1} > x_{2} > … > x_{n}.

(a) f ∈ F, so sei M(f, F) := M(lm(f), lm(F)) und NM(f, F) := NM(lm(f), lm(F)) die Menge der multiplikativen bzw. nichtmultiplikativen Variablen.

(b) h ∈ K[x_{1}, …, x_{n}]. Wir sagen, dass h in einem Schritt modulo (f, F) zu g Janetreduziert und schreiben

h \begin{matrix}f \\ → \\ F \end{matrix} g

falls h einen Term am hat (a ∈ K \ {0}, m ∈ 𝕄) mit lm(f) |_{lm(F)} m und g = h − \frac{am}{lt(f)}f.

(c) Analog definieren wir

h \begin{matrix}F \\ →_{+} \\ F \end{matrix} g

falls h mit einer Folge von Janet-Reduktionen modulo F zu g reduziert.

(d) h heißt Janet-reduziert modulo F, falls kein Term von h Janet-teilbar durch ein

f ∈ F. Gilt h \begin{matrix}F \\ →_{+} \\ F \end{matrix} g und ist g Janet-reduziert modulo F, so heißt g ein Janet-Rest

oder auch eine Janet-Normalform von h modulo F.

(e) F heißt Janet-autoreduziert, falls jedes f ∈ F Janet-reduziert modulo F \ {f} ist.

(f) F heißt Janet-Basis oder involutive Basis für (F), falls F Janet-autoreduziert ist und lm(F) involutiv.

10.9 Satz: Sei F ⊂ R = K[x_{1}, …, x_{n}] endlich und < eine Monomordung auf R mit x_{1} < … < x_{n}.

(a) Ist F Janet-autoreduziert, so hat jedes h ∈ R eine eindeutige Janet-Normalform modulo F, sogar der Reduktionsweg ist eindeutig.

(b) Ist F eine Janet-Basis, so ist F eine (i.a. nicht reduzierte) Gröbnerbasis und die Janet-Normalform von h ∈ R ist gleich der (Gröbner)-Normalform von h modulo F.

10.10 Beispiele