A
Ich bin den Code jetzt noch ein paar mal durchgegangen, konnte aber keinen Fehler finden. Ich werde ihn mal posten, vllt. hat ja jemand Lust ihn durchzugucken. Ich bin dabei nach dem Psoudocode vorgegangen, den man hier finden kann.
Folgender Java-Code funktioniert manchmal, manchmal aber auch nicht:
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import static java.lang.Math.*;
public class PollardBrent {
public static void main(final String... args) {
System.out.println(primeFactors(3624));
}
private static List<Integer> primeFactors(final int n) {
final List<Integer> l = new ArrayList<Integer>();
search(n, l);
return l;
}
private static void search(final int n, final List<Integer> l) {
int i = n;
while (i > 1) {
if (isPrime(i)) {
l.add(i);
break;
}
int d = brent(i);
while (d == i) {
d = brent(i);
}
search(d, l);
i /= d;
}
}
private static boolean isPrime(final int n) {
if (n == 2) {
return true;
}
if (n < 2 || n % 2 == 0) {
return false;
}
final int root = (int) sqrt(n);
int j = 3;
while (j <= root) {
if (n % j == 0) {
return false;
}
j += 2;
}
return true;
}
private static int brent(final int n) {
if (n % 2 == 0) {
return 2;
}
final int bitLen = (int) ceil(log(n) / log(2));
final int c = new Random().nextInt(bitLen) + 1;
int x = c, y = c;
int g = 1, r = 1, q = 1, ys = 1;
while (g <= 1) {
x = y;
for (int i = 1; i < r; ++i) {
y = f(y, n, c);
}
for (int k = 0; k < r && g <= 1; k += c) {
ys = y;
for (int i = 1; i < min(c, r - k); ++i) {
y = f(y, n, c);
q = q * abs(x - y) % n;
}
g = gcd(q, n);
}
r *= 2;
}
if (g == n) {
do {
ys = f(ys, n, c);
g = gcd(x - ys, n);
// c = c < n ? c + 1 : 0;
} while (g <= 1);
}
return g;
}
private static int f(final int x, final int n, final int c) {
return (x * x + c) % n;
}
private static int gcd(final int a, final int b) {
return gcdHelp(abs(a), abs(b));
}
private static int gcdHelp(final int a, final int b) {
return b == 0 ? a : gcdHelp(b, a % b);
}
}
Größtes Problem ist wohl, dass ich noch immer nicht verstanden hab wie der Algo genau funktioniert. Hab aber dieses Dokument gefunden, das den Code wohl erklärt, vllt. hilft mir das den Fehler zu finden.
Die Standardvariante von Pollard hab ich mittlerweile getestet und dabei festgestellt, dass sie knapp 50% schneller ist als mein bisheriger Algo. Das ist schon mal eine gute Nachricht, auch wenns mit dem Algo von Brent noch nicht so ganz hinhaut.
