Primzahlen gehören heutzutage zum Herzstück der Kryptographie. Sämtliche gängigen Verschlüsselungsmethoden bauen auf dem RSA-Algorithmus auf, welcher seine Sicherheit im Wesentlichen daraus gewinnt, dass es beinahe unmöglich ist, „große” Zahlen in angemessener Zeit zu faktorisieren. Wie kommt man aber an die benötigten Primzahlen bzw. woher weiß man, ob eine Zahl prim ist, wenn man das doch durch Faktorisieren gar nicht heraus bekommen kann?

Dieser Frage geht das Buch „Primzahltests für Einsteiger” auf den Grund. Anlässe zur Entstehung des Buches waren zum einen der im Jahr 2002 neu entwickelte AKS-Primzahltest sowie ein zu diesem Thema von den Autoren gestalteter Kurs im Rahmen der Deutschen SchülerAkademie. Deren Anspruch ist es demzufolge auch, einen sowohl für Schüler als auch Studenten verständlichen Beweis dafür zu geben, dass der Algorithmus sowohl deterministisch als auch effizient ist. Dadurch sticht der AKS-Algorithmus unter allen anderen Primzahltests hervor.

Um diesem Anspruch gerecht zu werden, sind natürlich Einführungen in die Gebiete Zahlentheorie und Algorithmik notwendig. Davon werden dann auch die ersten beiden Drittel des Buches eingenommen, wobei dies vermutlich schlimmer klingt als es ist – zum einen haben die Autoren einen sehr angenehmen Schreibstil gefunden, zum anderen bleibt der Bezug zum eigentlichen Ziel des Buches stets gewahrt. Im letzten Drittel dreht sich wirklich alles um den AKS-Algorithmus, allerdings werden die Beweise hier etwas technischer. Den Abschluss der einzelnen Unterkapitel bilden stets die Rubriken „Aufgaben” und „Weiterführende Übungen und Anmerkungen”. Positiv ist hierbei anzumerken, dass die Aufgabenauswahl der Zielgruppe gerecht wird, insbesondere erfordern die Aufgaben keine überlangen Lösungen.

Für Schüler und Studenten ohne große Vorkenntnisse ist das Buch auf jeden Fall empfehlenswert. Auch wenn manch ein Unbefleckter seine liebe Mühe mit dem Nachvollziehen einiger Beweise über Polynome haben dürfte, kann man den Versuch der Autoren, verständlich für jeden Interessierten zu schreiben, als gelungen werten. Wer allerdings bereits solide Grundkenntnisse in elementarer Zahlentheorie besitzt, wird sich ob der dann langen Wiederholung möglicherweise etwas langweilen.