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.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.