Lexikon der Mathematik: Faktorisierung natürlicher Zahlen
das Zerlegen von natürlichen Zahlen in Produkte von Primzahlen.
Die wichtigsten modernen Faktorisierungsverfahren sind die elliptische Kurvenmethode, das quadratische Sieb und das Zahlkörpersieb.
Das quadratische Sieb basiert auf der Bestimmung quadratischer Kongruenzen: Seien x, y ganze Zahlen und x2 ≡ y2 mod N und x ≢ ±y mod N, dann teilt n die Zahl x2 − y2, aber nicht x + y und x − y. Damit ist der größte gemeinsame Teiler von N und x − y ein echter Teiler von N.
Die Schwierigkeit, große Zahlen zu faktorisieren, ist die Grundlage einiger Kryptosysteme.
Schreiben Sie uns!