Lineaire combinatie en greatest common divisor

[code]
<?php

/**	Getting the lineair combination and the greatest common divider  of 2 integers
*	@description Used to get the modulo inverse of some integer
*	@author Ruud Verbij
*	@date April the 8th 2008
*/

class LineairCombination {

	/**	@var			Integer
		@description	For counting the total steps used for the algorithm 
	*/
	private $steps = 0;
	
	/**	@var			Array
		@description	These 2 Arrays are used in this way:
					a[0] = q[0]*a[1] + a[2]
					a[1] = q[1]*a[2] + a[3]
					etc. 
	*/
	private $A = Array();
	private $Q = Array();
	
	/**	@var			Array
		@description 	This array is used to get the lineair combination of a[0] (table[i][0]) and a[1] (table[i][1]) for every i > 1
					Offcourse most valuable at table[count(table)+1] (the last A, the greatest common divider  of a[0] and a[1]) 
					So, table[i][0]*a[0] + table[i][1]*a[1] = a[i], this means that table[i] stores the lineair combination of a[0] and a[1] for a[i]
	*/
	private $table = Array();
	
	/**	@var			Array
		@description	The same as table[count(table)+1], so, used to store the information on a more easy way to find
	*/
	private $lineairCombination = Array();
	
	/**	@var			Integer
		@description	Used to store the greatest common divider , the same as a[count(a)-1]
	*/
	private $gcd = -1;
	
	/** 	Constructor
		@param		Integer
		@param		Integer
		@description	Inputs the 2 integers for which the greatest common divider  and the lineair combination must be calculated
		@require		$a != $b && is_integer($a) && is_integer($b) && $a > 0 && $b > 0
	*/
	public function __construct($a,$b) {
		// make sure that a[0] > a[1]
		$this->A[0] = ($a < $b) ? $b : $a;
		$this->A[1] = ($a > $b) ? $b : $a;
	}
	
	/**	Returns the greatest common divider 
		@require		called AFTER run method has been called
		@return		Integer, containing the greatest common divider  of A[0] and A[1]
	*/
	public function getGcd() {
		return $this->gcd;
	}
	
	/**	Returns the lineair combination
		@require		called AFTER run method has been called
		@return		Array, containing the lineair combination of A[0] and A[1] --> return[0]*A[0] + return[1]*A[1] = returnGcd()
	*/
	public function getLinComb() {
		return $this->lineairCombination;
	}	
	
	/**	Return the module inverse of A[1] in module A[0], only exists whenever getGcd() == 1, otherwhise the return is false
		@require		called AFTER run method has been called && getGcd() == 1, otherwhise a[1] has no modulo-inverse in modulo a[0]
		@return		Integer, 0 < return < A[0] OR false if getGcd != 1
		@ensure		return * A[1] mod A[0] = 1 OR return is false
	*/
	public function getModuloInverse() {
		return ($this->getGcd == 1) ? (($this->lineairCombination[1] < 0) ? $this->lineairCombination[1] + $this->A[0] : $this->lineairCombination[1]) : false;
	}
	
	/**	Some sort of reset function
		@ensure		Object == new LineairCombination($a,$b);
	*/
	public function setAandB($a, $b) {
		// reset all variables
		$this->steps 				= 0;
		$this->A 					= Array();
		$this->Q					= Array();
		$this->table				= Array();
		$this->lineairCombination 	= Array();
		$this->gcd 					= -1;
		
		// make sure that a[0] > a[1]
		$this->A[0] = ($a < $b) ? $b : $a;
		$this->A[1] = ($a > $b) ? $b : $a;
	}
	
	/**	Run the class
		@description	Used to run the class and find the greatest common divider  and lineair combination
	*/
	public function run() {
		// call both the gcd and lineair combination functions
		$this->recursiveGcd();
		$this->recursiveLineairCombination();
		
		// store the found variables in a logically named variable
		$this->gcd = $this->A[count($this->A)-1];
		$this->lineairCombination = $this->table[count($this->table)+1];
		
		// example echo
		echo "So, the lineair combination of (".$this->A[0].",".$this->A[1].") is:<br />";
		echo $this->gcd." = ".$this->lineairCombination[0]." x ".$this->A[0]." + ".$this->lineairCombination[1]." x ".$this->A[1];
		echo "<br />Calculated in ".$this->steps." steps";
		
		return;
	}
	
	/**	Find the greatest common divider  */
	private function recursiveGcd() {
		// call recursive function
		$this->gcd($this->A[0],$this->A[1],0);
		
		return;
	}
	
	/**	Recursive function gcd
		@description	Find the lineair combination of $a and $b and store it at $this->A[$n+2]
		@require		$a > $b && is_integer($a) && is_integer($b) && $a != 0 && $b != 0
		@ensure		$this->A[$n+2] = gcd($a,$b) && $this->A[$n+2] + $this->Q[$n]*$b = $a
	*/
	private function gcd($a,$b,$n) {	
		// increase steps
		$this->steps++;
		
		// the probably new A and Q values
		$new_A = $a % $b;
		$new_Q = floor($a/$b);
		
		// though, the new A cannot be 0, otherwhise we have already found the greatest common divider  ($b)
		if($new_A != 0) {
			// store the new A and Q
			$this->A[$n+2] = $new_A;
			$this->Q[$n] = $new_Q;
			
			// call the function recursively to find the gcd of A[$n+1] and A[$n+2] ($b and $new_A)
			$this->gcd($this->A[$n+1],$this->A[$n+2],$n+1);
		}
		return;
	}
	
	/**	Find the lineair combination
		@require		Called AFTER the getGcd method is called, therefore made private, and only called from the run method
	*/
	private function recursiveLineairCombination() {
		// first fill the second position of the table (pre-made)
		$this->table[2] = Array(1, -1 * $this->Q[0]);
		
		// if there will be a theird position ($a[0] != m * $a[1])
		if(count($this->Q) > 1)
			// fill it
			$this->table[3] = Array(-1*$this->Q[1],$this->Q[0]*$this->Q[1] + 1);
			
		// find the lineair combination recursively, by starting at the last A and working back
		// using the equation: A[n] = -1 * Q[n-2] * A[n-1] + A[n-2]
		$this->lineairCombination(count($this->A)-1);
		
		return;
	}
	
	/**	Find the lineair combination
		@description	Find the lineair combination of A[0] and A[1] to make A[$n], started at A[count(A)-1] and working back, filling the table
		@param		Integer, for which to find the lineair combination of A[0] and A[1]
		@require		Called AFTER the getGcd method is called, therefor made private, and only called from the getLineairCombination method, which has the same requirement
		@ensure		table[n][0]*a[0] + table[n][1]*a[1] = a[n]
	*/
	private function lineairCombination($n) {
		// increase the number of steps made
		$this->steps++;
		
		// if $n <= 3 --> table[n-2] is not defined AND all necessary $n <= 3 are already in the table
		if($n <= 3) return;
		
		// to make the code a little smaller, fill table[i][0] and table[i][1] with this for-loop
		$temp = Array();
		for($i = 1; $i <= 2; $i++) {
			// if not already in the table, find it recursively
			if(!$this->table[$n-$i][0])
				$this->lineairCombination($n-$i);
			$temp[$i-1] = $this->table[$n - $i];
		}
		
		// Fill the table with the equation: A[n] = -1 * Q[n-2] * A[n-1] + A[n-2]
		$this->table[$n] = Array(-1 * $this->Q[$n-2] * $temp[0][0] + $temp[1][0],
								 -1 * $this->Q[$n-2] * $temp[0][1] + $temp[1][1]);
		return;
	}

}

// Example (and testing)
$a = (isset($_GET['a'])) ? $_GET['a'] : 91;
$b = (isset($_GET['b'])) ? $_GET['b'] : 17;

$linComb = new LineairCombination($a,$b);
$linComb->run();

?>
[/code]