Consider the program below:
import java.math.*; import java.util.*; public class Prime_Gen { private static KeyboardReader keyboard = new KeyboardReader(); public static void main(String[] args) { Random seed; BigInteger p,q,n,x; int l = keyboard.readInt("number of bits of prime to be generated: "); do { seed = new Random(); p = new BigInteger(l, seed); } while (!p.isProbablePrime(50)); System.out.println("prime p is " + p); } }This program produces a prime number p between 1 and 2**l, where l is the program input. (A number p is prime is 1 and p are its only divisors; e.g. 17 and 1999 are primes, but 45 is not as it equals 5*9.) The program depends on the method isProbablePrime that returns "false" if p is not prime. If it returns "true", then p is prime with probability at least 1 - 2**(-50). This method can therefore not be captured with our approach of partial or total correctness. But the probability bound, once proved, serves as a quantitative correctness criteria. Returning to the program in the class Prime_Gen above, we cannot fit it into the framework of our chapter 4 for two reasons:
nunk% java Prime_Gen number of bits of prime to be generated: 10 prime p is 521 number of bits of prime to be generated: 50 prime p is 779086272649297 number of bits of prime to be generated: 80 prime p is 294755374770727725802903 number of bits of prime to be generated: 512 prime p is 1582669745767556434598467840683850400995794483300909462432520859046879044255382564136703926567700854183918516779360732250925951294970703995515688910221737
We could implement the method isProbablePrime with the Miller-Rabin algorithm:
import java.math.*; import java.util.*; public class Miller_Rabin { private static KeyboardReader keyboard = new KeyboardReader(); private static final BigInteger ZERO = new BigInteger("0"); private static final BigInteger ONE = new BigInteger("1"); private static final BigInteger TWO = new BigInteger("2"); public static void main(String[] args) { String ns = keyboard.readString("number to be tested for primality: "); BigInteger n = new BigInteger(ns); int s = keyboard.readInt("number of tests: "); if (is_prime(n,s)) { System.out.println(n + " is prime with probability at least " + (1 - Math.pow(2,-s))); } else { System.out.println(n + " is definitely not prime"); } } public static boolean is_prime(BigInteger n, int s) { BigInteger a; for (int i = 1; i <= s; ++i) { Random seed = new Random(); do { a = new BigInteger(n.bitLength()-1, seed); } while (a.compareTo(ZERO) <= 0 || a.compareTo(n) >= 0); if (witness(a,n)) { return false; } } return true; } public static boolean witness(BigInteger a, BigInteger n) { BigInteger b = n.subtract(ONE); int k = b.bitLength() - 1; BigInteger t = new BigInteger("1"); BigInteger x; for (int i = k; i >= 0; --i) { x = t; t = t.modPow(TWO,n); if (t.equals(ONE) && !x.equals(ONE) && !x.equals(b)) return true; if (b.testBit(i)) t = t.multiply(a).mod(n); } if (!t.equals(ONE)) { return true; } return false; } }
// b[1..k] is the binary representation of n - 1 and b[k] stores the // most significant bit t = 1; i = k; while (i >= 1) { t = (t * t) mod n; if (b[i] == 1) t = (t * a) mod n; i = i - 1; }Let us first consider an example simulation. To compute 3**22 modulo 23, note that the binary representation of 22 is 10110. So 3**22 modulo 23 may be written as ((((1**2 * 3)**2)**2 * 3)**2 * 3)**2 modulo 23. Note that this expression suggests the manner in which the program will compute this: the "net effect" exponent is 10110 in binary. Note that there are only two squaring that are not immediately multiplied by 3; they correspond to the two 0 bits in 10110. This computation is an instance of a**(p-1) modulo p, where p is prime and a != 0 modulo p. By Fermat's theorem, all such expressions evaluate to 1. This is one of the things the witness method checks!
Michael Huth (huth@cis.ksu.edu)