import { loadModule, bytesToBigInt } from "./abi.js";
import { trialDivide, isPrime, perfectPower, pollardBrent, groupFactors, rsaNumber, bitLength } from "./numtheory.js";
const SIMD_WASM_URL = new URL("./rusqsieve-simd.wasm", import.meta.url);
const SCALAR_WASM_URL = new URL("./rusqsieve.wasm", import.meta.url);
const BATCH = 2;
const MAX_FAMILIES = 100_000;
const MAX_INPUT_BITS = 512;
const MAX_DECIMAL_DIGITS = 155;
const BOOT_TIMEOUT_MS = 30_000;
const JOB_TIMEOUT_MS = 120_000;
const RUN_TIMEOUT_MS = 30 * 60_000;
const els = {
input: document.getElementById("input"),
inputMirror: document.getElementById("input-mirror"),
inputInfo: document.getElementById("input-info"),
go: document.getElementById("go"),
bar: document.getElementById("bar"),
status: document.getElementById("status"),
result: document.getElementById("result"),
workers: document.getElementById("workers"),
meter: document.getElementById("meter"),
rsaBits: document.getElementById("rsa-bits"),
rsaBitsLabel: document.getElementById("rsa-bits-label"),
rsaGen: document.getElementById("rsa-gen"),
};
let coord = null; let workers = []; let gen = 0; let wasmFlavor = "scalar";
let runtimeReady = false;
const nWorkers = Math.max(1, Math.min(48, navigator.hardwareConcurrency || 4));
async function boot() {
runtimeReady = false;
let module;
try {
module = await withTimeout(loadModule(SIMD_WASM_URL), BOOT_TIMEOUT_MS, "SIMD wasm load");
wasmFlavor = "SIMD";
} catch {
module = await withTimeout(
loadModule(SCALAR_WASM_URL),
BOOT_TIMEOUT_MS,
"scalar wasm load",
);
wasmFlavor = "scalar";
}
const nextCoord = new Worker(new URL("./coordinator.js", import.meta.url), { type: "module" });
const nextWorkers = Array.from(
{ length: nWorkers },
() => new Worker(new URL("./worker.js", import.meta.url), { type: "module" }),
);
const bootAbort = new AbortController();
try {
const [coordinatorReady] = await Promise.all([
waitForWorkerReady(nextCoord, module, true, bootAbort.signal),
...nextWorkers.map((worker) =>
waitForWorkerReady(worker, module, false, bootAbort.signal),
),
]);
coord = nextCoord;
workers = nextWorkers;
runtimeReady = true;
els.workers.textContent =
`${nWorkers} worker${nWorkers === 1 ? "" : "s"} · ${wasmFlavor} · ` +
`ABI v${coordinatorReady.abi}`;
} catch (error) {
bootAbort.abort();
nextCoord.terminate();
for (const worker of nextWorkers) worker.terminate();
throw error;
}
els.go.disabled = false;
els.status.textContent = "Ready.";
}
function shutdownRuntime() {
runtimeReady = false;
coord?.terminate();
for (const worker of workers) worker.terminate();
coord = null;
workers = [];
}
async function restartRuntime() {
shutdownRuntime();
els.go.disabled = true;
await boot();
}
function waitForWorkerReady(worker, module, requireAbi, signal) {
return new Promise((resolve, reject) => {
let settled = false;
const timer = setTimeout(
() => finish(new Error("worker initialization timed out")),
BOOT_TIMEOUT_MS,
);
const cleanup = () => {
clearTimeout(timer);
worker.removeEventListener("message", onMessage);
worker.removeEventListener("error", onError);
worker.removeEventListener("messageerror", onMessageError);
signal?.removeEventListener("abort", onAbort);
};
const finish = (error, data) => {
if (settled) return;
settled = true;
cleanup();
if (error) reject(error);
else resolve(data);
};
const onMessage = ({ data }) => {
if (data?.type === "error") {
finish(new Error(data.error || "worker initialization failed"));
} else if (data?.type === "ready") {
if (requireAbi && data.abi !== 2) {
finish(new Error(`unsupported rusqsieve wasm ABI ${String(data.abi)}`));
} else {
finish(null, data);
}
}
};
const onError = (event) => {
event.preventDefault?.();
finish(new Error(event.message || "worker failed during initialization"));
};
const onMessageError = () => finish(new Error("worker initialization message was invalid"));
const onAbort = () => finish(new Error("worker initialization cancelled"));
worker.addEventListener("message", onMessage);
worker.addEventListener("error", onError);
worker.addEventListener("messageerror", onMessageError);
signal?.addEventListener("abort", onAbort, { once: true });
if (signal?.aborted) {
onAbort();
return;
}
try {
worker.postMessage({ cmd: "init", module });
} catch (error) {
finish(error);
}
});
}
function withTimeout(promise, milliseconds, label) {
return new Promise((resolve, reject) => {
const timer = setTimeout(() => reject(new Error(`${label} timed out`)), milliseconds);
Promise.resolve(promise).then(
(value) => {
clearTimeout(timer);
resolve(value);
},
(error) => {
clearTimeout(timer);
reject(error);
},
);
});
}
function siqsParallel(decimal, bits, report) {
return new Promise((resolve, reject) => {
const myGen = ++gen;
const sieveStarted = performance.now();
let target = 0;
let relations = 0;
let nextFamily = 0;
let activeJobs = 0;
let pendingSubmissions = 0;
let preparedWorkers = 0;
let finished = false;
const workerBusy = new Array(workers.length).fill(false);
const workerPrepared = new Array(workers.length).fill(false);
const jobTimers = new Map();
const runTimer = setTimeout(
() => fail(new Error("factorization timed out")),
RUN_TIMEOUT_MS,
);
const cleanup = () => {
clearTimeout(runTimer);
for (const timer of jobTimers.values()) clearTimeout(timer);
jobTimers.clear();
coord.onmessage = null;
coord.onerror = null;
coord.onmessageerror = null;
for (const worker of workers) {
worker.onmessage = null;
worker.onerror = null;
worker.onmessageerror = null;
}
};
const fail = (error) => {
if (finished) return;
finished = true;
cleanup();
reject(error instanceof Error ? error : new Error(String(error)));
};
const succeed = (factor) => {
if (finished) return;
finished = true;
cleanup();
resolve(factor);
};
const maybeExhausted = () => {
if (
!finished &&
nextFamily >= MAX_FAMILIES &&
activeJobs === 0 &&
pendingSubmissions === 0 &&
preparedWorkers === workers.length
) {
fail(new Error(`relation budget exhausted after ${MAX_FAMILIES} families`));
}
};
const dispatch = (worker, workerIndex) => {
if (finished || workerBusy[workerIndex]) return false;
if (nextFamily >= MAX_FAMILIES) {
maybeExhausted();
return false;
}
const family = nextFamily;
const count = Math.min(BATCH, MAX_FAMILIES - nextFamily);
nextFamily += count;
workerBusy[workerIndex] = true;
activeJobs++;
const timer = setTimeout(
() => fail(new Error(`sieve worker ${workerIndex + 1} timed out`)),
JOB_TIMEOUT_MS,
);
jobTimers.set(workerIndex, timer);
try {
worker.postMessage({ cmd: "sieve", family, count, gen: myGen });
} catch (error) {
clearTimeout(timer);
jobTimers.delete(workerIndex);
workerBusy[workerIndex] = false;
activeJobs--;
fail(error);
return false;
}
return true;
};
const finishJob = (workerIndex) => {
if (!workerBusy[workerIndex]) {
fail(new Error(`unexpected response from idle sieve worker ${workerIndex + 1}`));
return false;
}
clearTimeout(jobTimers.get(workerIndex));
jobTimers.delete(workerIndex);
workerBusy[workerIndex] = false;
activeJobs--;
return true;
};
coord.onmessage = ({ data }) => {
if (data?.gen !== myGen) return;
if (data.type === "error") {
fail(new Error(data.error || "coordinator failed"));
} else if (data.type === "session") {
if (!Number.isInteger(data.target) || data.target <= 0) {
fail(new Error("coordinator returned an invalid relation target"));
return;
}
target = data.target;
try {
for (const w of workers) {
w.postMessage({ cmd: "prepare", n: decimal, gen: myGen });
}
} catch (error) {
fail(error);
}
} else if (data.type === "submitted") {
if (pendingSubmissions <= 0) {
fail(new Error("coordinator acknowledged an unknown submission"));
return;
}
pendingSubmissions--;
if (
!Number.isInteger(data.worker) ||
data.worker < 0 ||
data.worker >= workers.length ||
!Number.isInteger(data.relations) ||
data.relations < relations ||
!Number.isInteger(data.target) ||
data.target <= 0
) {
fail(new Error("coordinator returned invalid progress"));
return;
}
relations = data.relations;
target = data.target;
const now = performance.now();
const elapsedSeconds = (now - sieveStarted) / 1000;
const progress = target > 0 ? Math.min(1, relations / target) : 0;
const etaSeconds =
progress >= 0.03 ? elapsedSeconds * (progress ** (-1 / 1.6) - 1) : null;
report({
phase: "sieving",
bits,
relations,
target,
elapsedSeconds,
etaSeconds,
});
if (!finished) {
dispatch(workers[data.worker], data.worker);
maybeExhausted();
}
} else if (data.type === "linalg") {
report({ phase: "linalg" });
} else if (data.type === "factor") {
if (!(data.factor instanceof Uint8Array)) {
fail(new Error("coordinator returned a malformed factor"));
return;
}
const factor = bytesToBigInt(data.factor);
const composite = BigInt(decimal);
if (factor <= 1n || factor >= composite || composite % factor !== 0n) {
fail(new Error("coordinator returned an invalid factor"));
return;
}
succeed(factor);
} else {
fail(new Error(`unknown coordinator response: ${String(data.type)}`));
}
};
coord.onerror = (event) => {
event.preventDefault?.();
fail(new Error(event.message || "coordinator worker crashed"));
};
coord.onmessageerror = () => fail(new Error("coordinator returned an invalid message"));
workers.forEach((w, workerIndex) => {
w.onmessage = ({ data }) => {
if (data?.gen !== myGen) return;
if (data.type === "error") {
fail(new Error(data.error || `sieve worker ${workerIndex + 1} failed`));
return;
}
if (finished) return;
if (data.type === "prepared") {
if (workerPrepared[workerIndex]) {
fail(new Error(`sieve worker ${workerIndex + 1} prepared twice`));
return;
}
if (!data.ok) {
fail(new Error(`sieve worker ${workerIndex + 1} could not build a sieve`));
return;
}
workerPrepared[workerIndex] = true;
preparedWorkers++;
dispatch(w, workerIndex);
} else if (data.type === "relations") {
if (!finishJob(workerIndex)) return;
if (data.payload) {
if (!(data.payload instanceof Uint8Array)) {
fail(new Error(`sieve worker ${workerIndex + 1} returned invalid relations`));
return;
}
pendingSubmissions++;
try {
coord.postMessage(
{ cmd: "submit", payload: data.payload, worker: workerIndex, gen: myGen },
[data.payload.buffer],
);
} catch (error) {
pendingSubmissions--;
fail(error);
}
return;
}
fail(new Error(`sieve worker ${workerIndex + 1} could not serialize relations`));
} else {
fail(new Error(`unknown sieve-worker response: ${String(data.type)}`));
}
};
w.onerror = (event) => {
event.preventDefault?.();
fail(new Error(event.message || `sieve worker ${workerIndex + 1} crashed`));
};
w.onmessageerror = () =>
fail(new Error(`sieve worker ${workerIndex + 1} returned an invalid message`));
});
try {
coord.postMessage({ cmd: "new", n: decimal, gen: myGen });
} catch (error) {
fail(error);
}
});
}
async function factorize(N, report) {
const primes = [];
const stack = [N];
while (stack.length) {
let c = stack.pop();
report({ phase: "trial", n: c });
await tick();
c = trialDivide(c, primes);
if (c === 1n) continue;
report({ phase: "primality", n: c });
await tick();
if (isPrime(c)) {
primes.push(c);
continue;
}
const pp = perfectPower(c);
if (pp) {
for (let i = 0; i < pp.k; i++) stack.push(pp.base);
continue;
}
report({ phase: "pollard", n: c });
await tick();
const d = pollardBrent(c, 1 << 15);
if (d && d > 1n && d < c) {
stack.push(d, c / d);
continue;
}
const factor = await siqsParallel(c.toString(), bitLength(c), report);
if (factor <= 1n || factor >= c || c % factor !== 0n) {
throw new Error("quadratic sieve returned an invalid factor");
}
stack.push(factor, c / factor);
}
return groupFactors(primes);
}
const tick = () => new Promise((r) => setTimeout(r, 0));
const SUP = { "0": "⁰", "1": "¹", "2": "²", "3": "³", "4": "⁴", "5": "⁵", "6": "⁶", "7": "⁷", "8": "⁸", "9": "⁹" };
const sup = (n) => String(n).replace(/\d/g, (d) => SUP[d]);
const PHASE_TEXT = {
trial: (s) => `Trial division on a ${digits(s.n)}-digit number…`,
primality: (s) => `Miller–Rabin primality test (${digits(s.n)} digits)…`,
pollard: (s) => `Pollard's rho on a ${digits(s.n)}-digit number…`,
sieving: (s) => {
const progress =
`Quadratic sieve: ${s.relations}/${s.target} relations across ${nWorkers} workers…`;
if (s.bits <= 256) return progress;
const elapsed = `elapsed ${formatDuration(s.elapsedSeconds)}`;
const eta =
Number.isFinite(s.etaSeconds) && s.etaSeconds >= 0
? `ETA ≈ ${formatDuration(s.etaSeconds)}`
: "ETA calculating…";
return `${progress} ${elapsed} · ${eta}`;
},
linalg: () => `Linear algebra over GF(2) — extracting a factor…`,
};
const digits = (n) => n.toString().length;
const normalizeNumberText = (text) =>
text
.replace(/[0-9]/gu, (digit) => String(digit.codePointAt(0) - 0xff10))
.replace(/[\p{White_Space}\uFEFF]/gu, "");
const formatDuration = (seconds) => {
const rounded = Math.max(0, Math.round(seconds));
if (rounded < 60) return `${rounded}s`;
const minutes = Math.floor(rounded / 60);
const remainder = rounded % 60;
return `${minutes}m ${String(remainder).padStart(2, "0")}s`;
};
function render(grouped, original, seconds) {
const plain = grouped
.map(({ prime, exponent }) => (exponent === 1 ? `${prime}` : `${prime}^${exponent}`))
.join(" * ");
let product = 1n;
for (const { prime, exponent } of grouped) product *= prime ** BigInt(exponent);
const verified = product === original;
els.result.innerHTML = "";
const big = document.createElement("div");
big.className = "factors";
if (!grouped.length) {
big.textContent = "1";
} else {
grouped.forEach(({ prime, exponent }, i) => {
if (i) {
const sep = document.createElement("span");
sep.className = "sep";
sep.textContent = "·";
big.append(sep);
}
const factor = document.createElement("span");
factor.className = "factor";
const value = document.createElement("span");
value.className = "value";
value.textContent = exponent === 1 ? `${prime}` : `${prime}${sup(exponent)}`;
const bits = document.createElement("span");
bits.className = "bits";
bits.textContent = `${bitLength(prime)} bits`;
factor.append(value, bits);
big.append(factor);
});
}
const meta = document.createElement("div");
meta.className = "meta";
meta.textContent =
`${grouped.length} distinct prime${grouped.length === 1 ? "" : "s"} · ` +
`${bitLength(original)}-bit input · ` +
`${verified ? "✓ verified" : "✗ VERIFICATION FAILED"} · ` +
`${seconds.toFixed(seconds < 10 ? 2 : 1)} s`;
const copy = document.createElement("code");
copy.className = "plain";
copy.textContent = plain || "1";
els.result.append(big, meta, copy);
els.result.classList.toggle("bad", !verified);
}
function updateInputInfo() {
const text = normalizeNumberText(els.input.value);
const significant = text.replace(/^0+/u, "") || "0";
if (/^\d+$/.test(text) && significant.length > MAX_DECIMAL_DIGITS) {
els.inputInfo.textContent =
`${significant.length} significant digits · exceeds the ${MAX_INPUT_BITS}-bit limit`;
} else if (/^\d+$/.test(text) && BigInt(text) > 0n) {
const N = BigInt(text);
const bits = bitLength(N);
els.inputInfo.textContent =
`${text.length} digit${text.length === 1 ? "" : "s"} · ${bits} bits` +
(bits > MAX_INPUT_BITS ? ` · limit ${MAX_INPUT_BITS}` : "");
} else {
els.inputInfo.textContent = "";
}
}
function resizeNumberInput() {
els.inputMirror.textContent = `${els.input.value}\u200b`;
}
function normalizeNumberInput() {
const normalized = normalizeNumberText(els.input.value);
if (normalized !== els.input.value) els.input.value = normalized;
resizeNumberInput();
updateInputInfo();
return normalized;
}
function insertAtNumberSelection(text) {
els.input.setRangeText(text, els.input.selectionStart, els.input.selectionEnd, "end");
resizeNumberInput();
updateInputInfo();
}
async function run() {
const text = normalizeNumberInput();
if (!/^\d+$/.test(text)) {
els.status.textContent = "Enter a positive whole number.";
return;
}
const significant = text.replace(/^0+/u, "") || "0";
if (significant.length > MAX_DECIMAL_DIGITS) {
els.status.textContent = `Enter a number no wider than ${MAX_INPUT_BITS} bits.`;
return;
}
const N = BigInt(text);
if (N < 1n) {
els.status.textContent = "Enter a positive whole number.";
return;
}
if (bitLength(N) > MAX_INPUT_BITS) {
els.status.textContent = `Enter a number no wider than ${MAX_INPUT_BITS} bits.`;
return;
}
els.go.disabled = true;
els.result.innerHTML = "";
els.result.classList.remove("bad");
els.meter.classList.add("busy");
setBar(0, true);
const t0 = performance.now();
const report = (s) => {
els.status.textContent = (PHASE_TEXT[s.phase] || (() => s.phase))(s);
if (s.phase === "sieving" && s.target) setBar(s.relations / s.target, false);
else setBar(0, true);
};
try {
if (N === 1n) {
render([], 1n, 0);
els.status.textContent = "1 has no prime factors.";
} else {
const grouped = await factorize(N, report);
render(grouped, N, (performance.now() - t0) / 1000);
els.status.textContent = "Done.";
}
} catch (error) {
const message = String(error?.message || error);
els.status.textContent = `Error: ${message} Resetting workers…`;
try {
await restartRuntime();
els.status.textContent = `Error: ${message} Worker runtime was reset.`;
} catch (restartError) {
els.status.textContent =
`Error: ${message} Worker reset failed: ` +
String(restartError?.message || restartError);
}
} finally {
els.meter.classList.remove("busy");
setBar(0, false);
els.go.disabled = !runtimeReady;
}
}
function setBar(fraction, indeterminate) {
els.meter.classList.toggle("indeterminate", indeterminate);
els.bar.style.width = indeterminate ? "100%" : `${Math.min(100, Math.max(0, fraction * 100)).toFixed(1)}%`;
}
els.go.addEventListener("click", run);
els.input.addEventListener("keydown", (e) => {
if (e.isComposing || e.keyCode === 229) return;
if (e.key === "Enter") {
e.preventDefault();
if (!els.go.disabled) run();
}
});
els.input.addEventListener("beforeinput", (e) => {
if (e.isComposing) return;
const lineAction = e.inputType === "insertLineBreak" || e.inputType === "insertParagraph";
const hasLine = typeof e.data === "string" && /[\n\r\u2028\u2029]/u.test(e.data);
if (!lineAction && !hasLine) return;
e.preventDefault();
if (hasLine) insertAtNumberSelection(e.data.replace(/[\n\r\u2028\u2029]/gu, ""));
});
els.input.addEventListener("paste", (e) => {
const pasted = e.clipboardData?.getData("text");
if (pasted == null || !/[\n\r\u2028\u2029]/u.test(pasted)) return;
e.preventDefault();
insertAtNumberSelection(pasted.replace(/[\n\r\u2028\u2029]/gu, ""));
});
els.input.addEventListener("input", () => {
resizeNumberInput();
updateInputInfo();
});
els.input.addEventListener("blur", normalizeNumberInput);
els.rsaBits.addEventListener("input", () => {
els.rsaBitsLabel.textContent = `${els.rsaBits.value} bits`;
});
els.rsaGen.addEventListener("click", () => {
const bits = Number(els.rsaBits.value);
els.rsaGen.disabled = true;
els.rsaGen.textContent = "Generating…";
requestAnimationFrame(() => {
try {
els.input.value = rsaNumber(bits).toString();
resizeNumberInput();
updateInputInfo();
els.input.focus();
} catch (e) {
els.status.textContent = "Generator error: " + (e?.message || e);
} finally {
els.rsaGen.disabled = false;
els.rsaGen.textContent = "Generate";
}
});
});
els.go.disabled = true;
els.status.textContent = "Loading WebAssembly…";
resizeNumberInput();
boot().catch((e) => {
shutdownRuntime();
els.status.textContent = "Failed to load: " + (e?.message || e);
});