Published
Edited
Dec 15, 2019
md`# Extended Euclidean Algorithm`
function extEuclid(m, n) {
if (m < 1 || n < 1)
throw Error('m and n must be positive');
if (Math.floor(m) != m || Math.floor(n) != n)
throw Error('m and n must be integers');
let a = [1, 0];
let b = [0, 1];
let r = [n, m % n];
let q = [NaN, Math.floor(m / n)];
for (let i = 2; r[i-1] != 0; i++) {
a.push(a[i-2] - a[i-1] * q[i-1]);
b.push(b[i-2] - b[i-1] * q[i-1]);
r.push(r[i-2] % r[i-1]);
q.push(Math.floor(r[i-2] / r[i-1]));
}
return {
text: tex`GDC(${m}, ${n}) = ${a[a.length-1]}(${m}) + ${b[b.length-1]}(${n}) = ${r[r.length-2]}`,
m, n,
a: a[a.length-1],
b: b[b.length-1],
gcd: r[r.length-2],
};
}
extEuclid(48, 1246).text;
md`# Modular Multiplicative Inverse`
function modInverse(x, N) {
if (Math.floor(x) != x || Math.floor(N) != N) {
throw Error('x and N must be integers');
}
if ( N < 1) {
throw Error('N must be positive');
}
x = x % N;
x = x < 0 ? x + N : x;
let {gcd, a} = extEuclid(x, N);
if (gcd != 1) {
return {
text: md`${tex`x`} does not have a modular inverse in ${tex`\mathbb Z_{${N}}^*`}`,
error: true,
};
}
a = a % N;
a = a < 0 ? a + N : a;
if (1 != a * x % N) {
throw Error('Modular multiplicative inverse algorithm is incorrect');
}
return {
text: tex`${a}(${x}) \equiv 1 \mod {${N}}`,
}
}
modInverse(4, 37).text
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
