Number Field Sieve
Das Zahlkörpersieb ist der schnellste bekannte klassische Faktorisierungsalgorithmus; es konstruiert Quadratkongruenzen über algebraische Zahlkörper mit subexponentieller Komplexität.
Zweck
Große Ganzzahlen (>100 Stellen) auf schnellstem Weg faktorisieren und damit die RSA-Sicherheitsgrenze definieren.
Mechanismus
Man wählt ein Polynom f und eine Ganzzahl m mit f(m)≡0 (mod n) und sucht dann glatte Elemente im algebraischen Zahlkörper Q(α). Lineare Algebra kombiniert sie so, dass die Normen Quadrate werden, was x^2≡y^2 (mod n) liefert. Komplexität L_n[1/3, (64/9)^(1/3)].
Anwendungsfälle
- RSA-Sicherheitsanalyse
- Faktorisierung großer Ganzzahlen
- Kryptographische Anwendungen