Neuere probabilistische Primtests

Primzahlen bilden dieGrundlage vieler heutegebräuchlicherVerschlüsselungstechniken,wie zum Beispiel RSA.Daher ist es notwendigsolche Zahlen extremeffizient finden zukönnen. Die meisten der heute gebräuchlichenVerfahren arbeiten dabeiprobabilistisch, das heißtmit einer gewissenFehlerwahrscheinlichkeit.In diesem Buch werdendie wichtigsten derheutzutage verwendetenTests besprochen und ihrFehlerverhaltendiskutiert. Dabei wirdneben einfacheren Test,wie zum Beispiel demFermat-Test, auch neuereMethoden, wie der Lucas-oder der Frobenius-Test,im Detail beschrieben.Zum besserenVerständnis des Texteswird der Leser zuvor mitden wichtigstenalgebraischen undalgorithmischenGrundlagen an dasThema herangeführt.Zudem finden sich zujedem der vorgestelltenTestsImplementierungsvorschlägein der funktionalenProgrammierspracheHaskell.

Klappentext

Primzahlen bilden die Grundlage vieler heute gebräuchlicher Verschlüsselungstechniken, wie zum Beispiel RSA. Daher ist es notwendig solche Zahlen extrem effizient finden zu können. Die meisten der heute gebräuchlichen Verfahren arbeiten dabei probabilistisch, das heißt mit einer gewissen Fehlerwahrscheinlichkeit. In diesem Buch werden die wichtigsten der heutzutage verwendeten Tests besprochen und ihr Fehlerverhalten diskutiert. Dabei wird neben einfacheren Test, wie zum Beispiel dem Fermat-Test, auch neuere Methoden, wie der Lucas- oder der Frobenius-Test, im Detail beschrieben. Zum besseren Verständnis des Textes wird der Leser zuvor mit den wichtigsten algebraischen und algorithmischen Grundlagen an das Thema herangeführt. Zudem finden sich zu jedem der vorgestellten Tests Implementierungsvorschläge in der funktionalen Programmiersprache Haskell.