15.5 A Combined Primality Tester We can have a better primality test if we combine the Miller-Rabin and Lucas tests. Since composite numbers are troublesome for the Lucas test, we can first use the Miller-Rabin test to filter out numbers that are definitely composite. The remaining numbers are probably prime, and so we use the Lucas test on them to determine primality for sure. Listing 15-3a shows class PrimalityTest in package numbercruncher.primeutils , which combines the two tests. Listing 15-3a A combined primality tester. package numbercruncher.primeutils; import numbercruncher.primeutils.MillerRabinTest; import numbercruncher.primeutils.LucasTest; /** * Primality test that combines the Miller-Rabin and Lucas tests. */ public class PrimalityTest { /** number to test for primality */ private int p; /** number of times to run the Miller-Rabin test */ private int iterations; /** * Constructor. * @param p the number to test for primality * @param iterations the number of times to run * the Miller-Rabin test */ public PrimalityTest(int p, int iterations) { this.p = p; this.iterations = iterations; } /** * Perform the primality test. * @return true if p is prime, false if p is composite */ public boolean test() { return (new MillerRabinTest(p, iterations, null)).test() && (new LucasTest(p, null)).test(); } } Listing 15-3b shows a program that demonstrates this combined primality tester. Listing 15-3b Demonstration of the combined primality tester. package numbercruncher.program15_3; import numbercruncher.primeutils.PrimalityTest; /** * PROGRAM 15-3: Primality Testing * * Demonstrate the primality test. */ public class TestPrimality { public static void main(String args[]). { // Numbers to test. int ps[] = {7, 21, 8191, 15787, 149287, 524287, 1604401}; // Loop to test each number. for (int i = 0; i < ps.length; ++i) { int p = ps[i]; System.out.print(p + " is "); System.out.println((new PrimalityTest(p, 5)).test() ? "prime." : "composite."); } } } Output: 7 is prime. 21 is composite. 8191 is prime. 15787 is prime. 149287 is prime. 524287 is prime. 1604401 is composite. The primality tester in class numbercruncher.primeutils.PrimalityTest is similar to the one in class java.math.BigInteger . However, in class BigInteger , method isProbablePrime() uses the more advanced Lucas-Lehmer [7] test instead of the Lucas test. The Lucas-Lehmer test is beyond the scope of this book, but there are references for it at the end of this chapter. [7] Derrick Henry Lehmer (1905 C1991), known as the father of computational number theory, taught mathematics at the Berkeley campus of the University of California. | 
