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.