Hallo allerseits,
ich suche nach einer schnellen Methode, den kleinsten Primfaktor einer Zahl herauszufinden. Natürlich könnte man einfach alle n von 2 bis n durchprobieren, ob x mod n=0 gilt. Aber gibt es noch eine schnellere Methode?
MfG Z4ppy
Hi z4ppy,
zu deinem Algorithmus fällt mit spontan einer ein, der doppelt so schnell ist: Es reicht nämlich, alle Zahlen bis n/2 zu probieren. 
Grüße,
JPL
Das ist schneller, das stimmt. Aber mir ist grad noch eingefallen:
Man muss nur von 2 bis Wurzel(n) probieren. Denn ist die Zahl keine Primzahl, so muss der kleinste Primfaktor sicher in diesem Interval liegen.
Aber eine schnellere Methode, als durchprobieren, wirds wohl nicht geben, oder?
MfG Z4ppy
Moin,
Um den kleinsten Primfaktor einer Zahl x herauszufinden wird nichts anderes übrig bleiben als die Primzahlen n im Intervall [0;x/2] nacheinander in aufsteigender Reihenfolge zu testen, ob x mod n = 0 ergeben. Für Zahlen, die nicht prim sind, braucht man den Test natürlich nicht durchführen, da bspw. jede gerade Zahl durch zwei teilbar ist.
Gruß,
Ingo
Hallo,
Man muss nur von 2 bis Wurzel(n) probieren. Denn ist die Zahl
keine Primzahl, so muss der kleinste Primfaktor sicher in
diesem Interval liegen.
richtig. Dabei reicht es, nur die ungeraden Zahlen als Teiler zu testen (sofern Du nicht vergisst, die 2 zu prüfen). Das bringt nochmal eine Halbierung des Rechenaufwands.
Um festzustellen, dass eine Zahl knapp unterhalb von 109 prim ist, musst Du dann ungefähr (√109)/2 ≈ 15811 Divisionen durchführen. Wenn Dir das noch zu viel ist, kannst Du eine Tabelle anlegen mit allen Primzahlen 9 ≈ 31622. Von denen gibt es genau 3401 Stück (kleinste: 2; größte: 31607). Die ca. 14 KByte Speicherplatz, den die Tabelle belegt (32-Bit-Integer), ist auf heutigen Rechnern ein Klacks. Indem Du nur die Zahlen in der Tabelle als Teiler prüfst, kannst Du dann mit höchstens 3401 Divisionen jede Zahl unterhalb 109 in ihre Primfaktoren zerlegen bzw. feststellen, dass sie prim ist. Das geht so schnell, dass Du keine Verzögerung spüren wirst.
Aber eine schnellere Methode, als durchprobieren, wirds wohl
nicht geben, oder?
Es gibt eine Reihe von Verfahren, mit denen man größere Zahlen (bis zu einer gewissen Grenze) in relativ kurzer Zeit faktorisieren kann. Sie basieren alle auf bestimmten zahlentheoretischen Zusammenhängen, die weit jenseits von Schulmathematik angesiedelt sind. Das sogenannte Zahlkörpersieb ist der bekannteste Vertreter; eine Übersicht findest Du in der Wikipedia:
http://de.wikipedia.org/wiki/Faktorisierungsverfahren
An sehr, sehr großen Zahlen, wie man sie z. B. in der Kryptographie verwendet, scheitern diese Verfahren aber auch alle. „Scheitern“ heißt: sie haben alle ein schlechtes Laufzeitverhalten, das sich irgendwann bemerkbar macht. Eine Methode zur schnellen Faktorisierung wirklich großer Zahlen hat noch niemand entdeckt.
Gruß
Martin
14 KB sind auf einem PC natürlich kein Problem, allerdings muss ich das auf meinem Taschenrechner (TI-89 Titanium) lösen 
Und dort diese ganzen Primzahlen einzuprogrammieren - vielen Dank 
Aber danke für den Tipp mit den ungeraden Zahlen, das war mir gar nicht eingefallen…
Das mit den anderen Verfahren lass ich dann mal lieber. Auf einem PC könnte ich das natürlich ohne weiteres umsetzen, aber aufm TR wirds schon schwieriger…
MfG Z4ppy
Hallo allerseits,
Hallo, Heribert.
Natürlich könnte man einfach alle n von 2 bis n durchprobieren, ob x
mod n=0 gilt.
Unnötig. Du musst die Schleife nur bis √n laufen lassen - noch nicht einmal bis n/2, wie hier auch schon behauptet wurde.
Ansonsten würde ich einen Kompromiss zwischen der „Schleife mit Gewalt“ und den einfachen Teilbarkeitsregeln wählen:
Wir suchen den kleinsten Primfaktor einer Zahl kP(z).
z ist gerade => kP(z)=2. Fertig.
Quersumme von z ist durch 3 teilbar => kP(z)=3. Fertig.
Letzte Stelle von z ist 0 oder 5 => kP(z)=5. Fertig.
Damit musst du die Schleife nur von 7 bis √z laufen lassen, und zwar logischerweise mit Schrittweite 2.
Wenn dein Rechner 10 (richtige) Stellen hat, ist die maximale Zahl, die du prüfen könntest, 9.999.999.999. Die Wurzel davon wäre 99999. Mit 49999 Schleifenschritten hättest du damit alles erschlagen, was überhaupt geritten und gefahren kommen kann. Das scheint mir ein guter Mittelweg zwischen Speicherbedarf und Rechenweg zu sein.
GEK
Hallo allerseits,
Hallo, Heribert.
Natürlich könnte man einfach alle n von 2 bis n durchprobieren, ob x
mod n=0 gilt.Unnötig. Du musst die Schleife nur bis √n laufen lassen - noch
nicht einmal bis n/2, wie hier auch schon behauptet wurde.Ansonsten würde ich einen Kompromiss zwischen der „Schleife
mit Gewalt“ und den einfachen Teilbarkeitsregeln wählen:Wir suchen den kleinsten Primfaktor einer Zahl kP(z).
z ist gerade => kP(z)=2. Fertig.
Quersumme von z ist durch 3 teilbar => kP(z)=3. Fertig.
Letzte Stelle von z ist 0 oder 5 => kP(z)=5. Fertig.Damit musst du die Schleife nur von 7 bis √z laufen lassen,
und zwar logischerweise mit Schrittweite 2.
Hallo !
Wenn man die möglichen Primfaktoren bis 7 schon getestet hat reicht schon eine Schrittweite von abwechelnd 4 und 2, siehe „Sieb des Eratosthenes“.
hendrik
Hallo,
Und dort diese ganzen Primzahlen einzuprogrammieren
man lässt diese Tabelle natürlich vom Rechner zur Laufzeit generieren! Das ist mit einem bescheidenen Stück Code erledigt:
PROCEDURE GeneratePrimeNumberArray;
VAR
i: INTEGER;
n: LONGINT;
begin
PrimeNumber[0] := 3;
i := 1;
(\* sqrt(10^9) = 31622.776... \*)
FOR n := 4 TO 31623 DO
begin
IF (LowestFactor(n)=n) THEN
begin
PrimeNumber[i] := n;
Inc(i)
end
end
end;
Nach einmaligem Aufruf dieser Routine zum Programmstart enthält das Array „PrimeNumber“ alle Primzahlen zwischen einschließlich 3 und 31607 (= die größte Primzahl, die man zur Faktorisierung von Zahlen in der Nähe von 109 als Teiler testen muss). Dieses Array hat 3400 Elemente und belegt somit genau 13600 Bytes Speicherplatz (32-Bit-Integer). Damit kommen neuere Grafik-Taschenrechner klar.
Anschließend kannst Du eine Routine schreiben, die mit Hilfe des vorberechneten Arrays den kleinsteen Primfaktor jeder Zahl 9 bestimmt („rohe“ Routine ohne Bereichsprüfungen etc.):
FUNCTION LowestFactor (n\_: LONGINT): LONGINT;
VAR
i : INTEGER;
t : LONGINT;
s : LONGINT;
Result: LONGINT;
begin
Result := n\_;
IF ((n\_ MOD 2)=0) THEN
begin
Result := 2
end
ELSE
begin
s := round(sqrt(n\_));
FOR i := 0 TO PNCOUNT-1 DO
begin
t := PrimeNumber[i];
IF (t\>s) THEN
begin
Break
end;
IF ((n\_ MOD t)=0) THEN
begin
Result := t;
Break
end
end
end
end;
Zuerst wird der Kandidat n_ auf „gerade Zahl“ geprüft. Ist n_ gerade, wird die Routine mit dem Ergebnis 2 verlassen. Ist n_ ungerade, werden alle Primzahlen beginnend mit 3, 5, 7, 11, … aus der Tabelle gelesen und als Teiler getestet. Abgebrochen wird, wenn eine Probedivision aufgeht („n MOD t = 0“; dann wird dieses t als Ergebnis zurückgeliefert), oder die Teiler √n übersteigen („t>s“).
Das ist schon alles. Die Berechnung des PrimeNumber-Arrays selbst erfordert übrigens genau 146801 Modulo-Operationen. Ein PC erledigt das mit links; was ein TR dazu sagt, weiß ich allerdings nicht.
Unten hab ich das ganze Programm angehängt (zum Studieren und Experimentieren, nicht zum Abkopieren).
Gruß
Martin
–––––––––––––––––––––––––––––––––––––––––––
PROGRAM LowFac;
CONST
PNCOUNT = 3400;
VAR
PrimeNumber: ARRAY[0..PNCOUNT-1] OF LONGINT;
(\* Speicherplatzbedarf von PrimeNumber \*)
(\* = 4\*PNARRAYSIZE = 13600 Bytes \*)
ModCount: LONGINT;
(\* =========================================== \*)
FUNCTION LowestFactor (n\_: LONGINT): LONGINT;
(\* Argument Ergebnis \*)
(\* ------------------------------ \*)
(\* = 0 0 \*)
(\* = 1 1 \*)
(\* = 2...10^9 der kleinste Prim- \*)
(\* faktor von n\_ \*)
(\* sonst -1 \*)
VAR
i : INTEGER;
t : LONGINT;
s : LONGINT;
Result: LONGINT;
begin
IF (n\_\>=2) AND (n\_s) THEN
begin
Break
end;
Inc(ModCount);
IF ((n\_ MOD t)=0) THEN
begin
Result := t;
Break
end
end
end
end
ELSE
begin
Result := -1;
IF (n\_=0) THEN Result := 0;
IF (n\_=1) THEN Result := 1;
end;
LowestFactor := Result;
end;
(\* =========================================== \*)
PROCEDURE GeneratePrimeNumberArray;
VAR
i: INTEGER;
n: LONGINT;
begin
PrimeNumber[0] := 3;
i := 1;
(\* sqrt(10^9) = 31622.776... \*)
FOR n := 4 TO 31623 DO
begin
IF (LowestFactor(n)=n) THEN
begin
PrimeNumber[i] := n;
Inc(i)
end
end
end;
(\* =========================================== \*)
PROCEDURE PerformTest;
CONST
TESTCOUNT = 22;
TEST:
ARRAY[0..TESTCOUNT-1] OF LONGINT
= (100, 200, 500,
1000, 2000, 5000,
10000, 20000, 50000,
100000, 200000, 500000,
1000000, 2000000, 5000000,
10000000, 20000000, 50000000,
100000000, 200000000, 500000000,
1000000000);
VAR
f: TEXT;
c: INTEGER;
n: LONGINT;
l: LONGINT;
s: STRING;
m: LONGINT;
begin
Assign(f, 'FACTEST.TXT');
ReWrite(f);
WriteLn(f, ModCount, ' Mod Ops');
WriteLn(f, '');
m := 0;
FOR c := 0 TO TESTCOUNT-1 DO
begin
FOR n := TEST[c]-100 TO TEST[c]+100 DO
begin
ModCount := 0;
l := LowestFactor(n);
m := m+ModCount;
WriteLn(f, 'n = ', n,
' ',
'l = ', l,
' ',
'(', ModCount, ' Mod Ops)');
end
end;
WriteLn(f, '');
WriteLn(f, m, ' Mod Ops total');
Close(f);
WriteLn('Output written to file FACTEST.TXT');
WriteLn('');
ReadLn;
end;
(\* =========================================== \*)
begin
ModCount := 0;
GeneratePrimeNumberArray;
PerformTest
end.
1 „Gefällt mir“
Hallo,
machst du nicht einen Zirkelschluss? Du generierst das Array, greifst dabei aber bereits auf die Funktion zu, die man aber erst nutzen kann, wenn das Array existiert - oder versteh ich da was falsch?
Übrigens: Sag mir bitte mal, wie man das auf dem Taschenrechner schnell (!) umsetzen soll.
Das ursprüngliche Problem war: ich muss mit dem Taschenrechner Texte mit RSA verschlüsseln und dabei M^e mod n rechnen. Nun ist e aber zum Teil im Bereich 10^3 bis 10^4, was der TR einfach nicht bewältigen kann (er rechnet zuerst die Potenz aus und danach modulo, wobei er beim Potenzieren meistens Unendlich zurückgibt, um einem Stack Overflow vorzubeugen). Ich wollte mir daher eine Funktion schreiben, die diese Berechnung schrittweise durchführt, denn
(M^1 mod n)^(e-1) mod n = M^e mod n
So kann man nun fortfahren, am Schluss erhält man den korrekten Wert, obwohl der TR das eigentlich nicht rechnen kann ^^
Ich habe das zuerst mit einer Schleife gelöst. Pseudocode:
a=M
Von 1 bis (e-1) mach a=a*M mod n
Gib a zurück
Das gibt natürlich den korrekten Wert, ist aber sehr langsam, da der TR e-mal modulo n rechnen muss. Würde man e in die Primfaktoren zerlegen und dann die einzelnen Primfaktoren abspalten, dann würde man nur so viel mal modulo rechnen, wie e Primfaktoren hat. Das ergibt dann wieder Probleme, wenn e eine Primzahl ist oder sehr grosse Primfaktoren hat. Ich belass es jetzt einfach bei der Schleife, die funktioniert wenigstens immer (wenn auch langsam)…
Eine kleine Sache hab ich aber trotzdem noch eingebaut: Ist e durch 2 teilbar, so kann ich ja die Anzahl Schleifen halbieren, da ich jeweils mit M^2 multiplizieren kann. Dasselbe könnte ich natürlich auch für die anderen Primzahlen machen, aber das ist mir zu mühsam ^^
MfG Z4ppy
Hallo,
machst du nicht einen Zirkelschluss? Du generierst das Array,
greifst dabei aber bereits auf die Funktion zu, die man aber
erst nutzen kann, wenn das Array existiert
gut erkannt. Ja, dieser Zirkel ist vorhanden, aber er funktioniert, weil zur Berechnung der Primzahlen, mit denen das PrimeNumber-Array in GeneratePrimeNumberArray gefüllt wird, zwar Elemente aus ebendiesem Array benutzt werden, jedoch nur solche, die schon berechnet wurden, nämlich die „am Anfang“ des Arrays. Beispiel: Testet die Schleife gerade 293 (ist prim), dann werden aus dem Array nur die Zahlen 3, 5, 7, 11, 13 und 17 benutzt. Der nächste Eintrag 19 wird nicht mehr benötigt, weil √293 = 17.11… Diese kleinen Zahlen sind allesamt schon längst berechnet worden. Damit das korrekt starten kann, muss lediglich das erste Array-Element – die 3 – von Hand eingetragen werden (sonst gibts nen division-by-zero-Error).
ich muss mit dem Taschenrechner
Texte mit RSA verschlüsseln und dabei M^e mod n rechnen.
Binäre Exponentiation! Ein Beispiel:
11865 = 10111001011001 (links vom „=“ dezimal, rechts davon binär)
⇒ M11865 = ((((((((((((M2)2 · M)2 · M)2 · M)2)2)2 · M)2)2 · M)2 · M)2)2)2 · M
(ohne Garantie da nicht überprüft…)
Die Berechnung von M11865 ist also mit nur 13 Quadrierungen und 7 Multiplikationen möglich! Für M11865 mod n müsstest Du nach jedem Quadrierung- und Multiplikationschritt einfach noch „mod n“ anwenden, insgesamt also nur 20 mal. Dadurch bleiben die Zwischenergebnisse während des Durchlaufens der Schleife dann immer kleiner als n.
Von diesem cleveren Verfahren wird in der Kryptographie vielfach Gebrauch gemacht. Wie es genau funktioniert, steht hier beschrieben:
http://de.wikipedia.org/wiki/Binäre_Exponentiation
So kann man nun fortfahren, am Schluss erhält man den
korrekten Wert, obwohl der TR das eigentlich nicht rechnen kann ^^
Dein TR kann mehr als Du denkst…
Gruß
Martin
Hallo,
interessant, dieses Verfahren kannte ich bisher nicht. Ich werd mir das mal genauer anschauen.
MfG Z4ppy
Hallo,
Du suchst also M^e mod n.
Zuerst ist M^e mod n dasselbe wie (M mod n)^e mod n, aber das ist Dir sicher bewusst.
In welcher Größenordnung ist denn n? Lohnt es sich, φ(n) zu bestimmen (Euler’sche Phi-Funktion)? Wenn dann noch M und n teilerfremd sind, dann ist M^φ(n) mod n = 1. Damit sparst Du Dir schon einmal viel Arbeit, weil Du nun nur noch M^(e mod φ(n)) mod n berechnen musst.
Sind M und n nicht teilerfremd, so kannst Du wenigstens M zerlegen in M=m*ggt(M,n) und auf m die obige Beziehung anwenden.
Nachzulesen ist dies übrigens unter http://de.wikipedia.org/wiki/Satz_von_Euler.
Liebe Grüße
Immo
n ist im Bereich 100 bis ~25000 - verhältnismässig klein also…
Phi(n) = (p-1)(q-1), für n=p*q
Oder irre ich mich da?
n in p und q zu faktorisieren, dürfte bei so kleinen Zahlen recht schnell möglich sein, selbst mit einem TR. Ob es sich jedoch lohnt, das alles zu machen, weiss ich nicht…
MfG Z4ppy
Hallo Z4ppy!
Ob es sich
jedoch lohnt, das alles zu machen, weiss ich nicht…
Es lohnt sich genau dann, wenn n (und damit auch phi(n)) nicht wesentlich größer als e ist. Ist n (und damit auch phi(n)) kleiner als e, dann ist e mod phi(n) ja höchstens noch halb so groß wie e, und damit ist, denke ich, schon etwas gewonnen. Ist phi(n) nur wenig größer als e, so nimmst Du einen negativen Vertreter der Restklasse von e modulo phi(n) und musst nur M^(-1) mod n bestimmen, um insgesamt weniger Rechenoperationen zu erhalten.
Liebe Grüße
Immo
Hallo Immo,
3987612345678 mod 30101 = 28962
Das hat mein PC gerade mit binärer Exponentiation ausgerechnet. Der Aufwand: 34 Ganzzahl-Multiplikationen und 34 Modulo-Operationen. Das Ergebnis erschien erwartungsgemäß instantan. Der Rechenaufwand ist sogar so gering, dass dieses Verfahren auch auf Prozessoren mit begrenzter Leistung noch ausreichend schnell ist, nämlich solchen auf Chipkarten.
Die binäre Exponentiation ist einfach zu verstehen, leicht zu implementieren und überragend effizient in Bezug auf Laufzeit und Speicherplatz. Deshalb ist sie die praktisch alternativlose Lösung für dieses Problem. Sie ähnelt übrigens dem Verfahren der sogenannten ägyptischen Multiplikation.
Das Pascal-Programm habe ich unten angehängt. Essentiell ist nur die Funktion BinExpoPower. Zum Checken der Ergebnisse (sie stimmen!) habe ich ein Applet benutzt, das ebenfalls me mod n durch schnelle Exponentiation berechnet:
http://www.math.umn.edu/~garrett/crypto/a01/FastPow…
musst nur M^(-1) mod n bestimmen, um insgesamt weniger
Rechenoperationen zu erhalten.
Weniger als 34?
Gruß
Martin
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
PROGRAM BinExpo;
VAR
OpCount: INTEGER;
(\* ================================================ \*)
FUNCTION BinExpoPower (m\_, e\_, n\_: LONGINT): LONGINT;
VAR
TwoPower: LONGINT;
u: INTEGER;
x: LONGINT;
k: INTEGER;
begin
OpCount := 0;
IF (e\_=0) THEN
begin
x := 1
end
ELSE
begin
TwoPower := $80000000; (\* = 2^31 = \*)
u := 0;
x := m\_;
FOR k := 0 TO 32-1 DO
begin
IF ((e\_ AND TwoPower)=0) THEN
begin
IF (u\>0) THEN
begin
x := x\*x;
x := x MOD n\_;
OpCount := OpCount+1
end
end
ELSE
begin
IF (u\>0) THEN
begin
x := x\*x;
x := x MOD n\_;
x := x\*m\_;
x := x MOD n\_;
OpCount := OpCount+2
end;
Inc(u)
end;
TwoPower := TwoPower SHR 1
end
end;
BinExpoPower := x
end;
(\* ================================================ \*)
PROCEDURE Calc (m\_, e\_, n\_: LONGINT);
VAR p: LONGINT;
begin
p := BinExpoPower(m\_, e\_, n\_);
Write(m\_, '^', e\_, ' mod ', n\_, ' = ', p);
Write(' ');
WriteLn('(', 'OpCount = ', OpCount, ')');
WriteLn('');
end;
(\* ================================================ \*)
PROCEDURE Main;
VAR m, e, n: LONGINT;
begin
WriteLn('Bin„re Exponentiation');
WriteLn('');
Calc(13, 8, 1000000000);
Calc(12121, 11865, 29753);
Calc(39876, 12345678, 30101);
WHILE TRUE DO
begin
Write('m = (max 40000) ');
ReadLn(m);
IF (m=0) THEN Break;
Write('e = (max 10^9) ');
ReadLn(e);
IF (e=0) THEN Break;
Write('n = (max 40000) ');
ReadLn(n);
IF (n=0) THEN Break;
Calc(m, e, n)
end
end;
(\* ================================================ \*)
begin
Main
end.
Hallo Martin!
musst nur M^(-1) mod n bestimmen, um insgesamt weniger
Rechenoperationen zu erhalten.Weniger als 34?
Da magst Du recht haben, dass mit binären Operationen das Ziel schnell erreicht ist. Ich kenne mich mit Programmieren nicht wirklich aus, deshalb kann ich jetzt nicht schnell herleiten, wie viele Operationen ich tatsächlich bräuchte. Bei e