Faktorisierung großer Zahlen und elliptische Kurven

Eines der großen Probleme der Zahlentheorie ist die Frage, wie Primzahlen erzeugt werden können. Dazu gibt es viel Literatur, (von der hier nur Zagiers Aufsatz [Za] erwähnt werde), obwohl das Problem natürlich auch für die RSA-Methode von Bedeutung ist. Es soll nun nur auf das (damit zusammenhängende) Problem eingegangen werden, wie die beiden Primfaktoren p und q bestimmt werden können, wenn n als Produkt zweier unbekannter Primzahlen gegeben ist. Falls ein Verfahren zur Faktorisierung großer Zahlen gefunden wird, wird das RSA-Verfahren natürlich wertlos.

Es ist eines der großen Geheimnisse der Mathematik, daß bei zunächst rein zahlentheoretisch aussehenden Fragestellungen zunächst nicht zur Zahlentheorie gehöriges Objekte zum Einwirken gebracht werden können, nämlich die elliptischen Kurven.

• Vorbemerkungen über elliptische Kurven
• Elliptische Kurven über endlichen Körpern
• Faktorisierung mit Hilfe elliptischer Kurven
• Ein Kryptosystem zu einer elliptischen Kurve
• Das Problem des diskreten Logarithmus