Java & JavaScript


Home
Applets
   3D:
 · Würfel
 · Würfel 2
 · Würfel 3
 · Tetraeder
 · Tetraeder 2
 · Dodekaeder
 · Ikosaeder
 · Fußball
 · Kugel
 · Kugel 2
   Fraktale:
 · Apfelmännchen
 · Apfelmännchen 2
 · Apfelmännchen 3
 · Apfelmännchen MA
 · Apfelmännchen Zoom
 · Apfelmännchen Zoom 2
 · Juliamenge
 · Juliamenge MA
 · Julia-Generator
 · Koch-Kurve
 · Koch-Kurve 2
 · Hilbert-Kurve
 · Sierpinski-Dreieck
 · Sierpinski-Dreieck 2
 · Sierpinski-Dreieck 3
 · Sierpinski-Teppich
 · Pythagoras-Baum
 · Lindenmayer-System
 · Lindenmayer-System 2
   Mathematik:
 · Funktionsplotter
 · Eratosthenes-Sieb
 · Miller-Rabin-Test
   Verschiedenes:
 · Morsezeichen-Ticker
 · Analoguhr
Scripts
Gäste
Kontakt



Crandall/Pomerance: Prime Numbers. A Computational Perspective
- Anzeige -


- Applets : Mathematik : Miller-Rabin-Test -


Ein probabilistischer Primzahlen-Test nach Miller-Rabin als Java-Applet.

Dieser Primzahlen-Test ermöglicht die Berechnung von Primzahlen in einer Größenordnung bis zu 10^1000 innerhalb weniger Momente. Darüber hinaus nimmt die Rechenzeit jedoch deutlich zu. (Siehe Test-Ergebnisse)

Während aber diejenigen Zahlen, die durch diesen Test durchfallen, definitiv nicht prim sind, kann für die gefundenen Primzahlen nur eine Wahrscheinlichkeitssausage getroffen werden. Sie sind deshalb auch nur "pseudoprim".
Die Fehlerwahrscheinlichkeit ist jedoch bei hinreichender Wiederholung des Tests wesentlich kleiner als zum Beispiel die eines Programmierfehlers meinerseits, eines Ablesefehlers Ihrerseits oder eines Fehlers im Betriebssystem des Computers, auf dem dieses Programm läuft.


[Primzahlen-Test nach Miller-Rabin als Java-Applet zum Download. Das Miller-Rabin-Applet kann die Primzahlen allerdings nur mit aktiviertem Java testen !]


Hinweise zur Benutzung

Eingegeben werden können Zahlen entweder in ausgeschriebener Form oder in der Form a*b^c+-d.
Zum Beispiel 4503599627370449 oder 3*2^5+5 oder 2^127-1.

Die Anzahl der "Zeugen" (W) bestimmt die maximale Fehlerwahrscheinlichkeit.
20 Zeugen bedeutet etwa, dass für eine gefundene Primzahl die Wahrscheinlichkeit, dass sie doch zusammengesetzt ist, kleiner als 1/4^20 (~ 10^-14) ist. Das heißt, bei 100.000.000.000.000 Tests (mit jeweils 20 Zeugen) wird einmal eine Zahl als prim deklariert, obwohl sie es nicht ist. Vernünftig sind Angaben zwischen 10 und 30.

Bei einer Dauersuche oder bei sehr großen Zahlen empfiehlt es sich, zunächst eine Probedivision durch die ersten (hier maximal 5000) Primzahlen durchzuführen. Das Miller-Rabin-Verfahren ist für zusammengesetzte Zahlen mit kleinen Primfaktoren nämlich deutlich langsamer als einfache Sieb-Methoden. Dass etwa 10^1000000+11 nicht prim ist, sehen Sie schon mit bloßem Auge (Quersumme durch 3 teilbar), der Miller-Rabin-Test würde viele Tage für diese Antwort brauchen!

Das Abbrechen des Tests wird erst nach der Befragung eines Zeugen wirksam. Die ständige Abfrage innerhalb einer Zeugenbefragung würde das Programm nur unnötig verlangsamen.


Einige Test-Ergebnisse zur Einschätzung der ungefähren Rechendauer (für 10 Zeugen bei 900 MHz):

10^100+267 (0 Sekunden)
10^200+357 (1 Sekunde)
10^500+961 (5 Sekunden)
10^1000+453 (31 Sekunden)
10^1500+2329 (1:40 Minuten)
10^2000+4561 (3:52 Minuten)
10^2500+11859 (7:32 Minuten)
10^5000+12123 (1:02 Stunden)
10^7000+4981 (2:41 Stunden)
10^11000+11973 (10:19 Stunden)

(Wobei die meiste Zeit natürlich dabei vergeht, diese Zahlen erst einmal zu finden.)


Mathematische Grundlage

Basis des Miller-Rabin-Verfahrens ist der kleine Satz von Fermat:

Sei n eine Primzahl, dann gilt  an-1 ≡ 1 (mod n)  für alle a aus [1,n-1].

Ein einfacher Test für eine natürliche Zahl n besteht nun darin, zufällige a aus [1,n-1] auszuwählen und zu prüfen, ob die Kongruenz gilt. Leider gibt es jedoch Zahlen, die diesen Test für jedes a unbeschadet überstehen (z.B. 561), die sogennanten Carmichael-Zahlen.

Gary Miller entwickelte nun 1976 einen Test, der das Problem mit den Carmichael-Zahlen umging, jedoch auf Kosten der Benutzung der (noch unbewiesenen) Riemann-Hypothese. Michael Rabin gelang es dann 1980 auch dieses Manko zu beheben und den Test auf eine sichere mathematische Basis zu stellen.
Der entscheidene Satz für den Miller-Rabin-Test ist folgender:

Sei n eine Primzahl und  n-1 = 2t·u  mit ungeradem u, dann gilt für alle a ≤ n-1

entweder  au ≡ 1 (mod n)
oder      a2i·u ≡ -1 (mod n)  für ein i aus [0,t-1].

Der Primzahlen-Test besteht nun darin, zu der zu prüfenden Zahl n eine teilerfremde Zahl a zu finden, die keine der beiden Aussagen erfüllt. Dies würde die Nicht-Primalität von n definitiv bestätigen.
Da mehr als 3/4 der Zahlen aus [2,n-1] dies tun, ist die Wahrscheinlichkeit, bei einem einmaligen Versuch, keinen dieser "Zeugen" gegen die Primalität von n zu finden, kleiner als 1/4.


Das Verfahren lässt sich programmtechnisch so umsetzen:

Miller-Rabin Pseudo-Code

function miller_rabin (n,s) {
    for i := 1 to s do {
        a := random(1,n-1);
        if (witness(a,n) then return composite;
    }
    return prime;
}

function witness(a,n) {
    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 {
        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;
    }
    if x[t] <> 1 then return true;
    else return false;
}

function modular_exponentiation(a,b,n) {
    c := 0;
    d := 1;
    let {b[k],b[k-1],...,b[0]} be the binary representation of b
    for i := k downto 0 do {
        c := 2*c;
        d := (d*d) mod n;
        if b[i] = 1 then {
            c := c+1;
            d := (d*a) mod n;
        }
    }
    return d;
}

Diesen Pseudo-Code habe ich der Seite http://highered.mcgraw-hill.com/.../algorithm_pseudocode.html entnommen und folgendermaßen in obigem Java-Applet implementiert:


Miller_Rabin.java
(Kurzform)

import java.awt.*;
import java.applet.*;
import java.math.BigInteger;
import java.util.Random;

public class MillerRabin extends Applet {

    int w; // Zeugen

    public void init() {
        // Eingabe: eine natürliche ungerade Zahl größer 2
        BigInteger N = new BigInteger("4503599627370449");
        w = 10;
        miller_rabin(N,w);
    }

    // Häufig benötigte Werte
    BigInteger Big0 = BigInteger.valueOf(0);
    BigInteger Big1 = BigInteger.valueOf(1);
    BigInteger Big2 = BigInteger.valueOf(2);

    public void miller_rabin(BigInteger N, int s) {

        BigInteger R, N_2 = N.subtract(Big2);
        boolean prime = true;

        for (w=1;w<s+1;w++) {
            R = random(N_2);
            if (witness(R,N)) {
                prime = false;
                break;
            }
        }

        if (prime) System.out.println(N.toString()+" ist eine Primzahl !");
        else System.out.println(N.toString()+" ist keine Primzahl !");
    }


    Random seed = new Random();

    public BigInteger random(BigInteger N_2) {

        BigInteger R;

        // Zufallszahl aus [1,N-1]
        do {R = new BigInteger(N_2.bitLength(),seed).add(Big1);}
        while (R.compareTo(N_2)>0);

        return R;
    }


    String bin;

    public String bigIntToBinaryString(BigInteger B) {

         // Eingabe in binäre Form umwandeln
        for (BigInteger I=Big2.pow(B.bitLength()-1);I.compareTo(Big0)!=0;I=I.divide(Big2)) {
            if (B.compareTo(I)>=0) {
                bin += "1";
                B = B.subtract(I);
            }
            else bin += "0";
        }

        return bin;
    }


    public BigInteger modular_exponentiation(BigInteger A, BigInteger U, BigInteger N) {

        BigInteger C = Big0;
        BigInteger D = Big1;

        // Sei {b[0],b[1],...,b[k-1],b[k]} die binäre Darstellung von b
        if (w==1) bin = bigIntToBinaryString(U);
        // Da für alle Zeugen gleich, nur einmal berechnen

        for (int i=0;i<bin.length();i++) {

            C = C.multiply(Big2);
            D = D.pow(2).mod(N);

            if (bin.charAt(i)=='1') {
                C = C.add(Big1);
                D = D.multiply(A).mod(N);
            }
        }

        return D;
    }


    int t;

    public boolean witness(BigInteger A, BigInteger N) {

        BigInteger N_1 = N.subtract(Big1);

        // Sei n-1 = 2^t*u mit t >= 1 und u ungerade
        if (w==1) while(N_1.divide(Big2.pow(t)).mod(Big2).compareTo(Big0)==0) t++;
        // Da für alle Zeugen gleich, nur einmal berechnen

        BigInteger U = N_1.divide(Big2.pow(t));

        BigInteger x0;
        BigInteger x1 = modular_exponentiation(A,U,N); // A^U mod N

        for (int i=1;i<t+1;i++) {
            x0 = x1;
            x1 = x0.pow(2).mod(N);
            if (x1.compareTo(Big1)==0 && x0.compareTo(Big1)!=0 && x0.compareTo(N_1)!=0)
                return true;
        }
        if (x1.compareTo(Big1)!=0) return true;
        else return false;
    }
}

Statt mit modular_exponentiation(A,U,N), kann der Startwert x0 für die for-Schleife in der Funktion witness(), auch mit der Java-eigenen Methode modPow() bestimmt werden (und zwar deutlich schneller !):

BigInteger x1 = A.modPow(U,N);


Nicht unerwähnt bleiben soll, dass Java in der Klasse BigInteger mit isProbablePrime() eine spezielle Methode zur Primzahlen-Bestimmung besitzt, die auf der Miller-Rabin-Methode beruhen soll. (Eine ausdrückliche Aussage dazu habe ich allerdings nicht gefunden.)


Weiterführende Informationen

http://home.arcor.de/alex.79/uni%20stuff/Rabin-Miller%20Test.pdf
http://www.bitnuts.de/rienhardt/docs/miller_rabin.pdf



Gary Miller  Michael O. Rabin

(Gary L. Miller und Michael O. Rabin)


Download  Miller_Rabin.zip (ca. 9 kb)




© 2001-2004 Albert Kluge - Alle Rechte vorbehalten
Impressum | Datenschutz | Nutzung | eMail