Java Miller-Rabin-Test-Implementation

[Knobi-Wan]

Hi,

ich sitze seit einiger Zeit an einer Implementation des Miller-Rabin-Tests, sie hat jedoch noch nie funktioniert. Ich hab mir Definitionen von verschiedenen Seiten angesehen und auch einige ausprobiert, kein Ergebnis. Also frage ich hier mal nach, was ich falsch mache.

import util.LowerBoundRandom;

public class MillerRabin {

	private boolean	isProbablePrime	= true;

	public MillerRabin(final int n, final int k) { // n=possible prime, k=iterations
		final int exponent = exponentTest(n);
		final int factor = (int) ((n - 1) / (Math.pow(2, exponent)));
		int[] base = new int[k];
		baseLoop: for (int i = 0; i < k; i++) {

			// ensures that a different base is used for every iteration
			if (n > k) {
				int j = 0;
				while (j < i) {
					if (base[i] == base[j]) {
						base[i] = LowerBoundRandom.with(2, n - 1);
						j = 0;
						continue;
					}
					j++;
				}
			}
			else {
				base[i] = LowerBoundRandom.with(2, n - 1);
			}

			// actual algorithm
			if (Math.pow(base[i], factor) % n == 1 % n) {
				continue;
			}
			for (int r = 0; r < exponent; r++) {
				if (Math.pow(base[i], factor * Math.pow(2, r)) % n == (-1 - Math.floor(-1.0 / n) * n)) {
					continue baseLoop;
				}
				if (r == exponent - 1) {
					break baseLoop;
				}
			}
		}
	}

	private int exponentTest(final int n) { // computes s=max{r e N : 2^r divides (n-1)}
		for (int r = (int) Math.floor((log2(n - 1))); r > 0; r--) {
			if ((n - 1) % Math.pow(2, r) == 0) {
				return r; // exponent of biggest power of two lower or equal n-1
			}
		}
		return 0;
	}

	private int log2(final int n) {
		return (int) (Math.log(n) / Math.log(2.0));
	}

	public static void main(final String[] args) {
		MillerRabin m = new MillerRabin(15, 10);
		System.out.println(m.isProbablePrime);
	}
}

import java.util.Random;

public class LowerBoundRandom {
	public static int with(final int min, final int max) { //returns random integer including lower and upper bound
		Random random = new Random();
		return random.nextInt(max - min + 1) + min;
	}
}

n=15 ist laut des Tests eine Primzahl, doch meiner Meinung nach ist das genau der Algorithmus, der auf Wikipedia beschrieben ist, bitte belehrt mich eines Besseren.

 

[sk1mo]

Ich würde sagen deine fehler sind, dass isProbablePrime final ist und nie auf false gesetzt wird.

 

[1668mib]

Nimm's mir nicht übel, aber hab nicht gewusst, dass man mit Java so schlimmen Code fabrizieren kann...

Ist nicht viel besser, aber funktioniert wenigstens...

import java.util.HashSet;
import java.util.Set;

public class MillerRabin {
 
	public static boolean isPrime(final int n, final int k) { // n=possible prime, k=iterations
		Set<Integer> randomNumbers = new HashSet<Integer>();
		randomNumbers.add(Integer.valueOf(0));

		final int s = exponentTest(n);
		final int d = (int) ((n - 1) / (Math.pow(2, s)));
		
		
		baseLoop: for (int i = 0; i < k; i++) {
			int base = 0;
			while (randomNumbers.contains(Integer.valueOf(base))) {
				base = LowerBoundRandom.with(2, n - 1);
			}
                        randomNumbers.add(Integer.valueOf(base));
			
			int x = (int)Math.pow(base, d) % n; 
			
			// actual algorithm
			if (x == 1) {
				continue baseLoop;
			}
			for (int r = 1; r < s; r++) {
				x = (x * x) % n;
				if (x == 1) {
					return false;
				}
				if (x == n-1) {
					continue baseLoop;
				}
			}
			return false;
		}
		
		return true;
	}
 
	private static int exponentTest(final int n) { // computes s=max{r e N : 2^r divides (n-1)}
		for (int r = (int) Math.floor((log2(n - 1))); r > 0; r--) {
			if ((n - 1) % Math.pow(2, r) == 0) {
				return r; // exponent of biggest power of two lower or equal n-1
			}
		}
		return 0;
	}
 
	private static int log2(final int n) {
		return (int) (Math.log(n) / Math.log(2.0));
	}
 
	public static void main(final String[] args) {
		System.out.println(isPrime(15, 10));
		System.out.println(isPrime(17, 10));
	}
}

 

[Knobi-Wan]

@sk1mo: Daran lags nicht.

@1668mib Erklären! Ich kanns nicht ändern, wenn ich nicht weiß, was ich so alles scheiße mach.

 

[sk1mo]

Wenn ich das bei Wiki richtig überflogen habe, dann musst du in Zeile 35 den break machen.

 

[xbrtll]

Den exponentTest durch etwas ersetzen wie

public static int findExponent(int n) {
    int r = 0;
    int p = 2;
    for(int i = 1; p < n; p *= 2, i++) {
        if((n-1) % p == 0) r = i;
    }
    return r;
}

was zum einen sehr viel schneller ist und zum anderen auch garantiert korrekt. Das mit den double-Werten wird zumindest im int-Bereich wahrscheinlich auch gut gehen, muss i.A. aber keine korrekte Lösung liefern.


Mit Blick auf das, was bei wiki zu den deterministischen Varianten steht, ist die Implementierung mit Einschränkung auf int-Werte für n ohnehin nicht allzu interessant.

 

[Knobi-Wan]

@ 1668mib das funktioniert auch nicht, bei zB 7919 wird false ausgegeben.

@ xbrtll Danke dafür. Sollte ich dann statt int eher BigInteger benutzen?

 

[xbrtll]

Wenn du damit noch mehr oder minder ernsthaft was machen willst: ja. Wenn's nur eine Übung ist, ist es (relativ) egal, zumindest nach long könnte man es ja noch ohne nennenswerte Probleme ändern.

 

[1668mib]

Evtl (bzw. ziemlich sicher) ist das "return false" bei mir am Ende des baseLoops falsch... und erklären? Hab die englische Wiki-Seite zum Artikel genommen...

im Wiki stehts aber eigentlich drin...

Und eigentlich find ich das fast so noch aussagekräftiger:
(statt findExponent)

        public static int getPowersOf2(int n) {
		int result = 0;
		while (n % 2 == 0) {
			result++;
			n = n / 2;
		}
		return result;
	}

Bei 7919 reicht Integer im Übrigen eh nicht mal mehr im Ansatz... da können solche Rechnungen vorkommen: 337^3959...
selbst mein armes Matlab sagt da nur noch "Inf" dazu...

Lösen würde sich das einfach in dem man BigInteger mit modPow nutzt, oder halt ein eigenes modular power programmiert, das aber vermutlich weniger optimiert wäre...
Dann könnte man gleich weiter optimieren und BigInteger.isProbablePrime verwenden...

 

[Knobi-Wan]

jo, das Ganze war auch nur als Übung gedacht, in meinem Programm wird BigInteger.isProbablePrime benutzt.

 

[1668mib]

Naja, wenn ich anschau, was für ein Code rausgekommen ist, dann würde ich andere Dinge üben ;-)

(ok, das kann missverständlich interpretiert werden: Ich mein damit nicht, dass du das Programmieren lassen sollst oder so...)

 

[Knobi-Wan]

dann gib mir doch bitte mal einen Tipp, was ich stattdessen üben sollte.

 

[1668mib]

Wenn du deine Interessenschwerpunkte auf Java hast, dann wäre es wohl eine bessere Übung das Buch Effective Java von Joshua Bloch zu lesen, als einen nicht wirklich ganz übersichtlichen Algorithmus in einer noch weniger übersichtlichen Weise in Java nach zu implementieren... oder etwas allgemeiner das Buch Clean Code... es gibt nicht viele Menschen, die sich autodidaktisch beibringen, guten Code zu schreiben. Am meisten lernt man, wenn man sich Code anderer ansieht, vor allem guten Code...

Aber einen Algorithmus mit der Holzhammer-Methode 1:1 wie man ihn gesehen hat zum Trotz aller guten Programmierstile in Java abzubilden, das ist eigentlich keine Übung... zumindest nicht, wenn man den Anspruch hat, Programmieren bzw. die Sprache zu lernen...