/*
	Author : Michael Clarke
	Description : This set of functions show the processes required for the Edinburgh uni mi1 course (from Extended Euclidean algorithm to the RSA cryptosystem) 

	License : 	This code is provided for everones use and can be copied and replicated at will. Feel free to link to it from your own website or put
				the file on your own site. Feel free to credit me as the source for this although it isn't necessary if you dont want to
				
	Please note : 	THIS FILE IS PROVIDED AS IS WITH NO WARRANTY OR IMPLIED WARRANTY FOR THE VALIDNESS OF THE FUNCTIONS 
	AND PROCESSES CONTAINED WITHIN.
		NO RESPONSIBILITY CAN BE ACCEPTED FOR USE OF ANY INCORRECT ANSWERS FROM THESE FUNCTIONS!
*/


/* Have fun using these and remember - they are here to help you learn : modify them to see if you can improve them  :o)   */


//gcd(a,b) takes two inputs and returns their grestest common divisor and X and Y as multiples of a and b to get the gcd
/*
	Requirements :
					integer "a"
					integer "b"
					
	Returns :
					Four-valued array - d,X,Y,display(of working)
*/

function gcd(a,b)
{
	
	var colA      = new Array(); // creates an array to hold the number in column A of the working
	var colB      = new Array(); // creates an array to hold the number in column B of the working
	var quotient  = new Array(); // creates an array to hold the quotient for each line in the workng 
	var remainder = new Array(); // creates an array to hold the remainder for each line of the working
	
	var counter=0; //counter is used to denote which line we are on (javascript index for an array is 0)
	var x=0;//initialises the variables x,y,d and output (the values returned by the function)
	var y=0;
	var d=0;
	var output="";
	
	colA[0] = new Array(1,0,a); //sets the first values in column A to (1,0,a)
	colB[0] = new Array(0,1,b); //sets the first values in column B to (0,1,b)
	
	quotient[0]  = Math.floor(colA[0][2]/colB[0][2]);     //gets the quotient of a/b (uses the floor function to make it a whole-number)
	remainder[0] = colA[0][2] - (quotient[0]*colB[0][2]); //gets the remainder of a/b
	
	while (remainder[counter]>0)
	//runs a loop to calculate all the rest of the lines (calculated the same as above) - runs until the remainder of the current line is 0
	{	
		counter++; //moves onto a new line
		colA[counter] = colB[counter-1]; //sets the new column A to the old column B
		colB[counter] = new Array(
								  	(colA[counter-1][0]-(colB[counter-1][0]*quotient[counter-1])), // calculates position 1 of column B eg (A,0,0)
									(colA[counter-1][1]-(colB[counter-1][1]*quotient[counter-1])), // calculates position 2 of column B eg (0,A,0)
									(colA[counter-1][2]-(colB[counter-1][2]*quotient[counter-1]))  // calculates position 3 of column B eg (0,0,A)
								);
		
		quotient[counter]  = Math.floor(colA[counter][2]/colB[counter][2]);
		remainder[counter] = colA[counter][2] - (quotient[counter]*colB[counter][2]);
		
	}
	
	//The following lines are executed once the loop (above) has finished so all lines of the euclidean algorithm are calculated
	
	
	//The following gets the required values from the working
	x = colB[counter][0]; //x is the 2nd number in the last line of column B
	y = colB[counter][1]; //y is the 2nd number in the last line of column B
	d = colB[counter][2]; //d is the 3rd number in the last line of column B

	//the coding that follows is just for purposes of displaying the stages of working for the user, it can be modified as needed
	
	output= "<table cellpadding='0' cellspacing='0' id='workingTable'>";
	output+=("<tr><th class='workingColumn'>A</th><th class='workingColumn'>B</th><th class='workingColumn'>Quotient</th><th>Remainder</th></tr>");
	for (i=0; i<= counter; i++)
	{
		output+="<tr><td class='workingColumn'>(";
		output+= colA[i];
		output+= ")</td><td class='workingColumn'>(";
		output+= colB[i]
		output+= ")</td><td class='workingColumn'>&nbsp;</td><td>&nbsp;</td></tr>";
		output+= "<tr><td class='topRow'>&nbsp;</td><td class='topRow'>&nbsp;</td><td class='topRow'>";
		output+= quotient[i]
		output+= "</td><td class='topRow1'>"
		output+= remainder[i];
		output+= "</td></tr>";
	}
	output+= "</table>";
	//end creation of display
	
	//returns the values for d,X,Y and the output display (in the order)
	return (new Array(d,x,y,output));
}
//end gcd(a,b)








//mod(a,b,n) takes three inputs and returns all possible values of x (mod n). Requires the gcd(a,b) equation from above
/*
	Requirements :
					integer "a"
					integer "b"
					integer "n"
					
	Returns :
					Two-valued array - x (array with all values of x or an error message),display(of working)
*/
function mod(a,b,n)
{
	var r = 0;// initialises variables
	var s = 0;
	var d = 0;
	var gcdOutput = "";
	var x = new Array();
	var output = "";
	
	var gcdAns = gcd(a,n);//runs the gcd on a and n
	
	d = gcdAns[0];//splits the naswers of the gcd into the appririate variables
	r = gcdAns[1];
	s = gcdAns[2];
	gcdOutput = gcdAns[3];
	if (Math.floor(b/d)!=(b/d))//checks if b is a factor of d
	{
		x = "<b>No Values for <i>x</i>";//returns an error message for x if b was not a factor of d
	}
	else // if b is a factor of d then it runs the following statements
	{
		
		if (b==1)//if b is 1 (and b is a factor of d) then x = r (mod n)
		{
			x[0] = r;
		}
		else //if b is not a factor of 1 then does the following lines
		{
			for (k=0; k<=(d-1); k++)
			{
				x[k]= (r*(b/d)) + (k*(n/d)); // for all values of k =0..(d-1) : x = r(b/d) + k(n/d)
			}
		}
		
		
		for (i=0; i<x.length; i++)//loops through all calculated calues of x
		{
			while (x[i]>=n)
			{
				x[i] -=(n*1); //if x is greater than n then it subtracts n repeadedly until 0<=x<n
			}
			
			while (x[i]<0)
			{
				x[i] += (n*1);//if x is less than 0 then it adds n repeadedly until 0<=x<n
			}
		}
	
		x.sort(sortHelp);//sorts n into numerical order (uses the helper functoin sortHelp shown below). This is only for display purposes
	}
	
	//what follows is only to show a working output for the user and can be modified at will
	
	output = "From the <a href=\"#\" onclick=\"if (document.getElementById('eeaHolder').style.display=='block') {document.getElementById('eeaHolder').style.display='none' } else {document.getElementById('eeaHolder').style.display='block'}\">Extended Euclidean Algorithm</a> we get:<br/><div id=\"eeaHolder\">"+gcdOutput+"<div id=\"equationSolved\"><i>d</i> = gcd("+a+","+n+") = "+d+"<br/><br/><i>r</i> = "+r+"<br/><i>s</i> = "+s+"<br/></div></div><i>d</i> = "+d+", <i>s</i> = "+s+", <i>r</i> = "+r+"	<br />and from above we know that<br /><i>a</i> = "+a+", <i>b</i> = "+b+", <i>n</i> = "+n+"<br /><br />";
	
	if (Math.floor(b/d)!=(b/d))
	{
		output += "<b>Since d=gcd(a,n) is not a factor of b the equation ax=b(mod n) has no solutions</b>";
	}
	else if (b==1)
	{
		output += "Since b = 1 and d = 1<br/>x = "+x[0]+"<br/>(using Extended Euclidean Algorithm : gcd(a,n) )";
	}
	else
	{
		output += "Now using:<br /><i>k</i> = 0,1,2...<i>d</i>-1<br />we can find <i>x</i> by<br /><br/><i>x</i> = <i>r</i>(<i>b</i>/<i>d</i>) + <i>k</i>(<i>n</i>/<i>d</i>) (mod <i>n</i>) <br/><i>x</i> = "+r+"("+b+"/"+d+") + <i>k</i>("+n+"/"+d+")<br/> = "+(r*(b/d))+" + "+(n/d)+"<i>k</i> (mod "+n+")<br/>for <i>k</i> = ";
		if (d>=1) { output += "0,1"; }
		if (d==2) { output += ",2"; } else if (d>2) {output += ",..,"+(d-1);}
	}
	output += "<br/><br/><span class=\"quickNote\">Note : Click on the above link to show/hide the working for the Extended Euclidean Algorithm</span></div>";
	//end creation of display
	
	//the following statement returns the vaues for x and the working given above
	return( new Array(x,output));
	
}
//end mod(a,b,n)




//this sortHelp function is to help numerical arrays to be sorted correctly
function sortHelp(a,b)
{
	return(a-b);
}
//end sortHelp(a,b)