Modular inverse

Calculate modular inverse

by Jun Wang

HTML

<form name="A_valueForm">
 A: <input type="range" name="AInput" id="AInputId" value="7" min="1" max="20" oninput="AOutputId.value = AInput.value">
  <output name="AOutput" id="AOutputId">7</output>
</form>
<br>

<form name="P_valueForm">
 P: <input type="range" name="PInput" id="PInputId" value="23" min="1" max="47" oninput="POutputId.value = PInput.value">
  <output name="POutput" id="POutputId">23</output>
</form>
<br>

<button id="b" class="myButton">Get A mod_inv P</button>

<p>The modular inverse is: <span id="mod_inv"></span></p>

<p><strong>Note:</strong> A and P must share no factor greater than 1.</p>

CSS

#mod_inv {
color: blue;
}

/* insane button CSS from http://www.bestcssbuttongenerator.com/ */ 
.myButton {
	-moz-box-shadow: 0px 1px 0px 0px #f0f7fa;
	-webkit-box-shadow: 0px 1px 0px 0px #f0f7fa;
	box-shadow: 0px 1px 0px 0px #f0f7fa;
	background:-webkit-gradient(linear, left top, left bottom, color-stop(0.05, #33bdef), color-stop(1, #019ad2));
	background:-moz-linear-gradient(top, #33bdef 5%, #019ad2 100%);
	background:-webkit-linear-gradient(top, #33bdef 5%, #019ad2 100%);
	background:-o-linear-gradient(top, #33bdef 5%, #019ad2 100%);
	background:-ms-linear-gradient(top, #33bdef 5%, #019ad2 100%);
	background:linear-gradient(to bottom, #33bdef 5%, #019ad2 100%);
	filter:progid:DXImageTransform.Microsoft.gradient(startColorstr='#33bdef', endColorstr='#019ad2',GradientType=0);
	background-color:#33bdef;
	-moz-border-radius:6px;
	-webkit-border-radius:6px;
	border-radius:6px;
	border:1px solid #057fd0;
	display:inline-block;
	cursor:pointer;
	color:#ffffff;
	font-family:Arial;
	font-size:15px;
	font-weight:bold;
	padding:6px 24px;
	text-decoration:none;
	text-shadow:0px -1px 0px #5b6178;
}
.myButton:hover {
	background:-webkit-gradient(linear, left top, left bottom, color-stop(0.05, #019ad2), color-stop(1, #33bdef));
	background:-moz-linear-gradient(top, #019ad2 5%, #33bdef 100%);
	background:-webkit-linear-gradient(top, #019ad2 5%, #33bdef 100%);
	background:-o-linear-gradient(top, #019ad2 5%, #33bdef 100%);
	background:-ms-linear-gradient(top, #019ad2 5%, #33bdef 100%);
	background:linear-gradient(to bottom, #019ad2 5%, #33bdef 100%);
	filter:progid:DXImageTransform.Microsoft.gradient(startColorstr='#019ad2', endColorstr='#33bdef',GradientType=0);
	background-color:#019ad2;
}
.myButton:active {
	position:relative;
	top:1px;
}

JavaScript

// get the button and make it respond to a click
var theButton = document.getElementById("b");
theButton.onclick = feedTheButton;

// Note: A and P must share no factor greater than 1.
function modular_inverse(A,P) {
 var p0 = 1; var a0 = 0; 
 var p1 = 0; var a1 = 1;
 var R0 = P; var R1 = A % P;

 var n = 0; var R2 = 0; 
 var p2 = 0; var a2 = 0;
 
 while (R1 != 1 && R1 != 0){
 	n = Math.floor(R0/R1); R2 = R0%R1;
  p2 = p0 - n*p1 ; a2 = a0 - n*a1;
  p0 = p1; a0 = a1; p1 = p2; a1 = a2;
  R0 = R1; R1 = R2;
 }
 if (R1 == 0) {
 	return "Error: A and P share factor " + R0 + ". They must share no factor greater than 1."
 } 
 return a1 % P + "  (Verified: " + a1 % P +" * " + A + " mod " + P + " = 1)"        
}

function feedTheButton() {
	var A = parseInt(AOutputId.value);
	var P = parseInt(POutputId.value);
  var result = modular_inverse(A,P);
  var place = document.getElementById("mod_inv");
  place.innerHTML = result;
}