Primality algorithms in java.math.BigInteger
While working on implementing a primality test based on Fermat's Little Theorem, I naturally came across java.math.BigInteger to mainly utilize it's method for Modular Arithmetic.
I also noticed that it has two other methods; isProbablePrime and ProbablePrime.
As such, I was wondering which methods these functions use for testing primality.
Does it use Na飗e methods, like the Sieve of Eratosthenes? Or probabilistic tests like Fermat's Little Theorem, Miller-Rabin or Solovay-Strassen primality test?
For anyone interested, it could be fun to get some feedback on my implementation which can be oogled over at: http://my.opera.com/duddev/blog/show.dml/298370
Thanks for your time, hoping for some good answers of course.
[762 byte] By [
the--duda] at [2007-10-2 22:33:14]
I skimmed through the source of the BigInteger class and found that it first uses a sieve and after that the number is checked with both the Lucas-Lehmer- and the Miller-Rabin tests.
You may want to check it yourself: in the installation folder of your JDK there should be a file called scr.zip which holds the source code of all standard Java classes.
Good luck.
I see, thanks for the info. :)
I guess there was a point in creating a Fermat's primality test then, as the built-in class does otherwise.
Did you notice if the method in BigInteger uses a pre-set of primes to feed the sieve, or does it start from 1? Would be quite a waste to start all from the smallest primes, wouldn't there?
> I see, thanks for the info. :)
> ...
You're welcome.
> Did you notice if the method in BigInteger uses a
> pre-set of primes to feed the sieve, or does it start
> from 1? Would be quite a waste to start all from the
> smallest primes, wouldn't there?
Have a look at the package-private class BitSieve for details. It's in the java.math package as well.
> For anyone interested, it could be fun to get some feedback on my implementation
I've modified your code: class FermatPrime {
public static boolean doTest (BigInteger p, int prob) {
for (int c = 0; c < prob; c++) {
if (!doModPow(p)) {
return false;
}
}
return true;
}
public static boolean doModPow (BigInteger n) {
long rndnum = 1 + generator.nextInt(99);
BigInteger b = BigInteger.valueOf(rndnum);
return b.modPow((n.subtract(n.ONE)), n).equals(n.ONE);
}
}
Of the four changes I've made, one fixes a bug and three clean up the implementation. I've left the distribution of rndnum alone, but I do think that it's somewhat imperfect. Firstly, if rndnum happens to be 1 the test is absolutely pointless; secondly, the range is rather small. If you are going to have such a small range, you should take steps to ensure that you don't use the same number in multiple tests.
Cheers mate. I'm still learning java you see, so it's nice of you to point of some things.
I changed the class to basically match your suggestions.
I do share your concern regarding the range of rndnum, which was something I thought about. I did however go for a rather small range, quite simply because of concerns with execution time. Obviously the base number of a modular exponation like this will have quite an effect on the execution time, so therefor I let it be in a small range. People could always just change the value if they were to get concerned about concistency of the method.
Anyhow, you'd need to work with some pretty big primes if this were to produce a substantial number of Fermat liars. And at that rate you might as well use Miller-Rabin, Solovay-Strassen, or something else like isProbablePrime. :)
But thanks for all the help! Appreciate it, as I said...
Assuming naive multiplication (i.e. multiplying two n-bit numbers is O(n^2)), the modular exponentation (x-1)^a (mod x) where x is an n-bit number is O(n^2 lg a), so you can probably afford to increase a. (Of course, if this is a real-world application then profiling to select a suitable value is the way forward).
