moduloarithmetic.java

素性检测的Java程序

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 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;
 	 	  }
 }