AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Miller-Rabin primzahltest

Ein Thema von qwertz543221 · begonnen am 16. Jun 2009 · letzter Beitrag vom 17. Jun 2009
 
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
44.555 Beiträge
 
Delphi 12 Athens
 
#4

Re: Miller-Rabin primzahltest

  Alt 17. Jun 2009, 00:28
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
Ein Therapeut entspricht 1024 Gigapeut.
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 21:29 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz