Deterministisch polynomielle Primzahlverfahren

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.

promoviert derzeit nach einem Studium der Informatik sowie der Computerphysik in Chemnitz und Melbourne über effiziente Algorithmen und Modelle zur Kooperationsgenerierung und -steuerung an der TU Chemnitz. Zu seinen Forschungsgebieten zählen Kombinatorische Optimierung, Algorithm Engineering und intelligente Systeme.