Der Prozess, eine zusammengesetzte ganze Zahl in ein Produkt kleinerer ganzer Zahlen, typischerweise in Primfaktoren, zu zerlegen; für n>1 bedeutet dies die Bestimmung einer Multimenge {p_i} von Primzahlen mit n=∏ p_i^{e_i}.

Prinzip

Ganzzahlfaktorisierung nutzt arithmetische Strukturen (Teilbarkeit, Ordnung von Elementen modulo n, algebraische Faktorisierungen) und algorithmische Techniken (Probenteilung, Siebe, Pollard-Rho, elliptische Kurvenverfahren, Number Field Sieve), um nichttriviale Faktoren zu finden; ihre Schwierigkeit bildet die Grundlage vieler kryptographischer Annahmen.

Demonstration

Konkrete Algorithmen: Probeteilung findet schnell kleine Primfaktoren; Pollard-Rho findet mittlere Faktoren via pseudozufällige Walks; ECM ist effektiv für mittelgroße Primfaktoren; das General Number Field Sieve (GNFS) ist die asymptotisch schnellste bekannte Methode für große allgemeine Zahlen und wird bei Rekordfaktorisierungen eingesetzt.

Fehlanwendung

Zu erwarten, dass eine einzelne heuristische Methode oder ein Algorithmus mit kleinen Parametern alle Zahlen effizient faktorisieren wird (z. B. Pollard-Rho auf semiprime mit sehr großen Primfaktoren anwenden), oder Ganzzahlfaktorisierung mit Polynomfaktorisierung oder Primalitätstest zu verwechseln.

Konsequenz

Erfolgreiche Faktorisierung liefert vollständige arithmetische Information über n (die Primzerlegung) und bricht kryptographische Systeme, die auf der angenommenen Schwierigkeit der Faktorisierung beruhen; algorithmische Fortschritte verschieben die Grenze praktischer Sicherheit und beeinflussen Empfehlungen zur Schlüssellänge.

Umkehrung

Die Umkehrung ist der Primalitätstest: statt Faktoren zu liefern, entscheidet man, ob n prim ist; eine positive Primzahlentscheidung macht Faktorisierung überflüssig, während Faktorisierung streng stärkere Information liefert und in der Regel schwerer zu erhalten ist.

Abgrenzung

Die Aufgabe bezieht sich auf in Standarddarstellung gegebene ganze Zahlen; schließt das Faktorisieren von Idealen in Zahlkörpern, das Faktorisieren von Polynomen über Körpern (verschiedene Algorithmen und Komplexität) und Probleme aus, bei denen spezielle Formen von Zahlen oder zusätzliche Strukturen separat ausgenutzt werden können.

Semantische Spannung

Spannung zwischen worst-case-theoretischer Komplexität und praktischer 'typischer' Schwierigkeit: Einige Zahlen (Sonderformen) lassen sich leicht faktorisieren, während zufällige große Semiprime allen bekannten Algorithmen widerstehen; zudem entsteht Verwirrung zwischen Faktorisieren einer ganzen Zahl und Bestimmen multiplikativer Strukturen in anderen algebraischen Objekten.

Synthese

Ganzzahlfaktorisierung ist die rechnerische Aufgabe, eine ganze Zahl in ihre Primfaktoren zu zerlegen, wobei ein Spektrum von Algorithmen Divisibilitäts- und algebraische Strukturen ausnutzt; die praktische Schwierigkeit hängt von Größe und spezieller Form der Faktoren ab und hat zentrale Bedeutung für die algorithmische Zahlentheorie und Kryptographie.