Der Prozess zur Feststellung, ob eine ganze Zahl n B‑glatt ist, d. h. ob alle Primfaktoren von n ≤ B sind, üblicherweise durch Versuchsfaktorisierung bis zur Grenze B oder durch spezialisierte Glattheitstests.

Prinzip

Verwende Trial‑Division durch alle Primzahlen ≤ B als ersten Schritt, kombiniert mit Siebverfahren und partiellen Faktorisierungsmethoden (Pollard‑Rho, p−1, ECM), um verbleibende große Cofaktoren zu erkennen; Glattheit wird nur zertifiziert, wenn die vollständige Faktorisierung nur Primfaktoren ≤ B zeigt.

Demonstration

Beispiel: n = 360 = 2^3·3^2·5 ist 5‑glatt, da der größte Primfaktor 5 ist; dagegen ist 1001 = 7·11·13 nicht 5‑glatt, da Primfaktoren >5 vorkommen.

Fehlanwendung

Das Vorhandensein vieler kleiner Faktoren mit B‑Glattheit verwechseln oder Trial‑Division vorzeitig abbrechen und fälschlich Glattheit behaupten, während ein unbekannter großer Primfaktor existiert; auch probabilistische Heuristiken als Beweis zu verwenden ist fehlerhaft.

Konsequenz

Glattheitserkennung ist wichtig für Faktorisierungsstrategien (ECM, quadratisches Sieb), kryptanalyse‑Methoden, die glatte Ordnungen ausnutzen, und Komplexitätsanalysen, bei denen glatte Eingaben schnellere Algorithmen erlauben.

Umkehrung

Das Gegenproblem ist die Rauheitserkennung: das Finden eines Primfaktors >B kann in manchen Fällen schneller sein (einen großen Primfaktor nachweisen) und ist die Negation der Glattheit.

Abgrenzung

Gilt für positive ganze Zahlen und eine explizite Schranke B≥2; erfordert vollständige Faktorisierung bis B, um Glattheit zu zertifizieren; schließt multiplikative Strukturen in Ringen mit abweichender Primzahldefinition aus, sofern nicht die passenden Primfaktoren interpretiert werden.

Semantische Spannung

Spannung zwischen praktischem heuristischem Screening (schnelle probabilistische Tests oder partielle Siebe) und rigoroser Zertifizierung (vollständige Faktorisierung) sowie zwischen der Häufung kleiner Faktoren und einem einzelnen großen Faktor, der Glattheit zerstört.

Synthese

Glattheitstestung ist die prozedurale Aufgabe, zu verifizieren, dass jeder Primteiler einer Zahl unter einer gegebenen Schranke B liegt; dies geschieht durch Trial‑Division, Siebverfahren und gezielte Faktorisierungsmethoden und bildet ein zentrales Prädikat in zahlentheoretischen Algorithmen und der Kryptanalyse.