Miller Rabin Test Primzahlen werden teilweise nicht gefunden

Status
Nicht offen für weitere Antworten.

hawkeye78

Bekanntes Mitglied
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:
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
 

setsuna9

Mitglied
Hallo,

eine schöne Aufgabe, endlich mal was mathematisches.
Potenzregel hast du nicht richtig angewandt. Ich habe es einfach iterativ gemacht und bei jedem Schritt den Restwert rausgezogen:

Code:
private double modular_exp2(double a, double u, double n) {
	double ergebnis = 1;

	if (a > 0 && u == 0) {
		return 1;
	}

	while (u > 0) {
		u--;
		ergebnis = (ergebnis * a) % n;
	}
	return ergebnis;
}

BTW: überall im code könntest du double durch long ersetzen
 

hawkeye78

Bekanntes Mitglied
Guten Morgen,

eigenltich hatte ich das Projekt gestern Vormittag gestartet weil ich endlich einen brauchbaren Algorithmus zum Test von Primzahlen in meinem wiki haben wollte. Aber nachdem sich das über den halben Tag und den gesamten Abend hinstreckte bin ich was solche Aufgaben betrifft eher gespaltener Meinung ob das so ein schönes Projekt ist :)

Was die implementierung selbst betrifft hatte ich mich nach dieser Dokumentation gerichtet und dort steht (Seite 7 ff) das im ersten Schritt a^t mod n berechnet werden soll (mit a=Zufallszahl, t=Anzahl der Nullen, n=zu prüfende Zahl), und genau das macht eigentlich modular_exp, wobei ich glaube das es nicht korrekt ist, wenn du in jedem Schritt eine Modulo-Division durchführtst. Ich bin mir zwar nicht ganz sicher aber ich glaube mit meiner Methode und dem Verfahren des sukzessiven Potenzieren erhalte ich auch noch einen (minimalen) Performences zugewinn.

Um abschließend noch einmal auf die Ausgangsfrage dieses Threads zurück zu kommen, ich habe mittlerweile den Fehler gefunden und es lag einfach daran das ich bei jedem Aufruf den Zufallsgenerator neu initialisert habe und damit keine verwendetbaren Zufallszahlen erhalten habe. Ich habe das ganze mit den Zahlen von 3 bis 300 getestet und dort findet er offenbar alle Primzahlen. Allerdings stehe ich noch vor dem Problem das das Programm mit einem Speicher überlauf gegen die Wand läuft wenn die Zahlen zugroß (~10.000) werden.
Viele Grüsse
Dan
 

setsuna9

Mitglied
ach ja...
dein algorithmus stimmt ja bei näherer Betrachtung (Schande über mich)

was ich eigentlich gemacht habe: alle double in long geändert (wegen der Genauigkeit des doubles auf 15 Stellen), dadurch musste ich dein modular_exp.
Was ich implementiert habe, stimmt dennoch, da:

Code:
a = xn + r
a^2 = (xn)^2 + 2xnr + r^2 = mn + r^2  mod n = r^2 
r^2 = yn + s mod n = s
a^2 - s ist immer durch n teilbar, daher multipliziere a mit s usw.

Die Sache mit dem Random kapier ich nicht, auch wenn dein Code in
Code:
Random r = new Random(new java.util.Date().getTime());
ändere, fehlen mir etliche Primzahlen.
 

hawkeye78

Bekanntes Mitglied
ach ja...
dein algorithmus stimmt ja bei näherer Betrachtung (Schande über mich)

ist ja nix passiert :) und ja du hast recht das würde auch so klappen. Was den Zufalls generator betrifft steht dieser nun ausserhalb der Methoden d.h. bei mir schaut der QUellcode im moment so aus:

Code:
public class MillerRabin
{
Random r= new Random();
   public boolean test(long n, int s) {}
private boolean witness(double n, double a) {}
private double bin2dec(String eingabe) {}
private double modular_exp(double a, double u, double n) {}
}

und damit findet er (zumindestens bei mir) alle Primzahlen. Ansonsten habe ich gerade (nach einem Blick in die Doku) auch den WEchsel von double nach long vollzogen, aber leider bleibt das Problem das ich bei großen Zahlen gegen die Wand laufe weiterhin bestehen, es gibt eigentlich irgendetwas was größer als long ist?
 

0x7F800000

Top Contributor
Mit BigInteger kannst du locker durch beliebig dicke wände laufen, hauptsache die sind nicht so dick wie der gesamte RAM deines Rechners... da ist auch schon eine methode powMod() [oder so ähnlich] implementiert ;) damit kannst du schnell a^u mon n ausrechnen [edit: wenn du glück hast, ist die methode vllt sogar nativ, und sonstwo im rasend schnellen assembler implementiert, aber ich weiss es nicht müsste guggen]
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
Zrebna Frage zu Test-Driven Development (TDD) Java Basics - Anfänger-Themen 3
W junit.Test not accessible? Java Basics - Anfänger-Themen 4
W Junit-Test (Java) Java Basics - Anfänger-Themen 4
W Testfälle bei Java ( Junit-Test) Java Basics - Anfänger-Themen 3
D Hilfe bei Calculator Test Java Basics - Anfänger-Themen 15
U jUnit 5 Test für eine addMethode Java Basics - Anfänger-Themen 18
M Test auf Exceptions schreiben Java Basics - Anfänger-Themen 11
P Eclipse Karate Framework API Test . Unexpected Error: the trustAnchors parameter must be non-empty Java Basics - Anfänger-Themen 1
I Variable innerhalb Methode: Local variable test defined in an enclosing scope must be final or effectively final Java Basics - Anfänger-Themen 3
A Junit Test für MysqlDataSource JDBC Java Basics - Anfänger-Themen 3
A Test Junit Java Basics - Anfänger-Themen 1
H Junit test Java Basics - Anfänger-Themen 12
P JUnitTest Best Practise (Ein Assert pro Test?) Java Basics - Anfänger-Themen 10
P Methoden JUnit 4 - Test Java Basics - Anfänger-Themen 6
Mr_Kleeblatt Operatoren if (arri[i] != "test.java"&& arri[i] != "test.class") Java Basics - Anfänger-Themen 3
N Fehler bei JUnit Test Java Basics - Anfänger-Themen 5
L Test-Methoden schreiben Java Basics - Anfänger-Themen 13
D Test auf Dopplungen Java Basics - Anfänger-Themen 32
neerual Klassen Wie rufe ich Klassen, die andere Klassen extenden in einer Test Unit auf? Java Basics - Anfänger-Themen 10
B JUnit Test erstellen Java Basics - Anfänger-Themen 6
B zzz.test Java Basics - Anfänger-Themen 13
W Problem bei JUnit Test Aufgabe Java Basics - Anfänger-Themen 15
W JUnit Test und HashCode Java Basics - Anfänger-Themen 14
C Erste Schritte Hexidezimal-Test Java Basics - Anfänger-Themen 2
A Kfz - Händler Klasse. JUnit-Test gibt noch Fehler an, aber finde Ursache nicht Java Basics - Anfänger-Themen 7
B Palindrom Test mit Junit Java Basics - Anfänger-Themen 23
T Minesweeper Test Java Basics - Anfänger-Themen 2
S Junit Test Java Basics - Anfänger-Themen 2
F Test Java Basics - Anfänger-Themen 12
W Ist das ein legitimer Test? Java Basics - Anfänger-Themen 5
shiroX Methoden JUnit-Test einer void-Methode Java Basics - Anfänger-Themen 4
U Best Practice Datenbereitstellung Unit Test Java Basics - Anfänger-Themen 6
B Binäre Suche - Junit Test Java Basics - Anfänger-Themen 6
B Datentypen Test float und double speichern Zahlen nur ungefähr Java Basics - Anfänger-Themen 4
Z Vererbung Test auf Normalverteilung, Wilcoxon Java Basics - Anfänger-Themen 3
M Assertion NotNull Test Java Basics - Anfänger-Themen 3
S Separate Funktion für JUnit-Test Java Basics - Anfänger-Themen 3
W Test, ob Datei existiert, schlägt fehl Java Basics - Anfänger-Themen 4
T JUnit test failed Java Basics - Anfänger-Themen 3
H Array Test Methode schreiben Java Basics - Anfänger-Themen 3
R JUnit Test mit einer Dateistruktur als Testparameter Java Basics - Anfänger-Themen 3
V Bruchrechner Test Java Basics - Anfänger-Themen 7
T Test läuft schief Java Basics - Anfänger-Themen 3
shiroX OOP Array kleinste Zahl mit jUnit test Java Basics - Anfänger-Themen 3
G mache aus Test nach sortieren estt oder java aajv Java Basics - Anfänger-Themen 5
S Code stimmt nicht für vorgegebenen JUnit-Test Java Basics - Anfänger-Themen 2
x22 Java Multiple Choice Test Java Basics - Anfänger-Themen 8
R JUnit Test mit mehrfach ausgeführt Java Basics - Anfänger-Themen 6
B JUnit - Mini-Test Java Basics - Anfänger-Themen 9
T Unterschied zwischen Integrationstest und JUnit test? Java Basics - Anfänger-Themen 12
N Test mit assert Java Basics - Anfänger-Themen 9
Y Junit Test - Testwert ändert sich Java Basics - Anfänger-Themen 12
K Palindrom Test Java Basics - Anfänger-Themen 9
S Performance-/Stress Test für Webanwendung Java Basics - Anfänger-Themen 2
V Mediaplayer - NullPointerException bei Unit-Test Java Basics - Anfänger-Themen 4
H Ich kann mein Java Programm Test.class nicht ausführen Java Basics - Anfänger-Themen 6
H Javabefehl Test Java Basics - Anfänger-Themen 3
S Hilfe zu Java-Programm und JUnit Test!! Java Basics - Anfänger-Themen 5
T JUNit Test IOException Java Basics - Anfänger-Themen 5
H lucas-test Java Basics - Anfänger-Themen 14
P White-Box-Test Verständnisproblem Java Basics - Anfänger-Themen 11
N Methoden Test ob Server vorhanden ist Java Basics - Anfänger-Themen 4
N Test Datei = Bild Java Basics - Anfänger-Themen 5
S Erste Schritte 1. Test Programm Java Basics - Anfänger-Themen 21
Spin JUNIT Test Case - Problem bei testen Java Basics - Anfänger-Themen 2
T brauche HILFE beim Junit test:eek: Java Basics - Anfänger-Themen 11
timbeau JUnit Test Dauer speichern/loggen Java Basics - Anfänger-Themen 16
E Am Mittwoch Test und ich checks überhaupt nich Java Basics - Anfänger-Themen 27
A junit test wann verwendet man "was"? Java Basics - Anfänger-Themen 4
J JUnit Test Java Basics - Anfänger-Themen 2
D Test einer Chipkarte Java Basics - Anfänger-Themen 2
J Problem mit Test-Klasse Java Basics - Anfänger-Themen 4
E Test, ob String in Double umwandelbar ist Java Basics - Anfänger-Themen 3
J Test steht vor der Tür !! Java Basics - Anfänger-Themen 2
X Array nur mit Zahlen (test) Java Basics - Anfänger-Themen 11
Houly JUnit Test Suite anlegen Java Basics - Anfänger-Themen 6
F Primitiver Lucas-Lehmer-Test hängt sich auf Java Basics - Anfänger-Themen 7
M Erster HashMap-test Java Basics - Anfänger-Themen 5
O Test auf JComponent Java Basics - Anfänger-Themen 7
pun Junit Test erkennt Exception nicht.. Java Basics - Anfänger-Themen 14
D C0 und C1 Test nochmal Java Basics - Anfänger-Themen 9
D C0 und C1 Test Java Basics - Anfänger-Themen 3
G BlueJ jUnit Test Java Basics - Anfänger-Themen 6
J Test auf UTF-8 Java Basics - Anfänger-Themen 2
M Wo und wie speich. ich .java und wo den zugehörigen test? Java Basics - Anfänger-Themen 2
Shalimar Test, ob mehr pos. oder neg. Zahlen Java Basics - Anfänger-Themen 3
M test Java Basics - Anfänger-Themen 5
M test Java Basics - Anfänger-Themen 2
M test Java Basics - Anfänger-Themen 10
V Test mit JUnit verbinden Java Basics - Anfänger-Themen 3
M test Java Basics - Anfänger-Themen 4
C Multiple Choice Test Java Java Basics - Anfänger-Themen 5
G Grundfläche färben, ein Bild (NORTH) ind Test darunter? Java Basics - Anfänger-Themen 6
M Palindrom Test mit Char-arrays! Java Basics - Anfänger-Themen 3
M Java Test Übungsfragen Hilfe! Java Basics - Anfänger-Themen 5
B JUnit Test Klasse Rational Java Basics - Anfänger-Themen 12
N class Test<E extends MyAbstractClass> => typ von E? Java Basics - Anfänger-Themen 5
G jar cvf test.war -C src/ WEB-INF -C src/ ALLE JSP Wildcard? Java Basics - Anfänger-Themen 2
0 Quadratzahl-Test Java Basics - Anfänger-Themen 4
C Unsupported major.minor bei jUnit Test Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben