Wann was — Methodenübersicht
| Aufgabe | Methode | Komplexität |
|---|---|---|
| ggT zweier Zahlen | Euklid | O(log min(a,b)) |
| kgV | (a · b) / ggT | O(log) |
| Inverses mod n | Erweiterter Euklid | O(log n) |
| a^k mod n | Square-and-Multiply | O(log k) |
| Primzahltest klein | Trial Division bis √n | O(√n) |
| Primzahltest groß | Miller-Rabin (probabilistisch) | O(log³ n) |
| Faktorisieren groß | Quadratisches Sieb / GNFS | schwer |
| RSA verschlüsseln | m^e mod n | O(log e · log² n) |
Sicherheit von RSARSA bricht zusammen, sobald jemand n in Primfaktoren zerlegen kann. Aktuell: 2048-Bit-Schlüssel sicher. Quantencomputer könnten das ändern (Shor-Algorithmus).