Pollards p-1-Algorithmus

In der Zahlentheorie ist der Algorithmus p - 1 Pollard ein Algorithmus zur ganzzahligen Faktorisierung , der 1974 von John Pollard entwickelt wurde . Es ist ein spezifischer Algorithmus (im Gegensatz zum Generalisten), da er nur mit ganzen Zahlen funktioniert, deren Faktoren eine bestimmte Form haben. Es ist das einfachste Beispiel für einen Faktorisierungsalgorithmus in der modularen Arithmetik .

Die Faktoren, die es findet, sind diejenigen, deren Präzedenzfall p - 1 super glatt (oder extrem zuverlässig ) ist.

Prinzip

Sei n eine durch eine Primzahl p teilbare ganze Zahl mit n ≠ p . Nach Fermats kleinem Theorem haben wir

a ^ {{p-1}} \ equiv 1 {\ pmod {p}}

für eine Primzahl mit p . Hier (mod) bezeichnet Kongruenz über ganze Zahlen .

Dies impliziert, dass wir für jedes Vielfache M von p - 1 haben ${\ displaystyle a ^ {M} \ equiv 1 {\ pmod {p}}}$ weil . ${\ displaystyle a ^ {k (p-1)} \ equiv ({a ^ {p-1}}) ^ {k} \ equiv 1 ^ {k} \ equiv 1 \ mod p}$

Wenn p - 1 ist , B -superlisse für einen Schwellwert B , dann p - 1 teilt die kleinste gemeinsame Vielfache von ganzen Zahlen von 1 bis B . Wenn wir also M = ppcm (1,…, B ) setzen, haben wir

a ^ {M} \ equiv 1 {\ pmod {p}}

für alles

eine

Primzahl mit p .

Mit anderen Worten, p teilt a M - 1 und daher ist der gcd von n und a M - 1 größer oder gleich p . Andererseits ist es möglich, dass dieser gcd gleich n selbst ist. In diesem Fall erhalten wir keinen nicht trivialen Faktor.

Beispiel eines Sonderfalls

Sei n = pqr , wobei p und q unterschiedliche Primzahlen sind und r eine ganze Zahl ist, so dass p - 1 B - Superliss und q - 1 keine B - Superlinien ist. Dann liefert gcd ( a M - 1, n ) einen Eigenfaktor von n .

Es ist zu beachten, dass in dem Fall, in dem q - 1 B - Superlisse ist, der gcd einen trivialen Faktor erzeugen kann, weil q ein M - 1 teilt .

Wir können feststellen, dass es diese Eigenschaft ist, die den Algorithmus spezifisch macht. Zum Beispiel 172189 = 421 × 409. Oder 421-1 = 2 2 × 3 × 5 × 7 und 409-1 = 2 3 × 3 × 17. Ein geeigneter Wert für B wäre also zwischen 7 und 16. Wenn wir B kleiner als 7 gewählt hätten, wäre der gcd 1 gewesen, und wenn wir B größer als 16 gewählt hätten, wäre der pgcd n gewesen . Natürlich kann man nicht im Voraus wissen, welcher Wert von B angemessen ist, daher ist dies ein Faktor, der im Algorithmus berücksichtigt werden muss.

Zur Beschleunigung der Berechnungen, wir wissen auch , dass es möglich ist, die GCD zu berechnen, zu reduzieren , bis M - 1 modulo n : PGCD ( ein M - 1, n ) = PGCD ( ein M - 1 mod n , n ). Sie kann mithilfe der modularen Exponentiation und des Euklid-Algorithmus effizient berechnet werden .

Algorithmus und Ausführungszeit

Der grundlegende Algorithmus kann wie folgt geschrieben werden:

Einträge : n : eine zusammengesetzte Ganzzahl Beenden : ein nicht trivialer Faktor von n oder ein Fehler

Wählen Sie eine Bröckeligkeitsschwelle B.
eine nehme eine zufällig in (Anmerkung: wir bereits festlegen ein , eine zufällige Auswahl hier ist nicht zwingend notwendig) $({\ mathbb {Z}} / n {\ mathbb {Z}}) ^ {*}$
für jede Primzahl q ≤ B (am Ende dieser Schleife, wir haben M ) mod n
$e \ bekommt {\ bigg \ lfloor} {\ frac {\ log {B}} {\ log {q}}} {\ bigg \ rfloor}$
$a \ bekommt ein ^ {{q ^ {e}}} \ mod {n}$
$g \ leftarrow \ operatorname {pgcd} (a-1, n)$
wenn 1 < g <n, dann g zurückgeben
Wenn g = 1, wählen Sie ein größeres B und fahren Sie mit Schritt 2 fort oder geben Sie den Fehler zurück
Wenn g = n, fahren Sie mit Schritt 2 fort oder geben Sie den Fehler zurück

Wenn wir in Schritt 6 g = 1 erhalten, bedeutet dies, dass unter allen p - 1 keine B- Superlisse war. Wenn wir in Schritt 7 g = n erhalten , zeigt dies normalerweise an, dass alle Faktoren B- Superlins waren, aber in seltenen Fällen könnte dies darauf hinweisen, dass a ein Modulo p kleiner Ordnung hat .

Variante für große Primzahlen

Manchmal wird eine Variation des Basisalgorithmus verwendet. Statistisch gesehen gibt es häufig einen Faktor p von n derart , daß p - 1 = fq wo f ist B -superlisse und B < q ≤ B ‚wobei q eine Primzahl ist und B ‘ gebunden sind , eine halbglatten genannt.

Diese Variante kann ab Schritt 6 des Basisalgorithmus angewendet werden, wenn wir gcd = 1 finden, dies jedoch nicht erwünscht ist, um B zu erhöhen . Für alle Primzahlen B < q 1 ,…, q L ≤ B ' prüfen wir, ob

{\ displaystyle \ operatorname {pgcd} \ left (a ^ {q_ {i} M} -1, n \ right) \ neq 1}

um einen nicht trivialen Faktor von n zu erhalten . Dies ist schnell erledigt, denn wenn wir c = a M , d 1 = q 1 und d i = q i - q i - 1 haben , können wir berechnen

{\ displaystyle a ^ {q_ {1} M} = c ^ {d_ {1}}, a ^ {q_ {2} M} = c ^ {d_ {1}} c ^ {d_ {2}} = a ^ {q_ {1} M} c ^ {d_ {2}}, \ ldots}

Die Ausführungszeit des Algorithmus mit dieser Variante wird dann O ( B '× log B ' × log 2 n ).

Kryptologische Konsequenz

Die Effizienz dieses Algorithmus hängt mit der Form der Primzahlen zusammen, aus denen die zu faktorisierende ganze Zahl besteht, genauer gesagt mit der Existenz eines Primfaktors p, so dass p - 1 B - Superlisse ist. Folglich erfordern Verschlüsselungssysteme mit öffentlichem Schlüssel , die auf der Schwierigkeit der Faktorisierung basieren, wie z. B. RSA , die Verwendung von Primzahlen, die diese Eigenschaft nicht haben, für einen zu kleinen Schwellenwert B.

Verweise

Pascal Boyer, Kleiner Begleiter der Zahlen und ihrer Anwendungen , Paris / 58-Clamecy, Calvage und Mounet,2019648 p. ( ISBN 978-2-916352-75-6 ) , VI. Kryptographie, Kap. 4. ("RSA"), p. 529-534.

Siehe auch

Pollards Rho-Algorithmus
Lenstra elliptische Kurvenfaktorisierung
P + 1 Algorithmus Williams (in)