PHP PowerMod Function

30 November -0001

So for my latest math homework assignment I was tasked to develop a powermod function similar to the one available in Wolfram’s Mathematica. We were told to do it in any programming language, but Mathematica and Maple were recommended.

Unfortunately, given time constraints I barely had enough time to figure out how I’d implement this program, let alone how I would get it written in Maple. Instead I turned to my trusty friend PHP, since it does so much for me and I’m very comfortable with the syntax. PHP probably isn’t the best language to be doing any advanced mathematics (actually I’m pretty sure it’s one of the worst since it’s an interpreted language) but hey.

So the crux of this problem is to take a large number(a), raise it to the power of another large number(b), and figure out the result modulus a third number(n). The key to being able to do this is to realize that a2 mod n is the same as (a mod n * a mod n) mod n. Utilizing the modulus you can reduce the numbers to something much easier to compute. Also, you can figure out a composite factorization using powers of 2 to quickly evaluate a large exponent without actually having to do all the multiplication. For instance a100 is really just a64*a32*a4. Figuring out a2 is easy, multiply the result by itself and you have a4, multiply that result by itself and you get a8, and so on. You can see how the exponents can get very large very fast. Using a combination of those exponents to achieve the total allows you to do much smaller calculations.

The following PHP code snippet is designed to be run in a stand alone web page, but I’m sure you can see how the class Power_mod could be implemented independently.

 class Power_mod {
/**
* Array of binary values that sum to the factor
*
* @var array
*/
public $bin_sum_array;
/**
* The single largest binary in the bin_array
*
* @var int
*/
private $largest_binary_factor;
/**
* Array of all possible binary values from 2 to 
* $largest_binary_factor
*
* @var array
*/
private $array_to_largest_bin;
private $remainder;
/**
* This is an array of that mirrors the bin_sum_array, but the 
* values are calculated to the appropriate exponents of a mod n
*
* @var array
*/
public $a_value_array;
private $a;
private $b;
private $n;
/**
* This is the output of the powermod operation
*
* @var int
*/
public $final_value;
/**
* This function does all the heavy lifing.
*
* @param int $a
* @param int $b
* @param int $n
*/
public function calculate($a,$b,$n) {
	$this->a = intval($a);
	$this->b = intval($b);
	$this->n = intval($n);
	$this->build_array_of_binaries();
	$this->remainder = $this->b - $this->largest_binary_factor;
	$this->get_composite();
	$this->get_a_values();
	$this->compute_final_value();
}
/**
* This function builds an array of binary numbers used to 
* create the composite sum
*
*/
private function build_array_of_binaries() {
	$this->array_to_largest_bin[] = 1;
	$working_factor = 2;
	$this->array_to_largest_bin[] = $working_factor;
	while ($working_factor < ($this->b)/2 ) {
		$working_factor = 2*$working_factor;
		$this->array_to_largest_bin[] = $working_factor;
	}
	//no $working_factor is the largest number, commit it
	$this->largest_binary_factor = $working_factor;
	$this->bin_sum_array[] = $this->largest_binary_factor;
}
/**
* This function plugs in values for all the elements in the 
* binary_sum_array and calculates the final output
*
*/
private function compute_final_value() {
$val = 1;
foreach ($this->bin_sum_array as $piece) {
$val = ($val * $this->a_value_array[$piece]) % $this->n;
}
$this->final_value = $val % $this->n;
}
/**
* This function populates the $a_value_array;
*
*/
private function get_a_values() {
	//begin the mod process with the true value of a
	$local_a = $this->a % $this->n;
	$factor_number = 1;
	$this->a_value_array[$factor_number] = $this->a;
	while ($factor_number <= $this->largest_binary_factor) {
		$factor_number = $factor_number * 2;
		$this->a_value_array[$factor_number] = ($local_a * $local_a) % $this->n;
		$local_a = $this->a_value_array[$factor_number];
	}
}
/**
* This function determines the composite of sums that total 
* the original factor
*
*/
private function get_composite() {
	$i = count($this->array_to_largest_bin)-1;
	while ($this->array_to_largest_bin[$i] > $this->remainder) {
		$i–;
	}
	$this->bin_sum_array[] = $this->array_to_largest_bin[$i];
	$this->remainder = $this->remainder - $this->array_to_largest_bin[$i];
	if ($this->remainder > 0) {
		$this->get_composite();
	}
}
}