000
16.01.2003, 23:59 Uhr
NemoEimi
|
Hi allerseits,
folgender
| C++: |
import java.math.*;
import java.util.*;
public class prime {
public static Random rand = new Random(1000000);
public static boolean milRab_one(BigInteger a, BigInteger q, BigInteger p, int t) {
if (a.modPow(q,p).equals(BigInteger.ONE)) return(true);
BigInteger pminusone = p.subtract(BigInteger.ONE);
for (int i = 0; i < t; i++) {
BigInteger erg = a.modPow(q.shiftLeft(i),p);
if (p.subtract(erg).equals(BigInteger.ONE)) return(true);
}
return(false);
}
public static boolean rabinMillerTest(int n, BigInteger p) {
if (!p.testBit(0)) return(false);
BigInteger q = p.subtract(BigInteger.ONE); int t = 0;
while (!q.testBit(0)) {
q = q.shiftRight(1); t = t + 1;
}
for (int i = 0; i < n; i++) {
int testval = rand.nextInt();
BigInteger a = new BigInteger(Integer.toString(testval+10));
if (!milRab_one(a,q,p,t)) return(false);
}
return(true);
}
public static void main(String[] argv) {
BigInteger test = new BigInteger("289460255901261578317337752985016270188759871669263349671");
System.out.println(test.toString());
if (test.isProbablePrime(50))
System.out.println("Das ist eine Primzahl, sagt Java");
else
System.out.println("Das ist keine Primzahl, sagt Java");
if (rabinMillerTest(50,test)) System.out.println("Aber sie besteht fünfzig Wiederholungen Rabin-Miller!");
}
}
|
sagt auf meiner Maschine, daß test keine "probable prime" sei, während meine eigene Implementation des Rabin-Miller-Testes (also die Funktion rabinMillerTest ) diese Zahl anstandslos passieren läßt. Verwendete VM ist Hotspot, build 1.3.1-b24 .
Es gibt nun drei Möglichkeiten:
- meine Rabin-Miller-Implementation ist fehlerhaft (sehe aber keinen Fehler)
- der probabilistische Primzahltest der Java-Standardbibliothek hat einen Bug
- meine spezielle Maschine hat irgendwelche Probleme
Falls jemand hier also entweder einen Fehler in diesem Programm findet oder das beschriebene Verhalten reproduzieren kann oder etwas anderes sieht, wäre ich dankbar für entsprechende Antworten  .
Grüße,
NemoEimi
Dieser Post wurde am 17.01.2003 um 00:01 Uhr von NemoEimi editiert. |
) erklären was der Rabin-Miller Test macht?