Deterministisch polynomielle Primzahlverfahren : Über die Entwicklung effizienter Primzahltests der AKS-Klasse

ISBN-13: 9783639116144 / Niemiecki / Miękka / 2009 / 260 str.

Jörg Lässig

Opis

Im August 2002 haben die drei indischen ForscherManindra Agrawal, Neeraj Kayal und Nitin Saxena amIndian Institute of Technology in Kanpur in einemManuskript unter dem Titel "PRIMES is in P" einenAlgorithmus präsentiert, der deterministisch inPolynomialzeit für eine gegebene natürliche Zahlfeststellt, ob diese prim oder zusammengesetzt ist.Bisher waren nur probabilistischePolynomialzeitalgorithmen zur Entscheidung diesesProblems bekannt, also Algorithmen, die eine gewisseFehlerwahrscheinlichkeit für die Ausgabe aufweisen.Es gab in der Folge eine Reihe vonVeröffentlichungen, die Varianten des Algorithmuspublizierten und damit die sogenannten AKS-KlasseAlgorithmen bilden. Die darin beschriebenenVerbesserungen des Originalalgorithmus sind vonerheblichem Umfang und beschleunigen das Verfahren imBereich mehrerer Größenordnungen. Primzahlverfahrensind aufgrund vielfältiger Anwendung vor allem inverschiedenen Verfahren der Kryptographie vonerheblicher praktischer Bedeutung. Das vorliegendeBuch behandelt umfassend die Algorithmen derAKS-Klasse und deren Entwicklung sowie die zumVerständnis notwendigen mathematischen Grundlagenaber auch weitere Verbesserungsansätze.

O autorze

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.