unerklärlicher fehler bei nichtprimzahl-test

[negaH]

Zitat:

Allerdings kommt es doch im Endeffekt auf's Gleiche raus, da 1 mod N grundsätzlich 1 ist, oder nicht (sofern N > 0, was allerdings eine Vorraussetzung ist)?

1 mod N == -1 mod N == (N-1) mod N == (N+1) mod N == (N*N +1) mod N

oder
0 == 0 mod N == N mod N

Zitat:

Zitat:

dies bedeutet das wir in modularen Ringen arbeiten.

Klar, aber ändert das etwas Grundlegendes jetzt?

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.

Zitat:

Gut. Aber das ist wenn dann ein Problem des Fermat-Tests (er ließe sich durch eine schnellere Power-Methode ein wenig optimieren, aber ich denke nicht, dass es dadurch extreme Vorteile geben würde) und nicht des Codes.

Eben falsch. Der optimierte Code einer modularen Exponentation beseitigt zwei Probleme:
1.) notwendige Genauigkeiten durch kleinere Zahlen
2.) erheblich bessere Effitzienz, und wir reden hier von mehr als 1000 mal schneller !!

Zitat:

Abgesehen davon handelt es sich hier - wie gesagt - um ein kleines Übungsprogramm. Solche große Zahlen kommen hier wohl nicht vor.

Das spielt keine Rolle, bzw. ist dir nicht ganz bewusst wie schnell die Zahlenbereiche ansteigen. "Kleine Zahl" was bedeutet dies für dich ? 4,5,6 oder 100,200,300 oder 10000,20000,30000 ?
Angenommen N wäre nur 49. Wir benutzen die Basis 3, ergo 3^(49-1) mod 49. 3^48 übersteigt schon die Fähigkeiten von Double Datentypen diese Zahl aufs letzte Bit exakt zu speichern. Aber eine modulare Exponentation arbeitet in jedem Schritt mit Zahlen bis maximal 48*48 -1, größer können die Zwischenergebnisse nicht werden, da ja nach jedem Schritt modular mit 48 reduziert wird. Wir könnten also 3^(49-1) mod 49 mit Byte-Arithmetik exakt ausrechnen.

Angenommen N=10000 -> 3^9999 mod 10000. Es ist nun ein gewaltiger Unterschied ob man 3^9999 erst komplett ausrechnet und so eine 15849 Bit große Zahl mit 10000 modular reduzieren muß -> dividieren. Oder ob man schon während des Ausrechnens von 3^9999 in jedem Zwischenschritt mit mod 10000 reduziert. Bei diesem Weg benötigt man insgesamt 13 Schritte und somit 13 modulare Quadierungen + 8 modulare Multiplikationen mit Zahlen < 10000^2.
Statt mit 2^15849 !!

Zitat:

Ersetzung der Power-Methode ist natürlich ratsam

Erstmal eines vorweg: ich greife NICHT deinen Vorschlag wegen DEINER Person an. Sondern gerade weil dein Vorschlag eine technisch mathematisch falsche Lösung darstellt versuche ich nur dies zu korregieren.

Es ist also nicht nur ratsam die obige Power Funktion zu ersetzen, sondern es ist damit alles mathematisch korrekt funktionieren kann zwingend erforderlich.

Weist du, es würde mich in keinster Weise stören wenn dein Vorschlag korrekt funktionieren würde, aber unschön, ineffizient oder so wäre. Aber in diesem Falle produziert dieser Test schon mit sehr kleinen Zahlen falsche Ergebnisse.

Zitat:

Zitat:

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

"programmtechnisch eine falsche Umsetzung"? Unvollständig, suboptimal oder nicht gelungene ist vielleicht besser angebracht. Falsch ist das oben m.E.n. nicht. Lasse mich gerne aber eines besseren belehren.

Falsche technische Realisation durch die Benutzung inadequater Datentypen zu einer math. Formel.
Der benutzte Fließkommadatentyp reicht bei weitem nicht aus um zb. Zahlen > 2^48 exxakt zu berechnen. Leider beinhaltet die Formel eine Exponentation, und diese hat die blöde Eigenschaft eben aus kleinen Zahlen ganz gewaltig schnell sehr große Zahlen werden zu lassen.
Und zweites arbeiten wir in mordularen Ringen, Kongruenzklassen und die können als Formel nur dann funktionierern wenn man die Zahlen Bitexakt berechnet. Einem Physiker reichen meistens 20 Stellen nach dem Komma aus, um Primzahlen zu erkennen mit Fermats einfacher Formel müssen wir aber mit Ganzzahlen absolut korrekt rechnen.

Schau, ich möchte nicht dich oder irgendjemand sonst beleidigen oder kritisieren, aber fakt ist das obige Lösung als Umsetzung der Fermatschen Formel absolut untauglich ist. Tja, was soll ich nun anderes tuen und exakt dieses "falsch" klipp und klar aussprechen. Man könnte jetzt lange drumherumreden, um ja nicht als Nörgler abgestempelt zu werden, um ja nicht irgendwelche Gefühle zu verletzen. Das ist aber nicht mein Ding, falsch bleibt falsch, die Begründung dafür habe ich geliefert. Kritik ist doch nichts schlechtes und eine "höflicher" ausgedrückte Kritik macht doch dan kritisierten Fehler nicht weniger zum Fehler. Ehrlich gesagt, nervt es mich auch ein bischen das in heutiger Zeit alle so empfindlich auf ein par Worte in einem Forum reagieren. Das kostet doch alles Zeit.

Zitat:

Ich muss aber sagen, dass ich bei meinem Ursprungs-Posting nicht an die Fließkomma-Verwendung gedacht habe.

Ey, du musst dich nicht entschuldigen, wie gesagt keiner hat dich persönlich angegriffen. Ich sehe es positiv, du hast was dazu gelernt und ich durfte mein Wissen mit dir teilen, und beide haben wir eine klitzekleine Spur im Sand des WWW hinterlassen

Zitat:

Allerdings hättest du auch deine Kritik ein wenig früher üben können, als die Funktion auf diese Art und Weise zu zerreißen.

Dazu muß ich erstmal die Zeit haben alle Postuings hier genauer zu lesen Egal, ich kann immer nur von Zeit zu Zeit ein par Stunden freimachen und durchstöbere dann die DP. Wichtig ist doch nicht der Zeitpunkt ansich sondern das man überhaupt das Problem genauer beschreibt.

Zitat:

Schlauerweise steht ja auch unter dem Source - sofern du weitergelesen hast - dass es sich hier um einen NICHT-Primzahltest handelt.

also jetzt wirst du spitzfindig. Es gibt Primzahlen und Zusammengesetzte Zahlen. Ein Primzahltest beantwortet die Frage ob eine Zahl eine Primzahl ist, ein NICHT-Primzahl-Test beantwortet die Frage ob die Zahl NICHT-Primzahl ist, also exakt negiert zum Primzahltest.

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.

Zitat:

Zitat von Wikipedia:

Wenn man nur auf die Basis 2 testet, dann kann man nur bis 340 sicher sein, dass man zu 100% ein korrektes Ergebnis bekommt.

Es sei denn man hat verschiedene feste Basen und andere schlaue Leute haben sich schon die Mühe gemacht zu verifizieren inwieweit der SPP-Test immer die korrekte Antwort liefert. Sprich sie haben die obere Zahlen-Schranke ermittelt ab dem ein spezifischer Test eine falsche Antwort liefert.

Zitat:

Ich weiß nicht genau, aber dein zweiter Post widerspricht sich ein wenig zum ersten ("Der Ansatz ist ja auch richtig.")

Nein, ich tue mich sehr selten widersprechen, dies ist eines meiner mir durch meinen Vater "eingeimpften" Prinzipien. (der liebe Gott soll ihn selig haben, eingeimpft wörtlich nach alten Erziehungsmethoden)

Der Ansatz, für einen Primzahltest, auf Fermat und den davon abgeleiteten und besseren Primzahltest zu verweisen, als Lösung eines Zahlenproblemes, ist absolut richtig. Falsch wäre als Lösung vorzuschlagen Blaue Schuhe beim OBI kaufen zu gehen.

Nicht korrekt ist aber die all zu simplizistische Umsetzung der Fermatschen Formel mit Hilfe von Fließkommazahlen und in der falschen Zahlendomain also nicht modularen Restringen.

Zitat:

aber ich hab jetzt nur mal versucht mich ein wenig zu rechtfertigen...

Nochmals: siehe meine Kritik als eine Kritik dem bösen Posting daoben Mich interessiert es einen Scheiß ob du das verzapft hast oder ein anderer oder ich. Mir geht es um die Richtigstellung eines Sachverhaltes.

Gruß Hagen

[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

[negaH]

Zitat:

aja, 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?

Vielleicht nochmal andersherum: Wenn der Test sagt das eine Zahl eine zusammengesetzte Zahl ist dann ist die Zahl keine Primzahl. Wenn die Funktion sagt das die Zahl keine zusammengesetzte Zahl ist dann muß die Zahl eine Primzahl sein. Die Funktione darf eine Primzahl nicht als zusammengesetzte Zahl und eine zusammengesetzte Zahl nicht als Primzahl ausweisen, logisch oder ? Ergo: wenn der Test TRUE bei einer Zusammengesetzten Zahl ausgibt dann gibt sie FALSE bei einer Primzahl aus. Ergo: NOT Function() gibt demzufolge TRUE für eine Primzahl aus und FALSE für eine NICHT-Primzahl. Die Funktion kann nur ein TRUE oder FALSE zurückgeben da es nur Primzahlen und Nicht-Primzahlen gibt. Würde die Funktion TRUE,FALSE und ICH_WEIS_NICHT_SO_RECHT ausgeben so würde die funktion die Frage nach der Form einer Zahl nicht korrekt beantworten, sie wäre also nicht exakt. Oder aber es gäbe neben den Primzahlen und Zusammengesetzten Zahlen noch andere Prim-Zusammengesetzte Zahlen. Der letztere Fall kann mathematisch ausgeschlossen werden, der erster Fall bedeutet das die Funktion kurz gesagt "mist" ist.

Ergo: wenn der Test 100% die Aussage bringt FALSE dann sollte es zu 100% bedeuten das die zahl eine Primzahl ist.
Soweit zur analytisch hypothetischen Seite des Problemes.

Worauf du aber nun hinauswillst ist der Fakt das man mit Fermats Formel eben nicht 100%tig sicher sein kann wenn er sagt die Zahl IST eine Primzahl. Sagt der Test die Zahl ist KEINE Primzahl dann sollte diese Aussage 100% richtig sein ! Mit Fermats Formel und allen anderen Pseudo Primzahl Test kann man also eine Nicht-Primzahl immer zu 100% exakt bestimmen aber eine Primzahl nur mit einer großen Wahrscheinlichkeit unterhalb 100%.

Ergo: Wenn dein Test die Frage beantwortet "ist die Zahl zusammengesetzt" dann kann dein Test auf Basis der Fermatschen Formel sehr wohl zu 100% sicher diese Aussage treffen wenn er erkennt das es eine zusammengesetzte Zahl ist. Wenn der Fermatsche Test aber sagt es wäre eine Primzahl dann ist dies nicht 100% sicher.

Ich weis es ist ein bischen kompliziert zu verstehen und auch ich habe einige Zeit gebracht es zu verdauen.

Praktisch gesehen bedeutet das:
Wenn Fermats Formel eine Zahl als Zusammengesetzte = Nicht-Primzahl ausweist dann mit 100% Sicherheit.
Dies bedeutet aber NICHT das Fermats Formel jede zusammengesetzte Zahl wirklich findet ! Es gibt also zusammengesetzte Zahlen die Fermats Formel als "ich glaube es ist eine Primzahl" ausweist.

Nun kommen wird dem Punkt näher zu deiner ersten Lösung mit Fließkomma-Power. Da deren Zahlenbereich auf Grund der Floats sehr schnell überschritten sind würde eine darauf basierende Funktion auch bei Zusammengesetzten Zahlen eine falsche Antwort liefern. Eben ganz im Gegensatz zu Fermatschen Formel.

Das heist aber praktisch gesehen eben nicht das der Fermatsche Test jede zusammengesetzte Zahl auch wirklich findet ! Es ist also ein Unterschied ob man die Sicherheit betrachtet wann der Test eine Zahl als zusammengesetzt erkennt oder wie sicher man sich sein kann wenn er eine zusammengesetzte Zahl erkannt hat. Sagt Fermats Formel das eine Zahl zusammengesetzt ist dann kann man sich absolut sicher sein das diese Zahl eine zusammengesetzte, also Nicht-Primzahl ist. Wenn der Test aber sagt das es eine Primzahl ist dann besteht die minimale Wahrscheinlichkeit das es denoch eine zusammengesetzte Zahl ist. Der Test erkennt also nicht sicher ob eine Zahl nun zusammengesetzt oder prim ist, aber wenn er eine zusammengesetzte Zahl erkannt hat dann mit 100% Sicherheit. Wenn er eine Zahl als Primzahl ausweist dann kann man sich nicht 100% sicher sein.

Deine Power Funktion auf Basis der Floats würde aber nun bei einer zusammengesetzten Zahl eben nicht mehr zu 100% sicher sein. Viel schlimmer noch, auf Grund der Ungenauigkeiten der Floats könnte sie Zahlen als prim ausweisen die ein korrekt umgesetzter Test als zusammengesetzt erkennen würde.

So jetzt muß ich mich erstmal wieder zusammensetzen um prim zu werden Es reicht.

Zitat:

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;

Das ist schonmal ein richtiger Ansatz aber eben wieder simplizistisch bzw. straight forward. Diese Methode spart nichts an Rechenzeit, leider.

Einfaches Beispiel:

3^8 mod X

du machst 3 mod X * 3 mod X * 3 mod X... abgekürzt also 3*3*3*3*3*3*3*3 wobei nach jeder Multiplikation modulo gerechnet wird.

Wie wäre es aber mit (((3^2 mod X)^2 mod X)^2 mod X, wobei nun ^2 eine Quadierung ist ? Für 3^8 benötigen wir nun nur noch 3 modulare Quadrierungen statt 8 modulare Multiplikationen. Man muß dabei wissen das eine Quadrierung auf einem Rechner 150% schneller ausgeführt werden kann als eine generische Multiplikation zweier gleichgroßer Multiplikaten. Dieser Faktor von 150% bzw. 1.5 ist ein mathematisch bewiesener Faktor und die heutzutage theoretisch angenommene und mathematisch bewiesene maximale Schranke. D.h. aus Sicht heutiger Mathematik kann man nicht schneller als 1.5 mal schneller Quadrieren als Multiplizieren.

Aber dies reicht uns ja schon aus, denn es bedeutet das ein Algorithmus der mit gleicher Anzahl an Quadrierungen arbeitet statt Multiplikationen immer bis zu 1.5 mal schneller sein kann. Ich persönlich konnte in meinem DECMath exakt die 1.5 praktisch bestätigen. Mit normalen Integern oder der ineffizienten Int64 Borland Funktionen kann man diesen Faktor nicht nachweisen.

So wie kommen wir aber zu einem Algo. der die korrekte Sequenz von Quadrierungen+Multiplikationen der Exponentation ermitteln kann ?

Betrachten wir 3^9:
Die kürzeste Formel lautet 3^8 * 3^1 = 3^(8 +1) weil 8 zerlegt werden kann in 2^3, ergo 3^2^2^2*3 wobei in jedem Schritt modular reduziert werden muß. Für 3^9 mod X benötigen wird also 3 Quadrierungen und 1 Multiplikation. Nun schauen wir uns mal den Exponenten 9 als Binärzahl an 1001b. Wir wisen das diese Zahl 4 Bits hat und 2 Bit sind auf 1 gesetzt. Wir schneiden das oberste Bit ab, ignorieren es, es bleiben 3 Bit Größe und 1 Bit auf 1 gesetzt -> ergibt 3 Quadrierungen + 1 Multiplikation.
Anderes Beispiel 3^11:
11 in binär ist 1011b wir schneiden oberstes Bit ab -> 011b es bleiben 3 Bit Gesamtgröße und 2 Bits gesetzt ergo 3 Quadrierungen + 2 Multiplikationen, nämlich ((3^2)^2*3)^2*3. Unsere Schleife benötigt 3 Durchläufe die man an den Klammern erkennt, also 3 Quadrierungen und 2 Multipliaktionen.

Der Algo sähe als nun so aus

Delphi-Quellcode:

Base := Base mod Modulus;
Result := Base;
for I := HighestBit(Exponent) -1 downto 0 do
begin
  Result := (Result * Result) mod Modulus;
  if BitIsSet(Exponent, I) then
    Result := (Result * Base) mod Modulus;
end;

Diese Methode nennt sich Modulare Exponentation nach der Binären Links-nach-Rechts expansion. Es gibt noch einige andere, zb. rekursive von Rechts-nach-Links oder trinäre mit +- Basen zb. in der Elliptischen Kurven Multipliaktion häufig verwendet. Es gibt einen ganzen Wissenschaftszweig der sich mit dem Problem der Zerlegung des Exponenten in den kürzesten Weg mit der geringsten Anzahl an Quadrierungen und Multipliaktionen forscht. Dieses Pronlem in ein angeblich NP vollständiges Problem und fällt auch in die große Gruppe der Kantenioptimierungen, Wegealgorithmen etc.pp.

Aber obiger Pseudocode ist "nearly optimal" und findet aufeinfache Weise fast immer den kürzesten Weg, zumindestens ausreichend für unsere Bedürfnisse.

Gruß Hagen