I am a very very creative app but it seems to have work hard and it doesn't even open. (written using predictive text)
Public
Edited
Apr 11, 2023
viewof p = Inputs.select([2, 3, 5, 7])
viewof n = Inputs.number({ value: 2, min: 2, max: 3 })
viewof polynomial = Inputs.select(allMinimalPolynomials(p, n), {
format: (x) => printPolynomial([...x, -1])
})
drawMultTable(p, n, polynomial)
fieldElements(2, 3).map(printPolynomial)
function fieldElements(p, n) {
const coeffs = _.range(n).map(() => _.range(p));
// return coeffs;
return [...cartesianProduct(...coeffs)].map((x) => x.reverse());
}
allMinimalPolynomials(2, 6).map((f) => printPolynomial([...f, -1]))
drawPolynomial([0, 1, 2, 2, 4], 5, 5)
function drawPolynomial(f, p, n) {
const s = 50;
const ds = s / 2 / n;
return html`<svg width=${s} height=${s}>${_.range(n - 1, -1, -1).map((i) => {
const pos = ds * (n - i - 1);
const l = ds * (i + 1);
return `<rect x=${pos} y=${pos} width=${l * 2} height=${
l * 2
} fill="${getElementColor(f[i], p)}"/>`;
})}</svg>`;
}
// get the color of an element in the prime field F_p
function getElementColor(a = 0, p) {
// scale lightness so that colors further from 0 are lighter
return d3Scale.interpolateRainbow(a / p);
// return `hsl(${(a / p) * 360}deg, 75%, 50%)`;
}
// find all minimal polynomials for F_{p^k}
function allMinimalPolynomials(p, k) {
// polynomials of the form x^q = f(x)
const coeffs = [_.range(1, p), ..._.range(1, k).map((i) => _.range(p))];
const fs = cartesianProduct(...coeffs);
return [...fs].filter((f) => isMinimalPolynomial(f, p, k));
}
//
function isMinimalPolynomial(f, p, k) {
// check irreducible by testing all elements of p
const fullF = [...f, -1];
if (_.range(p).some((n) => applyPolynomial(fullF, n, p) === 0)) {
return false;
}
// to check minimality, iterate by all powers and make sure it doesn't go to 1 until p^k-1
let g = [1];
for (const j of _.range(1, p ** k - 1)) {
g = reducePolynomial([0, ...g], p, k, f);
if (_.isEqual(g, [1])) {
return false;
}
}
return true;
}
// Reduce the polynomial g with the splitting polynomifal -x^k + f(x) over the prime field p (where k is the degree of f + 1)
function reducePolynomial(g, p, k, f) {
const deg = degree(g);
if (deg < k) {
return g;
}
const front = g.slice(0, k);
const back = g.slice(k);
// TODO handle case where deg > 2k
return addPolynomials(front, multiplyPolynomials(back, f, p), p);
}
// add the two polynomials with coefficients in F_p
function addPolynomials(f, g, p) {
const sum = _.zip(f, g).map(([a = 0, b = 0]) => mod(a + b, p));
return _.dropRightWhile(sum, (a) => a === 0);
}
// apply f(x) over F_p
function applyPolynomial(f, x, p) {
return mod(_.sum(f.map((coeff, i) => coeff * x ** i)), p);
}
function* cartesianProduct(...arrs) {
if (arrs.length <= 0) {
yield [];
return;
}
const [head, ...tail] = arrs;
for (const item of head) {
for (const rest of cartesianProduct(...tail)) {
yield [item, ...rest];
}
}
}
// Multiply polynomials f and g over p
function multiplyPolynomials(f, g, p) {
let result = [0];
for (const [i, a] of f.entries()) {
result = addPolynomials(
result,
[..._.range(i).map((_) => 0), ...multiplyScalar(g, a, p)],
p
);
}
return result;
}
// Multiply polynomial f over F_p over a
function multiplyScalar(f, a, p) {
return f.map((b) => mod(b * a, p));
}
[...[..."abc"].entries()]
function printPolynomial(f, variable = "x") {
return (
[...f.entries()]
.reverse()
.filter(([i, a]) => a !== 0)
.map(
([i, a]) =>
`${a === 1 && i != 0 ? "" : a}${
i === 0 ? "" : i === 1 ? "x" : "x^" + i
}`
)
.join(" + ") || 0
);
}
function mod(a, b) {
return ((a % b) + b) % b;
}
function degree(f) {
return f.length;
}
_ = require("lodash")
d3Scale = require("d3-scale-chromatic")
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.
