15.2 Congruences and Modulo Arithmetic

   

 
Java Number Cruncher: The Java Programmer's Guide to Numerical Computing
By Ronald  Mak

Table of Contents
Chapter  15.   Prime Numbers

15.2 Congruences and Modulo Arithmetic

A mathematician would take the boolean Java expression

 7%4 == 3 

and write it

graphics/15equ02.gif


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.

[2] Modulo arithmetic is also called modular arithmetic.

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 ).

[3] Note that the "(mod m )" applies to the entire sum of a + b, not just to b.

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

graphics/15equ03.gif


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

graphics/15equ04.gif


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

graphics/15equ05.gif


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
 


Java Number Cruncher. The Java Programmer's Guide to Numerical Computing
Java Number Cruncher: The Java Programmers Guide to Numerical Computing
ISBN: 0130460419
EAN: 2147483647
Year: 2001
Pages: 141
Authors: Ronald Mak

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net