15.4 The Miller-Rabin Test
15.4 The Miller-Rabin Test The Miller-Rabin test [6] is the complement of the Lucas testit determines quickly whether or not an integer p is composite. It also uses Fermat's Little Theorem, but unlike the Lucas test, it does not require any factoring.
If the Miller-Rabin test decides a number is composite, then the number is definitely composite. However, if the test declares that a number is prime, then the number is probably prime. The test is wrong about primality at most 25% of the time. Therefore, the Miller-Rabin test is a probabilistic test. (The Lucas test is deterministic. ) To increase the probability that the test's determination of primality for a number is correct, we can rerun the test on the number. Each rerun decreases the probability that the test is wrong by a factor of The Miller-Rabin test of an integer p involves several steps:
To increase the probability that the test is correct if it states that p is probably prime, we should rerun the test by redoing steps 3 through 7 with a new random value for b. We can continue to rerun the test either until it declares that p is definitely composite or until we're satisfied with the probability that the test is right about p being prime. Listing 15-2a shows class MillerRabinTest in package numbercruncher. primeutils , which implements this test. The variable i counts the repetitions of steps 6.1C6.3 . The caller specifies how many different random base values b to try. Listing 15-2a The Miller-Rabin test for primality. package numbercruncher.primeutils; import java.util.Random; import numbercruncher.mathutils.ModuloArithmetic; /** * An implemention of the Miller-Rabin test for primality. */ public class MillerRabinTest { private static MillerRabinStatus status = new MillerRabinStatus(); /** number to test for primality */ private int p; /** number of times to run the test */ private int iterations; /** caller of the test */ private MillerRabinCaller caller; /** * Constructor. * @param p the number to test for primality * @param iterations the number of times to run the test * @param caller the caller of the test */ public MillerRabinTest(int p, int iterations, MillerRabinCaller caller) { this.p = p; this.iterations = iterations; this.caller = caller; } /** * Perform the Miller-Rabin test. * @return true if p is probably prime, false if p is composite */ public boolean test() { Random random = new Random(0); int k = p - 1; int s = 0; // Shift k to the right s bits to make it odd. while ((k & 1) == 0) { k >>= 1; ++s; } status.k = k; status.s = s; // Run the test with different random base values. for (int i = 0; i < iterations; ++i) { // Generate a random integer base b. int b; while ((b = random.nextInt(p)) <= 1); // want 1 < b < p status.b = b; // Composite? if (!test(k, s, b)) return false; // definitely composite } return true; // most likely prime } /** * Perform the Miller-Rabin test. * @param k the value of p-1 shifted right until it is odd * @param s the number of right shifts * @return true if p is probably prime, false if p is composite */ private boolean test(int k, int s, int b) { int pm1 = p-1; int sm1 = s-1; status.i = 0; status.code = MillerRabinStatus.DONT_KNOW_YET; int r = ModuloArithmetic.raise(b, k, p); // b^k (mod p) status.r = r; if (r == 1) { status.code = MillerRabinStatus.PROBABLY_PRIME; reportStatus(); return true; // probably prime } // Loop at most s-1 times. int i = 0; while (r != pm1) { reportStatus(); status.i = ++i; if (i > sm1) { status.code = MillerRabinStatus.DEFINITELY_COMPOSITE; return false; // definitely composite } r = ModuloArithmetic.raise(r, 2, p); // r^2 (mod p) status.r = r; if (r == 1) { status.code = MillerRabinStatus.DEFINITELY_COMPOSITE; reportStatus(); return false; // definitely composite } } status.code = MillerRabinStatus.PROBABLY_PRIME; reportStatus(); return true; // probably prime } /** * Report the test status back to the caller. * @param status the test status */ private void reportStatus() { if (caller != null) caller.reportStatus(status); } } Like our implementation of the Lucas test, we want the Miller-Rabin test to report its status back to its caller. Listing 15-2b shows class MillerRabinStatus . Listing 15-2b Status of the Miller-Rabin test. package numbercruncher.primeutils; /** * The current status of the Miller-Rabin test. */ public class MillerRabinStatus { // Status codes public static final int DONT_KNOW_YET = 0; public static final int DEFINITELY_COMPOSITE = 1; public static final int PROBABLY_PRIME = 2; /** random base */ int b; /** shifted p-1 */ int k; /** no. of right shifts */ int s; /** counter */ int i; /** modulo value */ int r; /** status code */ int code; public int getB() { return b; } public int getK() { return k; } public int getS() { return s; } public int getIndex() { return i; } public int getValue() { return r; } public int getCode() { return code; } } Listing 15-2c shows the interface MillerRabinCaller , which the caller must implement. Listing 15-2c Interface MillerRabinCaller . package numbercruncher.primeutils; /** * Interface for a caller of the Miller-Rabin test. */ public interface MillerRabinCaller { /** * Report on the status of the Miller-Rabin test. * @param status the current status */ void reportStatus(MillerRabinStatus status); } Finally, Listing 15-2d shows a demonstration program for the Miller-Rabin test, as well as its output for two prime and two composite numbers. Listing 15-2d Demonstration of the Miller-Rabin test. package numbercruncher.program15_2; import numbercruncher.mathutils.AlignRight; import numbercruncher.primeutils.MillerRabinTest; import numbercruncher.primeutils.MillerRabinCaller; import numbercruncher.primeutils.MillerRabinStatus; /** * PROGRAM 15-2: Miller-Rabin Test for Primality * * Demonstrate the Miller-Rabin test for primality. */ public class TestMillerRabin implements MillerRabinCaller { private static final int ITERATIONS = 5; private static final String CODE_LABELS[] = { "???", "composite", "prime?" }; private AlignRight ar = new AlignRight(); /** * Test an integer p for primality. * @param p the value of p */ public void test(int p) { System.out.println("\nTESTING " + p + "\n"); ar.print("b", 10); ar.print("k", 10); ar.print("s", 5); ar.print("i", 5); ar.print("r", 10); ar.print("status", 12); ar.underline(); MillerRabinTest mrt = new MillerRabinTest(p, ITERATIONS, this); boolean result = mrt.test(); System.out.println(); System.out.print(p + " is "); System.out.println(result ? "probably prime." : "composite."); } /** * Report on the test status. * @param status the test status */ public void reportStatus(MillerRabinStatus status) { ar.print(status.getB(), 10); ar.print(status.getK(), 10); ar.print(status.getS(), 5); ar.print(status.getIndex(), 5); ar.print(status.getValue(), 10); ar.print(CODE_LABELS[status.getCode()], 12); ar.println(); } /** * Main. * @param args the commandline arguments (ignored) */ public static void main(String args[]) { TestMillerRabin millerRabin = new TestMillerRabin(); millerRabin.test(21); millerRabin.test(8191); millerRabin.test(524287); millerRabin.test(1604401); } } Output: Testing 21 b k s i r status CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 12 5 2 0 3 ??? 12 5 2 1 9 ??? 21 is composite. TESTING 8191 b k s i r status CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 1738 4095 1 0 1 prime? 7195 4095 1 0 1 prime? 7187 4095 1 0 8190 prime? 1368 4095 1 0 1 prime? 4550 4095 1 0 8190 prime? 8191 is probably prime. TESTING 524287 b k s i r status CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 26082 262143 1 0 1 prime? 308713 262143 1 0 1 prime? 125334 262143 1 0 524286 prime? 311826 262143 1 0 524286 prime? 454445 262143 1 0 1 prime? 524287 is probably prime. TESTING 1604401 b k s i r status CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC 637182 100275 4 0 419491 ??? 637182 100275 4 1 393000 ??? 637182 100275 4 2 1337735 ??? 637182 100275 4 3 494434 ??? 1604401 is composite.  |
. Thus, after two runs, the probability of error is at most 
, or 6.25%. After five runs, the probability of error is less than 0.1%. However, if at any time the test declares that the number is composite, then the number is definitely composite. 
0. | |
| Top |
EAN: 2147483647
Pages: 141