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