BigInteger in Java has constructor that generates prime numbers, I cant find any mention of what algorithm is used in this. Is there a name of algorithm or maybe a book where this algorithm described?
Asked
Active
Viewed 332 times
1
-
I looked in source code, there is no mention of algorithm source or name either – Akiles May 22 '15 at 08:58
-
1See http://stackoverflow.com/questions/8744085/difference-between-biginteger-probableprime-and-other-primality-algorithms – Jean-Baptiste Yunès May 22 '15 at 09:02
-
Give a look at http://stackoverflow.com/questions/8744085/difference-between-biginteger-probableprime-and-other-primality-algorithms. – Linuslabo May 22 '15 at 09:02
2 Answers
1
It is recommended that the probablePrime method be used in preference to this constructor unless there is a compelling need to specify a certainty. - from Java 7 BigInteger API docs
Having said that. BigInteger's probable prime methods use both the Miller-Rabin and Lucas-Lehmer algorithms to test primality.
See passesMillerRabin(rounds, random) && passesLucasLehmer(); in BigInteger internal method primeToCertainty from java 7.
Further reading on:
Laurentiu L.
- 6,566
- 1
- 34
- 60
0
The algorithm used is an implementation detail that may vary from jdk to jdk, even between versions. The contract is only that it gives you a prime number, not that it follows any given algorithm to do so.
corsiKa
- 81,495
- 25
- 153
- 204