Hans-Gert Gräbe: Algorithmen für Zahlen und Primzahlen 1. Auflage Reihe "Eagle Guide" EAGLE Verlag, Leipzig 2012 http://www.eagle-leipzig.de/058-graebe.htm

Über das Buch

The Rabin-Miller strong pseudoprime test is a particularly efficient test. Mathematica versions 2.2 and later have implemented the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test as the primality test used by the function PrimeQ[n]. Like many such algorithms, it is a probabilistic test using pseudoprimes. In order to guarantee primality, a much slower deterministic algorithm must be used. However, no numbers are actually known that pass advanced probabilistic tests (such as Rabin-Miller) yet are actually composite.

Nach einer Rekapitulation von Konzepten rund um den Teilbarkeitsbegriff im (Kapitel 2) werden die wichtigsten algorithmischen Ideen zum Rechnen mit langen Zahlen (Kapitel 3) sowie zum Rechnen mit Resten (Kapitel 4) zusammengetragen, ehe es mit Primtestverfahren auf der Basis des Fermat-Tests (Kapitel 5) richtig los geht. Nach einem Intermezzo zu einem "much slower deterministic algorithm", mit dem sich Primzahlen zertifizieren lassen (Kapitel 6), kommen mit dem Lucas-Test (Kapitel 7) etwas komplexere zahlentheoretische Konzepte zum Einsatz, mit denen sich dann auch das Gebiet der Primzahlrekorde (Kapitel 8) am Beispiel der Fermatzahlen sowie der Mersennezahlen konzeptionell genauer ausleuchten lässt.

Alle Algorithmen sind in der Notation des Open Source Computeralgebra-Systems Maxima angegeben und können leicht selbst nachvollzogen und modifiziert werden.

Inhalt:

• Was Sie erwartet
• Zahlen und Primzahlen – grundlegende Eigenschaften
• Das Rechnen mit ganzen Zahlen. Die Langzahlarithmetik und deren Komplexität
• Rechnen mit Resten
• Primzahl-Testverfahren
• Primzahl-Zertifikate
• Der Lucas-Test
• Primzahlrekorde

Hans-Gert Gräbe, Juni 2012