Deterministisch polynomielle Primzahlverfahren

Über die Entwicklung effizienter Primzahltests der AKS-Klasse

ISBN: 978-3-639-11614-4
Verlag: VDM Verlag Dr. Müller

Buch, 260 Seiten

Im August 2002 haben die drei indischen Forscher
Manindra Agrawal, Neeraj Kayal und Nitin Saxena am
Indian Institute of Technology in Kanpur in einem
Manuskript unter dem Titel "PRIMES is in P" einen
Algorithmus präsentiert, der deterministisch in
Polynomialzeit für eine gegebene natürliche Zahl
feststellt, ob diese prim oder zusammengesetzt ist.
Bisher waren nur probabilistische
Polynomialzeitalgorithmen zur Entscheidung dieses
Problems bekannt, also Algorithmen, die eine gewisse
Fehlerwahrscheinlichkeit für die Ausgabe aufweisen.
Es gab in der Folge eine Reihe von
Veröffentlichungen, die Varianten des Algorithmus
publizierten und damit die sogenannten AKS-Klasse
Algorithmen bilden. Die darin beschriebenen
Verbesserungen des Originalalgorithmus sind von
erheblichem Umfang und beschleunigen das Verfahren im
Bereich mehrerer Größenordnungen. Primzahlverfahren
sind aufgrund vielfältiger Anwendung vor allem in
verschiedenen Verfahren der Kryptographie von
erheblicher praktischer Bedeutung. Das vorliegende
Buch behandelt umfassend die Algorithmen der
AKS-Klasse und deren Entwicklung sowie die zum
Verständnis notwendigen mathematischen Grundlagen
aber auch weitere Verbesserungsansätze.

Autoren/Hrsg.

Lässig, Jörg

Über Autor(innen)

Jörg Lässig, Studium der Informatik und Computerphysik in Chemnitz und Melbourne. Forschung und Entwicklung in mehreren Industrieprojekten. Forschungsaufenthalte in Stanford, CA und Christchurch, NZ. Promotion über effiziente Algorithmen und Modelle zur Kooperationsgenerierung und -steuerung an der TU Chemnitz.