Prim ist Polynomial

M.Z.^{∗} 20.3.12003

In diesem Vortrag gebe ich den Beweis von Satz 1 (Agrawal, Kayal, Saxena, 2002). Es gibt einen Algorithmus, der in c log^{6} n Schritten entscheidet ob n prim ist.

Die besten Ergebnisse waren bisher

• Adelman, Pomerance, Rumely 1983: Ein Algorithmus mit (log n)^{log log log n} Schritten.

• Adelman, Huang 1992: Ein polynomialer, probalistischer Algorithmus (liefert mit Wahrscheinlichkeit 0.5 ein Resultat).

Man zeigt leicht, daß n genau dann prim ist, wenn für alle a (oder für ein a, das prim zu n ist),

(X − a)^{n} ≡ X^{n} − a mod n.

Das folgende Lemma gibt eine Version, die der Berechnung zugänglich ist. Lemma 2. Sei n eine positive natürliche Zahl. Weiter seien Primzahlen r, q gegeben und eine Zahl s, sodaß

q | r − 1  n^{\frac{r−1}{q}} ≢ 1 mod r  \binom{q + s − 1}{s} ≥ n^{2\sqrt{r}}  (1)

Wenn die folgenden Bedingungen erfüllt sind:

r |̸ n  (2)

und für alle a ∈ [0, s)

(a, n) = 1  (3)
(X − a)^{n} ≡ X^{n} − a mod (X^{r} − 1, n)  (4)

Dann ist n eine Primpotenz.

Der Algorithmus funktioniert nun folgendermaßen:

• Suche r, q, s, die (1) erfüllen. Wir werden weiter unten sehen, daß man r, q, s immer von der Größenordnung log^{6} n finden kann • Überprüfe (2),(3) und (4). Wenn eine der Bedingungen nicht zutrifft, ist

∗Vortrag in Freiburg 28.11.02 und Bogota 20.3.2003

n keine Primzahl.

• Wir wissen jetzt, daß n ein Primpotenz ist. n ist genau dann eine Primzahl, wenn für alle i ∈ [2, log n] n keine i–te Potenz ist.

Beweis von Lemma 2. Wenn n^{\frac{r−1}{q}} ≢ 1 mod r, gibt es einen Primteiler p von

n, für den p^{\frac{r−1}{q}} ≢ 1 mod r. Weil r |̸ n, ist p ≠ r und daher p^{r−1} ≡ 1 mod r. Daraus folgt, daß

q | ord_{r}(p),  (5)

wobei die ord_{r}(p), die Ordnung von p modulo r, die kleinste Zahl k > 0 ist, für die p^{k} ≡ 1 mod r.

Betrachte nun die Menge aller Zahlen t = p^{i}n^{j}, für i, j ∈ [0, \sqrt{r}]. Weil es mehr als r viele Indexpaare gibt, gibt es zwei Paare (i_{1}, j_{1}) ≠ (i_{2}, j_{2}) für die t_{1} ≡ t_{2} mod r.

Die folgende Behauptung impliziert sofort, das n eine Potenz von p ist.

Behauptung: t_{1} = t_{2}.

Beweis: Aus (4) und dem kleinen Fermat folgt

(X − a)^{t} ≡ X^{t} − a mod (X^{r} − 1, p)

für alle a ∈ [0, s) und alle t der Form p^{i}n^{j}. Auf der anderen Seite impliziert t_{1} ≡ t_{2} mod r, daß X^{t_{1}} ≡ X^{t_{2}} mod (X^{r} − 1). Es ergibt sich

(X − a)^{t_{1}} ≡ (X − a)^{t_{2}} mod (X^{r} − 1, p)  (6)

für alle a ∈ [0, s).

Sei ζ eine primitive r-te Einheitswurzel über 𝔽_{p} und 𝔽_{p^{k}} = F_{p}(ζ). k is minimal mit r | (p^{k} − 1). Also ist k = ord_{r}(p) und wir haben

q | k.  (7)

Aus (6) folgt, daß (ζ −a)^{t_{1}} = (ζ −a)^{t_{2}} für alle a ∈ [0, s). Sei G die multiplikative Gruppe, die von allen (ζ − a) erzeugt wird. Dann ist g^{t_{1}} = g^{t_{2}} für alle g ∈ G. Weil G zyklisch ist, folgt, daß

t_{1} ≡ t_{2} mod |G|.  (8)

Aus (7) folgt, daß alle Elemente

∏_{a∈[0,s)}(ζ − a)^{e_{a}}

mit ∑ e_{a} < q verschieden sind. G hat also mindestens die Ordnung

\binom{q + s − 1}{s} ≥ n^{2\sqrt{r}} ≥ (pn)^{\sqrt{2}} > max(t1, t2).

Aus (8) folgt jetzt t_{1} = t_{2}.

Lemma 3. Es gibt eine Konstante c_{0}, sodaß es für alle n eine Primzahl r ≤

c_{0} log^{6} n und einen Primteiler q von r − 1 gibt mit n^{\frac{r−1}{q}} ≢ 1 mod r und q ≥ 4\sqrt{r} log n.

Beweis. Wir nennen eine Primzahl r gut, wenn r − 1 einen Primteiler hat, der

mindestens so groß wie r^{\frac{2}{3}} . Aus einem Satz von Foury (1985) folgt^{1}, daß es ein ϵ > 0 gibt, sodaß unter jedem x mindestens ϵ\frac{x}{log x} viele gute Primzahlen liegen. Weil es asymptotisch \frac{x}{log x} viele Primzahlen unterhalb von x gibt, schließt man daraus leicht auf die Existenz^{2} eines c_{0}, sodaß für alle x im Intervall [4^{6}x, c_{0}x] mindestens \frac{x}{log x} gute Primzahlen liegen. Wir haben damit:

Das Intervall I = [4^{6}, c_{0} log^{6} n] enthält mindestens \frac{log^{6}}{log log^{6} x} viele gute Primzahlen.

Es ist schon klar, daß es für jedes gute r aus I r − 1 einen Primteiler q hat mit q ≥ 4\sqrt{r} log n. Aus q > r^{\frac{2}{3}} folgt nämlich

q > \sqrt{r} r^{\frac{1}{6}} ≥ \sqrt{r} 4 log n.

Wir müssen nur noch zeigen, daß I immmer gute r enthält, die ein q mit n^{\frac{r−1}{q}} ≢ 1 mod r haben: Für alle guten r unterhalb von c_{0} log^{6} n und alle q ≥ r^{\frac{2}{3}} ist

\frac{r − 1}{q} ≤ r^{\frac{1}{3}} ≤ c0^{\frac{1}{3}} log^{2} n =: y.

Es genügt also ein gutes r zu finden, das keine der Zahlen

n − 1, n^{2} − 1, …, n^{y} − 1

teilt. Jeder dieser Zahlen hat höchstens log(n^{y}) viele Primteiler. r muß also verschieden gewählt werden von höchsten

x log(n^{y}) = y^{2} log n = c0^{\frac{1}{3}} log^{5} n =: z

vielen Primzahlen. z ist aber für große n kleiner als \frac{log^{6}}{log log^{6} x}.

Folgerung 4. Es gibt für alle n Primzahlen r, q ≤ c_{0} log^{6} n und eine Zahl s ≤ 2\sqrt{c_{0}} log^{4} n, für die (1) gilt.

Beweis. Wähle r und q wie in Lemma 3 und setze s = 2\sqrt{r} log n. Dann gilt

\binom{q + s − 1}{s} ≥ \frac{q^{s}}{s^{s}} ≥ 2^{s} = n^{2\sqrt{r}}.

Eine Primzahl r heißt Germaine–Sophie , wenn \frac{r−1}{2} prim ist. Eine Vermutung von Hardy–Littlewood besagt, daß es ein D > 0 gibt , sodaß es unterhalb eines jeden x asymptotisch \frac{Dx}{log^{2} x} viele Germaine–Sophie–Primzahlen gibt.

1Es gibt unterhalb von x sogar mindestens ϵ \frac{x}{log x} viele Primzahlen r, für die r − 1 einen Primteiler q hat mit q > x^{\frac{2}{3}} .

2c_{1} = \frac{4^{6}}{ϵ}

Bemerkung 5. Wenn die Hardy–Littlewood–Vermutung gilt, gibt es ein c_{1}, sodaß es für alle n Primzahlen r, q ≤ c_{1} log^{2} n und eine Zahl s ≤ 2\sqrt{c_{1}} log^{2} n gibt, für die (1) gilt.

Beweis. Wähle c_{1} so groß, daß es im Intervall J = [64 log^{2} n, c_{1} log^{2} n] immer mehr als 2 log n viele Germaine–Sophie–Primzahlen gibt. (Das ist möglich, weil \frac{log^{2} n}{log^{2} log^{2} n} schneller wächst als log n.) Wir finden dann in J eine Germaine– Sophie–Primzahl r, die n^{2} − 1 nicht teilt, weil n^{2} − 1 höchstens 2 log n–viele Primteiler hat. Damit ist also klar, daß für q = \frac{r−1}{2} n^{\frac{r−1}{2}} ≢ 1 mod r. Wir haben wieder (mit etwas ungenauer Rechnung)

q = \frac{r}{2} = \sqrt{r} \frac{\sqrt{r}}{2} ≥ \sqrt{r} \frac{\sqrt{64 log^{2} n}}{2} = 4\sqrt{r} log n.

Wir setzen s = 2\sqrt{r} log n und sind fertig.

(Erratum: Es ist leider nicht klar, welche Basis log hat.)