15.3 The Lucas Test
15.3 The Lucas Test In 1640, French mathematician Pierre de Fermat first wrote what is now known as Fermat's Little Theorem. [4] It states
For example, let p = 5, and let a = 7, which is certainly not divisible by 5. Then 7 5 - 1 = 7 4 = 2401 By itself, this theorem is not sufficient to prove that p is prime. There are also composite values for p that satisfy a p
For example, let p = 7 and a = 2. Then 3 7 - 1 = 3 6 = 729 This test has two serious drawbacks. First, we need to compute the prime factors of p -1. We've written a method to do this, but if p is large, it will take a while, assuming we have sufficient memory. Then there's the matter of finding the integer a. How many integers should we try before we give up and conclude that p is not prime? Listing 15-1a shows our implementation of the Lucas test in class LucasTest in package numbercruncher.primeutils . It tries values of a from 2 up to and including p. (The values of a ( p - 1)/ q (mod p ) start to repeat themselves every time the value of a reaches a multiple of p. ) Listing 15-1a The Lucas test for primality. package numbercruncher.primeutils; import numbercruncher.mathutils.ModuloArithmetic; import numbercruncher.mathutils.PrimeFactors; /** * An implemention of the the Lucas test for primality. */ public class LucasTest { private static LucasStatus status = new LucasStatus(); /** number to test for primality */ int p; /** prime factors of p-1 */ int q[]; /** caller of the test */ LucasCaller caller; /** * Constructor. * @param p the number to test for primality * @param caller the caller of the test */ public LucasTest(int p, LucasCaller caller) { this.p = p; this.caller = caller; q = PrimeFactors.factorsOf(p-1); } /** * Perform the Lucas test. * @return true if p is prime, false if p is composite */ public boolean test() { // Try integers a from 2 through p. for (int a = 2; a <= p; ++a) { if (passPart1(a) && passPart2(a)) return true; // prime } return false; // composite } /** * Test if integer a passes the first part of the test. * @param a the value of a * @return true if [a^(p-1)]%p == 1, else false */ private boolean passPart1(int a) { int exponent = p-1; int value = ModuloArithmetic.raise(a, exponent, p); // Report status back to the caller. if (caller != null) { status.a = a; status.q = 1; status.exponent = exponent; status.value = value; status.pass = (value == 1); caller.reportStatus(status); } return (value == 1); // pass if it's 1 } /** * Test if integer a passes the second part of the test. * @param a the value of a * @return true if [a^(p-1)/q]%p != 1 for all prime factors q, * else false */ private boolean passPart2(int a) { int pm1 = p-1; // Loop to try each prime factor. for (int i = 0; i < q.length; ++i) { int exponent = pm1/q[i]; int value = ModuloArithmetic.raise(a, exponent, p); // Report status back to the caller. if (caller != null) { status.a = a; status.q = q[i]; status.exponent = exponent; status.value = value; status.pass = (value != 1); caller.reportStatus(status); } if (value == 1) return false; // fail } return true; // pass } } The class breaks the test into two parts , methods passPart1() and passPart2() . It can also report the current status of the test back to the caller. Listing 15-1b shows the class LucasStatus . Listing 15-1b Status of the Lucas test. package numbercruncher.primeutils; /** * The current status of the Lucas test. * / public class LucasStatus { /** trial integer a */ int a; /** prime factor */ int q; /** exponent of a */ int exponent; /** modulo value */ int value; /** pass or fail */ boolean pass; public int getA() { return a; } public int getQ() { return q; } public int getExponent() { return exponent; } public int getValue() { return value; } public boolean didPass() { return pass; } } In order for the status reporting to work, the caller of the Lucas test must implement the interface LucasCaller , shown in Listing 15-1c. Listing 15-1c Interface LucasCaller . package numbercruncher.primeutils; /** * Interface for a caller of the Lucas test. */ public interface LucasCaller { /** * Report on the status of the Lucas test. * @param status the current status */ void reportStatus(LucasStatus status); } Finally, Listing 15-1d shows a demonstration program for the Lucas test, as well as its output for three prime numbers and a composite number. Listing 15-1d Demonstration of the Lucas test. package numbercruncher.program15_1; import numbercruncher.mathutils.AlignRight; import numbercruncher.primeutils.LucasTest; import numbercruncher.primeutils.LucasCaller; import numbercruncher.primeutils.LucasStatus; /** * PROGRAM 15-1: Lucas Test for Primality * * Demonstrate the Lucas test for primality. */ public class TestLucas implements LucasCaller { private int prevA = 0; private AlignRight ar = new AlignRight(); /** * Test an integer p for primality. * @param p the value of p */ void test(int p) { System.out.println("\nTESTING " + p + "\n"); ar.print("a", 5); ar.print("q", 10); ar.print("exponent", 12); ar.print("mod value", 12); ar.print("status", 10); ar.underline(); prevA = 0; boolean result = (new LucasTest(p, this)).test(); System.out.println(); System.out.println(p + " is " + (result ? "prime." : "composite.")); } /** * Report on the test status. * @param status the test status */ public void reportStatus(LucasStatus status) { // Skip a line for a new value of a. if ((prevA != 0) && (status.getA() != prevA)) { System.out.println(); } prevA = status.getA(); ar.print(status.getA(), 5); ar.print(status.getQ(), 10); ar.print(status.getExponent(), 12); ar.print(status.getValue(), 12); ar.print((status.didPass() ? "pass" : "fail"), 10); ar.println(); } /** * Main. * @param args the commandline arguments (ignored) */ public static void main(String args[]) { TestLucas lucas = new TestLucas(); // Test various integers. All but 21 are prime. lucas.test(7); lucas.test(15787); lucas.test(149287); lucas.test(21); } } Output: Testing 7 a q exponent mod value status ------------------------------------------------- 2 1 6 1 pass 2 2 3 1 fail 3 1 6 1 pass 3 2 3 6 pass 3 3 2 2 pass 7 is prime. TESTING 15787 a q exponent mod value status ------------------------------------------------- 2 1 15786 1 pass 2 2 7893 15786 pass 2 3 5262 11258 pass 2 877 18 9552 pass 15787 is prime. TESTING 149287 a q exponent mod value status ------------------------------------------------- 2 1 149286 1 pass 2 2 74643 1 fail 3 1 149286 1 pass 3 2 74643 149286 pass 3 3 49762 22426 pass 3 139 1074 131616 pass 3 179 834 123639 pass 149287 is prime. TESTING 21 a q exponent mod value status ------------------------------------------------- 2 1 20 4 fail 3 1 20 9 fail 4 1 20 16 fail 5 1 20 4 fail 6 1 20 15 fail 7 1 20 7 fail 8 1 20 1 pass 8 2 10 1 fail 9 1 20 18 fail 10 1 20 16 fail 11 1 20 16 fail 12 1 20 18 fail 13 1 20 1 pass 13 2 10 1 fail 14 1 20 7 fail 15 1 20 15 fail 16 1 20 4 fail 17 1 20 16 fail 18 1 20 9 fail 19 1 20 4 fail 20 1 20 1 pass 20 2 10 1 fail 21 1 20 0 fail 21 is composite. From the program output, it appears that, even for fairly large numbers, if the number is prime, it doesn't take too much time or effort to find the integer a that passes the test. However, if the number is large and composite, the Lucas test can take a long time if we're willing to test all values of a from 2 through p. What we need is a quick way to eliminate composite numbers.  |
1 (mod 
1 (mod | |
| Top |
EAN: 2147483647
Pages: 141