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