Miller-Rabin primzahltest

[himitsu]

also irgendwie komm ich mit den ganzen Pseudocodes auch nicht klar

z.B.: http://en.wikipedia.org/wiki/Miller-...primality_test

nja, so weit bin ich grad mal "schnell" gekommen ...

Delphi-Quellcode:

Type TMillerRabinResult = (mrZusammengesetzt, mrWahrscheinlichPrimzahl);

Function MillerSelfridgeRabinTest(n, k: String): TMillerRabinResult;
  Var n1, n2, s, d, a, x, r: String;

  Begin
    n := Mathe.Normalisieren(n);
    k := Mathe.Normalisieren(k);
    Result := mrZusammengesetzt;
    If Mathe.istGerade(n) or (Mathe.Vergleich(n, '2') <= 0) Then Exit;
    n1 := n;
    Mathe.Minus1(n1);
    n2 := n1;
    Mathe.Minus1(n2);
    //write n − 1 as 2^s*d with d odd by factoring powers of 2 from n − 1
    While Mathe.Vergleich(k, '0') > 0 do Begin
      Mathe.Minus1(k);
      a := Mathe.Zufallszahl('2', n2);
      x := Mathe.PotenzModulo(a, d, n);
      If (x <> '1') and (x <> n1) Then Begin
        r := '1';
        If Mathe.Vergleich(r, s) < 0 Then
          While True do Begin
            Mathe.Plus1(r);
            x := Mathe.PotenzModulo(x, '2', n);
            If (x = '1') or (Mathe.Vergleich(r, s) >= 0) Then Exit;
            If x = n1 Then Break;
          End;
      End;
    End;
    Result := mrWahrscheinlichPrimzahl;
  End;

und beim Anderem
http://www.jjam.de/Java/Applets/Prim...ler_Rabin.html

hatte ich da erstmal aufgegeben

Delphi-Quellcode:

Function MillerSelfridgeRabinTest(n, s: String): TMillerRabinResult;
  Function Witness(a, n: String): Boolean;
    Begin
      //If Mathe.Vergleich(Mathe.Differenz(n, '1'), ) = 0 Then
      let n-1 = 2^t*u, where t>=1 and u is odd
      x[0] := modular_exponentiation(a,u,n);
      for i := 1 to t do Begin
          x[i] := x[i-1]^2 mod n
          if x[i] = 1 and x[i-1] <> 1 and x[i-1] <> n-1 then return true;
      End;
      Result := x[t] <> 1;
    End;

  Var n2: String;

  Begin
    Result := mrZusammengesetzt;
    If Mathe.istGerade(n) or Mathe.istNegativ(n) Then Exit;
    Result := mrWahrscheinlichPrimzahl;
    n2 := n;
    n2 := Mathe.Minus1(n2);
    While Mathe.Vergleich(s, '0') > 0 do Begin
      Mathe.Minus1(s);
      If Witness(Mathe.Zufallszahl('1', n2), n) Then Exit;
    End;
    Result := mrZusammengesetzt;
  End;

ich kappier bei einigen "Befehlen" einfach nicht, was die da wollen