Faktorisierung von Zahlen

[CalganX]

Jede ganze Zahl, die keine Primzahl ist, lässt sich als ein Produkt von endlich vielen Primzahlen darstellen. In der Schule lernt man das unter dem Namen Primfaktorzerlegung kennen. In diesem Beitrag möchte ich ein paar Algorithmen sammeln, um eine Zahl in ihre Faktoren zu zerlegen.

Brute-Force-Methode
Die Haudrauf-Methode besteht nur daraus alle ganzen Zahlen von 2 bis n/2 zu durchlaufen und ihre Teilbarkeit zu überprüfen. Hier bei ist es nicht nötig diese Zahlen auf Primalität zu überprüfen, da die Vielfachen der Primzahlen automatisch herausfallen. Ich habe einfach mal diese Brute Force-Methode zusammengehackt:

Delphi-Quellcode:

type
  TPFactor = record
    Base: longint;
    Power: integer;
  end;
  TPFactors = array of TPFactor;

function Factorize(const n: longint): TPFactors;
var
  idx: longint;
  iCount: longint;
  iTemp: longint;
begin
  SetLength(Result, 0);
  iCount := 0;
  iTemp := n;
  idx := 2;
  while (idx <= (n div 2)) do begin
    if (iTemp mod idx = 0) then begin
      if (iCount > 0) and (Result[iCount-1].Base = idx) and (iCount <> 0) then begin
        inc(Result[iCount-1].Power);
      end else begin
        inc(iCount);
        SetLength(Result, iCount);
        Result[iCount-1].Base := idx;
        Result[iCount-1].Power := 1;
      end;
      iTemp := iTemp div idx;
    end else
      inc(idx);
  end;
end;

Zu Bemerken ist, dass diese Algorithmus relativ langsam ist und nur mit kleinen Zahlen arbeiten kann (Innerhalb der Grenzen von Longint).
Demo: http://downloads.csd-software.net/pf...ce_v01_src.zip

alzaimar hat noch eine alternative Brute-Force-Methode:

Delphi-Quellcode:

Procedure Factorize (aNumber : Integer);
Var
  p, aStop  :Integer;
  f : Boolean;

  Procedure AddFactor (aFactor : Integer);
  Begin
    While (aNumber > 1) And (aNumber mod aFactor = 0) Do Begin
      form1.memo1.lines.add (IntToStr (aFactor));
      aNumber := aNumber div aFactor;
      aStop := Trunc (Sqrt (aNumber));
      End;
  End;

Begin
  AddFactor (2);
  AddFactor (3);
  p := 5; f := True;
  aStop := Trunc (Sqrt (aNumber));
  While p <= aStop do begin
    AddFactor (p);
    if f then inc (p,2) else inc (p,4);
    f := Not f;
    End;
  If aNumber > 1 then
    AddFactor (aNumber);
End;

Pollard-Rho-Methode
Die Pollard-Rho-Methode hat den großen Vorteil, dass sie extrem schnell ist. Jedoch nur unter der Vorraussetzung, dass die gewählte Zufallszahl passend ist. Denn die ganze Methode beruht im Grunde auf Zufallszahlen. Wichtig ist, dass man vor der Faktorierung einen Primzahltest durchführt, da ansonsten sich Pollard Rho in einer Endlosschleife verfängt. Es reicht jedoch einen Test durchzuführen, der zeigt, dass n keine Primzahl ist (es gibt spezielle Tests für diese Art des Primzahltests; zum Beispiel Primzahltest nach Fermat).
Ansonsten ist noch anzumerken, dass die Pollard-Rho-Methode nur einen ganzzahligen Faktor findet und dieser nicht unbedingt prim sein muss. D.h. um eine komplette Primfaktorzerlegung zu erhalten muss dieser Algorithmus mehrmals hintereinander durchgeführt werden.

Rest (u.a. Source) Folgt...