unerklärlicher fehler bei nichtprimzahl-test

[negaH]

Result := (Power(a, n-1) mod n) <> 1; Also das kann garnicht funktionieren.

Der Fermat-Test ist so definiert

A ^ (N-1) mod N |= 1 mod N

dies bedeutet das wir in modularen Ringen arbeiten.
Angenommen A = 3 und N = 1000 dann würde Power(A, N-1) == 3^999 werden. Diese riesige Zahl kann aber in einem Fließkommadatentyp nicht mehr EXAKT gespeichert werden. Ergo: mit Fließkommazahlen wird der Wert 3^999 gerundet/abgeschnitten gespeichert. Die nachfolgende modulare Division mit N wird also je nach Rundungsfehler in den Fliekommazahlen ein nicht mehr mathematisch aussagekräftiges Resulat liefern.

Der obige Code ist also programmtechnisch eine falsche Umsetzung der nötigen Mathematik. Du solltest dir an solchen Beispielen kein Beispiel nehmen.

Der richtige Weg wäre die Implementation einer eigenen modularen Exponentation die mit Ganzzahlen arbeitet. Beim Fermat Test MUSS jedes einzelne Zahlenbit absolut exakt berechnet werden, Fließkommazahlen haben darin nichts zu suchen.

Es ist besser hier in Forum nach meinem schnellen Primzahltest zu suchen.
Anbei mein Code zum schnellen Test einer Zahl < 2^32 auf Primzahleigenschaft.
Der normale Fermat Test wie oben gezeigt würde nämlich auch Zusammengesetzte Zahlen als Primzahlen ausweisen die garkeine Primzahlen sind. Ich weis nicht was deine Kids davon halten sollen wenn sie durch dummen Zufall eine sogenannte Carmichael Zahl eingeben und dein Program sagt ads es eine Primzahl wäre, obwohl ads natürlich bei Carmichaelzahlen falsch ist.


Gruß Hagen