15.2 Congruences and Modulo Arithmetic A mathematician would take the boolean Java expression 7%4 == 3 and write it
which is read "7 is congruent to 3, modulo 4." In this example, the number 4 is the modulus . Modulo arithmetic [2] is key to many primality tests. Like "regular" arithmetic, modulo arithmetic has certain properties. Intuitively, these properties make sense if we think of modulo arithmetic as clock arithmetic, which we first encountered in Chapter 2 when we discussed Java's integer types. Here, if the modulus is m, we can imagine a clock face with the digits from 0 through m -1.
One property involves addition. Suppose we wish to compute the value of a + b (mod m ), where a, b, and m are integers. [3] One way is first to compute the sum s = a + b using regular addition. Then, starting at 0, we go around the clock face, perhaps several times, counting s digits. The digit where we end up is the value of a + b (mod m ).
Another way is to start at 0 and go around the clock face, counting a digits. Where we end up is the value of a (mod m ). From that digit, we continue around the clock face by counting b more digits. Where we stop is the value of a + b (mod m )?awhich is the same digit we arrived at the first way. In other words, we've demonstrated that
On the right-hand side, the final "(mod m )" is necessary to keep the sum inside the square brackets on the clock face, in case the sum exceeds m. Since multiplication is repeated addition, we also have the multiplication property
Listing 15-0b shows class ModuloArithmetic in package numbercruncher. mathutils . Its two methods compute ab (mod m ) and a b (mod m ). Listing 15-0b Modulo multiplication and exponentiation.package numbercruncher.mathutils; /** * Perform multiplication and exponentiation modulo arithmetic. */ public class ModuloArithmetic { /** * Multiply two integer values a and b modulo m. * @param a the value of a * @param b the value of b * @param m the modulus m * @return the value of ab (mod m) */ public static int multiply(int a, int b, int m) { int product = 0; // Loop to compute product = (a*b)%m. while (a > 0) { // Does the rightmost bit of a == 1? if ((a & 1) == 1) { product += b; product %= m; } // Double b modulo m, and // shift a 1 bit to the right. b <<= 1; b %= m; a >>= 1; } return product; } /** * Raise a to the b power modulo m. * @param a the value of a * @param b the value of b * @param m the modulus m * @return the value of a^b (mod m) */ public static int raise(int base, int exponent, int m) { int power = 1; // Loop to compute power = (base^exponent)%m. while (exponent > 0) { // Does the rightmost bit of the exponent == 1? if ((exponent & 1) == 1) { power = multiply(power, base, m); } // Square the base modulo m and // shift the exponent 1 bit to the right. base = multiply(base, base, m); exponent >>= 1; } return power; } /** * Main for testing. * @param args the commandline arguments (ignored) */ public static void main(String args[]) { int a = 3; int b = 13; int m = 5; // Test modulo multiplication. int modProduct = multiply(a, b, m); System.out.println(a + "*" + b + " = " + a*b); System.out.println(a + "*" + b + " = " + modProduct + " (mod " + m + ")"); System.out.println(); // Test modulo exponentiation. int modPower = raise(a, b, m); System.out.println(a + "^" + b + " = " + IntPower.raise(a, b)); System.out.println(a + "^" + b + " = " + modPower + " (mod " + m + ")"); } } Output: 3*13 = 39 3*13 = 4 (mod 5) 3^13 = 1594323.0 3^13 = 3 (mod 5) Recall that, in Chapter 2, we wrote the class IntPower , which performs exponentiation by partitioning the exponent into the sum of powers of 2. We can similarly compute the value of ab by partitioning the factor b into the sum of powers of 2. For example, if b is 13, we compute a x 13 as
But 4 a is 2 x 2 a, and 8 a is 2 x 4 a, so we can just repeatedly double the value of a, and by using the binary representation of 13 (1101), we simply add together the doubled values that correspond to each 1 bit. Method ModuloArithmetic.multiply() uses this algorithm, except that it computes each sum and doubling modulo m, which the addition property allows us to do. Method ModuloArithmetic.raise() is similar to IntPower.raise() , except that it invokes ModuloArithmetic.multiply() to do each multiplication and squaring. The multiplication property makes that possible. The test output in Listing 15-0b shows an example result from each method. With our two new classes, PrimeFactors and ModuloArithmetic , we're ready to do some primality testing. |
Top |