Direkt zum Inhalt

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 x2y2 mod N und x ≢ ±y mod N, dann teilt n die Zahl x2y2, aber nicht x + y und xy. Damit ist der größte gemeinsame Teiler von N und xy ein echter Teiler von N.

Die Schwierigkeit, große Zahlen zu faktorisieren, ist die Grundlage einiger Kryptosysteme.

Schreiben Sie uns!

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.