unerklärlicher fehler bei nichtprimzahl-test

[CalganX]

Hi Hagen,
hm, okay, verstanden worum es dir geht und mir sind auch ein paar Sachen etwas klarer geworden. Und entschuldige, wenn ich ein wenig giftig geantwortet habe.

Zitat:

Aber sicher doch, nämlich die mathematische Sicht. Wenn man schreibt A^(n-1) == 1 mod N dann zeigt dies an das man in einer Kongruenzklasse arbeitet, in einem modularem Restering. Das bedeutet technisch zB. das man auf der Linken Seite alles mod N rechnen kann, in jedem Schritt. Statt also 3^999 komplett ausrechnen zumüssen kann man auch (((((3*3 mod N) * 3) mod N * 3) mod N ... usw. rechnen. Dies produziert ausgehend von der mathematischen Schreibweise eine komplett andere technische Umsetzung.

Das ist mir erst ganz am Ende meines Postings eingefallen. Und das ist der entscheidende Punkt. Wäre also folgende Funktion doch eigentlich wesentlich optimierter, weil sie 1. nicht auf Fließkommazahlen aufbaut und 2. die Rechenarbeit verringert. Oder habe ich noch etwas vergessen?

Delphi-Quellcode:

function PowerMod(Base, Exponent, Modul: longint): longint;
var
  idx: longint;
begin
  Result := -1;
  if (Exponent < 0) then Exit;

  Result := 1;
  for idx:=1 to Exponent do begin
    Result := (Result * Base) mod Modul;
  end; 
end;

function IsNotPrime(a, n: longint): boolean;
begin
  Result := PowerMod(a, n-1, n) <> (1 mod n);
end;

Zitat:

fakt ist das obige Lösung als Umsetzung der Fermatschen Formel absolut untauglich ist

Okay, ich habe vorhin selber gesehen, wie schnell die kleinen Zahlen bei Real oder anderen Float-Typen sehr ungenau werden. Ich war mir vorher gar nicht darüber bewusst wie schnell das passiert. Und das deswegen das Ergebnis schnell daneben liegen kann.

Zitat:

Gäbe es eine weitere Unterscheidung, als nur die Negation des Resultates, zwischen Primzahl-Test und Nicht-Primzahl-Test so würde dies bedeuten das es nicht nur Primzahlen und Zusammengesetzte Zahlen gibt sondern noch eine dritte oder vierte Form. Dies ist zum Glück nicht der Fall (oh und bitte wir reden bekanntermaßen von Ganzzahlen und nichts anderem) also ist es wurscht ob man eine Zahl auf Primzahl testet oder auf Nicht-Primzahl, in beiden Fällen wird man bei einer 100% richtigen Aussage der Funktion wissen um welchen Typus es sich handelt

Naja, wenn aber nun der Test sagt "false" (also die Zahl ist nicht keine Primzahl), dann heißt das doch noch nicht, dass sie automatisch eine Primzahl ist, oder?

Chris