Skip to content

Instantly share code, notes, and snippets.

@adameubanks

adameubanks/ChineseRemainderTheorem.html

Created June 10, 2021 14:24
Show Gist options
  • Save adameubanks/809066b211c36383fa2f26cb50cebd8a to your computer and use it in GitHub Desktop.
Save adameubanks/809066b211c36383fa2f26cb50cebd8a to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ChineseRemainderTheorem.html
<!DOCTYPE html>
<html>
<body>
<h3>x ≡ <input type="number" id="a1"> mod <input type="number" id="m1"></h3>
<br>
<h3>x ≡ <input type="number" id="a2"> mod <input type="number" id="m2"></h3>
<br>
<h3>x ≡ <input type="number" id="a3"> mod <input type="number" id="m3"></h3>
<button onclick="chineseRemainderTheorem()">Compute</button>
<h3 id="M"></h3>
<h3 id="M1"></h3>
<h3 id="M2"></h3>
<h3 id="M3"></h3>
<h3 id="y1"></h3>
<h3 id="y2"></h3>
<h3 id="y3"></h3>
<h3 id="Y1"></h3>
<h3 id="Y2"></h3>
<h3 id="Y3"></h3>
<h2 id="X"></h2>
<h2 id="X_final"></h2>
<script>
//Modular inverse
//e^-1 (mod n)
function modInv(e, n){
n0 = n;
y = 0;
x = 1;
while (e > 1){
quotient = Math.floor(e / n);
temp = n;
n = e % n;
e = temp;
temp = y;
y = x - (quotient*y);
x = temp;
}
if (x < 0){
x = x + n0
}
return x;
}
//Function on button-click
function chineseRemainderTheorem() {
big_m = document.getElementById("m1").value*document.getElementById("m2").value*document.getElementById("m3").value;
M.innerText = "M=m₁*m₂*m₃="+big_m;
big_m1 = document.getElementById("m2").value*document.getElementById("m3").value;
M1.innerText = "M₁=m₂*m₃="+big_m1;
big_m2 = document.getElementById("m1").value*document.getElementById("m3").value;
M2.innerText = "M₂=m₁*m₃="+big_m2;
big_m3 = document.getElementById("m1").value*document.getElementById("m2").value;
M3.innerText = "M₃=m₁*m₂="+big_m3;
y1.innerText = big_m1+"y₁ ≡ 1 (mod "+document.getElementById("m1").value+")";
y2.innerText = big_m2+"y₂ ≡ 1 (mod "+document.getElementById("m2").value+")";
y3.innerText = big_m3+"y₃ ≡ 1 (mod "+document.getElementById("m3").value+")";
y1_inv = modInv(big_m1,parseInt(document.getElementById("m1").value));
y2_inv = modInv(big_m2,parseInt(document.getElementById("m2").value));
y3_inv = modInv(big_m3,parseInt(document.getElementById("m3").value));
Y1.innerText = "y₁ ≡ "+y1_inv+" (mod "+document.getElementById("m1").value+")";
Y2.innerText = "y₂ ≡ "+y2_inv+" (mod "+document.getElementById("m2").value+")";
Y3.innerText = "y₃ ≡ "+y3_inv+" (mod "+document.getElementById("m3").value+")";
a1 = document.getElementById("a1").value;
a2 = document.getElementById("a2").value;
a3 = document.getElementById("a3").value;
X.innerText="X ≡ a₁*M₁*y₁ + a₂*M₂*y₂ + a₃*M₃*y₃ (mod M) ≡ "+(a1*big_m1*y1_inv+a2*big_m2*y2_inv+a3*big_m3*y3_inv)+" (mod "+big_m+")";
X_final.innerText = "X ≡ "+((a1*big_m1*y1_inv+a2*big_m2*y2_inv+a3*big_m3*y3_inv) % big_m)+" (mod "+big_m+")";
}
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment