Hallo,
ich habe mir heute ein bißchen den Tag damit vertrieben den Miller Rabin Test zu implementieren. Nun nachdem das Programm läuft stehe ich allerdings vor dem Problem das beim Durchlauf von der Zahlen von 10 bis 100 nicht alle Primzahlen gefunden werden.
Soweit ich das im moment überblicken kann entspricht meine Impelementierung der Dokumentation (am Ende der Wiki-Seite als PDF). Allerdings scheint das Programm noch aus irgendwelchen Gründen einige Zahlen nicht als Primzahlen identifizieren zu können, wobei ich im moment am ehesten die Zufallszahlsgenerator im Verdacht habe. Aber vielleicht kann ja mal jemand über den Quellcode herüber schauen und hat den einen oder anderen Tipp für mich, ich wäre über einen Kleinen Hinweis warum es nicht so wirklich funktioniert auf jeden Fall sehr dankbar.
Viele Grüsse
Dan
PS
Ach ja ich sollte evtl. den Quellcode auch anfügen :-D Meine Main-Methode schaut im moment so aus:
und das eigentlich Programm so, wobei ich bereis die methoden dec2bin, bin2dec und modular_exp überprüft habe, diese sollten also fehlerfrei funktionieren.
Edit
Nachtrag im moment schaut die Ausgabe so aus:
ich habe mir heute ein bißchen den Tag damit vertrieben den Miller Rabin Test zu implementieren. Nun nachdem das Programm läuft stehe ich allerdings vor dem Problem das beim Durchlauf von der Zahlen von 10 bis 100 nicht alle Primzahlen gefunden werden.
Soweit ich das im moment überblicken kann entspricht meine Impelementierung der Dokumentation (am Ende der Wiki-Seite als PDF). Allerdings scheint das Programm noch aus irgendwelchen Gründen einige Zahlen nicht als Primzahlen identifizieren zu können, wobei ich im moment am ehesten die Zufallszahlsgenerator im Verdacht habe. Aber vielleicht kann ja mal jemand über den Quellcode herüber schauen und hat den einen oder anderen Tipp für mich, ich wäre über einen Kleinen Hinweis warum es nicht so wirklich funktioniert auf jeden Fall sehr dankbar.
Viele Grüsse
Dan
PS
Ach ja ich sollte evtl. den Quellcode auch anfügen :-D Meine Main-Methode schaut im moment so aus:
Code:
public class Aufruf
{
public static void main(String args[])
{
int s=200;
//long n=33679;
for(long n=10; n<100; n++)
{
double prozent=Math.pow(0.5, (double)s)*100;
MillerRabin mr=new MillerRabin();
if(mr.test(n, s)==true)
{
System.out.println(n+" ist zu "+prozent+"% eine Primzahl");
}
else
{
// System.out.println(n+" ist keine Primzahl");
}
}
}
}
und das eigentlich Programm so, wobei ich bereis die methoden dec2bin, bin2dec und modular_exp überprüft habe, diese sollten also fehlerfrei funktionieren.
Code:
import java.util.*;
public class MillerRabin
{
public boolean test(long n, int s)
{
long a=2;
Random r = new Random();
for(int i=1; i<=s; i++)
{
a=(long)r.nextInt((int)n-2)+2;
if(witness(n, a)==true)
{
return false; // Die Zahl n ist zu 100% nicht prim
}
}
return true; // Die Zahl n ist zu ((1/2)^s*100)% prim
}
// Überprüft ob a ein Zeuge (= Teiler) für die Zahl n ist
private boolean witness(double n, double a)
{
String u_bin=""; // Zahl n in binärdarstellung
double u_dec=0;
int t=0; // Anzahl der "abschließenden" Nullen
double x0=0;
double x1=0;
// Falls n gerade ist
if(n%2==0)
{
return true;
}
else
{
u_bin=dec2bin(n-1);
// Zählen der Nullen von rechts nach links bis zur ersten Eins
for(int i=u_bin.length()-1; i>0 && u_bin.charAt(i)!='1'; i--)
{
t++;
}
// Abtrennen der letzten Nullen
u_bin=u_bin.substring(0, u_bin.length()-t);
// Umrechnen von U in der Binärdarstellung in die Dezimaldarstellung
u_dec=this.bin2dec(u_bin);
// Berechnen von a^u mod n
x0=modular_exp(a, u_dec, n);
for(int i=1; i<=t; i++)
{
x1=(x0*x0)%n;
if(x1==1 && x0 != 1 && x0 != (n-1))
{
return true;
}
x0=x1;
}
if(x0!=1)
{
return true;
}
else
{
return false;
}
}
}
// Umrechnung von der Dezimal in die Binärdarstellung
private String dec2bin(double eingabe)
{
String ausgabe="";
while(eingabe!=0)
{
if(eingabe%2==1)
{
eingabe--;
ausgabe="1"+ausgabe;
}
else
{
ausgabe="0"+ausgabe;
}
eingabe=eingabe/2;
}
return ausgabe;
}
// Umrechnen von der Binär- in Dezimaldarstellung
private double bin2dec(String eingabe)
{
double ausgabe=0;
double powerOfTwo=1;
for(int i=eingabe.length()-1; i>=0; i--)
{
if(eingabe.charAt(i)=='1')
{
ausgabe=ausgabe+powerOfTwo;
}
powerOfTwo=powerOfTwo*2;
}
return ausgabe;
}
// Berechnet (a^u) mod n
private double modular_exp(double a, double u, double n)
{
double ergebnis=1;
if(a > 0 && u==0)
{
return 1;
}
while(u>0)
{
if(u%2==0)
{
u=u/2;
a=a*a;
}
else
{
u--;
ergebnis=ergebnis*a;
}
}
ergebnis=ergebnis%n;
return ergebnis;
}
}
Edit
Nachtrag im moment schaut die Ausgabe so aus:
Code:
11 ist zu 6.223015277861142E-59% eine Primzahl
13 ist zu 6.223015277861142E-59% eine Primzahl
17 ist zu 6.223015277861142E-59% eine Primzahl
19 ist zu 6.223015277861142E-59% eine Primzahl
23 ist zu 6.223015277861142E-59% eine Primzahl
29 ist zu 6.223015277861142E-59% eine Primzahl
37 ist zu 6.223015277861142E-59% eine Primzahl
41 ist zu 6.223015277861142E-59% eine Primzahl
97 ist zu 6.223015277861142E-59% eine Primzahl