2.4.2 (p-1)-Faktorisierung von Pollard

Der (p-1)-Faktorisierungsalgorithmus wurde entworfen um effizient Primfaktoren p einer nichtprimen Zahl n, für welche p-1 in Bezug zu einer relativ kleinen Schranke B glatt ist, zu finden. Dazu folgende

Definition:
Sei 0 > B ∈ Z. Ein n ∈ Z heißt B-glatt oder glatt bezüglich B, falls alle Primfaktoren ≤ B sind.

Die Idee zum (p-1)-Algorithmus ist folgende:
Sei B eine Glattheitsschranke. Sei Q das kleinste gemeinsame Vielfache aller Potenzen von Primzahlen ≤ B, welche ≤ n sind. Falls g^l ≤ n, so ist l⋅ln q ≤ ln n und damit l ≤ ⌊ ln n / ln q ⌋. Daher ist Q = ∏_{q ≤ b} q^{⌊ ln n / ln q ⌋} wobei das Produkt über alle verschiedenen q ≤ B läuft. Falls p ein Primfaktor von n ist, so dass p-1 B-glatt ist, dann gilt p-1|Q und folglich für jedes a, für das gilt ggT(a, p) = 1, impliziert der kleine Fermatsche Satz a^Q ≡ 1 (mod p). Also gilt: falls d = ggT(a^Q - 1, n ), dann gilt p|d.

Es ist möglich, dass d = n ist. In diesem Fall scheitert der Algorithmus. Jedoch ist das unwahrscheinlich falls n mindestens zwei große unterschiedliche Primfaktoren hat.

Beispiel

Sei n = 27869. Man wähle nun eine Glattheitsschranke B, etwa B = 8 und wähle eine weitere Zahl a₀, wobei 2 ≤ a₀ ≤ n-1, in diesem Fall etwa a = 3.
Als ersten Schritt berechne man den ggT(a₀ , n) = ggT(3, 27869) = 1. (Hätten wir hier ein d ≠ 1 so hätten wir bereits unseren nicht-trivialen Faktor).
Nun berechnet man für jeden Primfaktor q_i ≤ B:
1. l_i = ⌊ ln n / ln q_i ⌋
2. a_i+1 = a_i^ql_i mod n
Also ist:
a₀ = 3,
q₁ = 2, l₁ = ⌊ ln n / ln q₁ ⌋ = ⌊ 10,23527 / 0.69315 ⌋ = 14, a₁ = 14465
q₂ = 3, l₂ = 9, a₂ = 17337
q₃ = 5, l₃ = 6, a₃ = 18787
q₄ = 7, l₄ = 5, a₄ = 3597
ggT(a₄ - 1, n) = ggT(3596, 27869) = 899.

Im Beispielprogramm wurde der Algorithmus so implementiert, dass nach jedem Schritt der Berechnung von a, der kleinste gemeinsame Teiler berechnet wird. Es gibt aber noch zahlreiche andere praktische Verbesserungen dieser Methode. Der Algorithmus ist in erster Linie für Zahlen gedacht, die aus einem Produkt von genau zwei großen Primzahlen bestehen. Bei solchen Zahlen ist ein Scheitern des Algorithmuses sehr unwahrscheinlich.

Applet (p-1)-Algorithmus:

Quellcode:
PmeAlgSF.java - Appletoberfläche
PmeAlg.java - Algorithmenklasse

2.4.3 RSA-Faktorisierung