rusqsieve

rusqsieve is a speed-first, portable Rust/WebAssembly implementation of the self-initializing quadratic sieve. Its primary target is balanced, RSA-style semiprimes from 192 through 256 bits, scheduled across browser Web Workers without shared memory.

On the fixed, factor-verified corpus, rusqsieve currently:

beats FLINT's single-threaded quadratic sieve on every measured native tier from 160 through 240 bits;
factors the 192-, 224-, and 256-bit browser cases in 0.72 s, 5.04 s, and 37.86 s under Node 24.15/V8 with eight workers;
scales the fixed 256-bit case to 13.96 s with 48 workers on the 96-thread reference host.

These results make rusqsieve a plausibly fastest-class browser integer factorizer for balanced 192–256-bit semiprimes, and a particularly strong candidate for the fastest browser SIQS in that range. This is deliberately not an unqualified world-record claim: current Alpertron, Msieve-Wasm, and other browser implementations still need to be run on the same browser, hardware, and fixed corpus. See BENCHMARKING.md for inputs, factors, commands, measurement scope, and the competitor protocol.

The default Natural<16> has a 1024-bit storage capacity. That is not a promise that hard 1024-bit semiprimes are practical; NFS is the appropriate algorithm at that scale.

The crate is not constant-time and must not be used where operand-dependent timing is secret.

Native API

use rusqsieve::{Natural, factor};

let factors = factor(Natural::<16>::from_decimal("360").unwrap()).unwrap();
assert!(factors.verify_product(&Natural::from_u64(360)));

Custom schedulers, including Web Workers, can use engine::prepare, EngineSession::take_jobs, engine::execute, and EngineSession::submit. The portable job kernel never creates threads; the native blocking API schedules the same deterministic polynomial-family work across persistent workers.

Why it is fast in browsers

Numerically target-fitted SIQS polynomials and a double-large-prime relation graph reduce the amount of sieving needed.
Translated, sorted roots and paired stride loops keep division out of the score-write hot path.
Low-weight sparse elimination shrinks the matrix before a compact row-echelon dependency solve.
A scoped Wasm simd128 XOR kernel accelerates linear algebra without applying whole-program SIMD transformations that regress the sieve.
Two-family Worker jobs limit end-of-run overshoot. The pool follows navigator.hardwareConcurrency up to a measured cap of 48 workers.
The deployment preserves Rust/LLVM's speed-optimized Wasm. Binaryen 120 wasm-opt -O3 and -Oz were both measured and rejected because they slowed the 192-bit sieve by roughly 50%.

Browser demo

make docs builds a self-contained WebAssembly demo into docs/ for GitHub Pages (enable Pages on the docs/ folder). It factors a number you type using the same crate compiled to wasm32-unknown-unknown, sieving in parallel across a pool of Web Workers, and renders the result in power notation. Modern browsers use the scoped simd128 linear-algebra kernel; a portable scalar artifact is selected automatically on older engines. make serve previews it locally at http://localhost:8000/.

RSA challenge proof-of-work

The balanced-semiprime SIQS path is the performance-critical deployment target for sign-in proof-of-work. Server-generated challenges should use similarly sized random primes and enter the SIQS coordinator directly through the low-level engine/Worker API. The returned factor must be nontrivial, divide the challenge, and reconstruct the original challenge with its cofactor.

ECM is not currently part of this path. If ECM is added for unbalanced, general-purpose composites, the project policy is:

ECM is opt-in behind a non-default feature and a separate general-purpose Wasm artifact.
The balanced-RSA artifact contains no ECM code or initialization.
The fixed 192/224/256-bit corpus is an A/B regression gate for native time, browser time, Wasm size, and module startup.

This separation is intentional: merely skipping ECM at runtime would still let its additional Wasm download and compilation cost slow a sign-in challenge.

Proof-of-work is resource pricing, not authentication. Bind each challenge to the intended session, expire it, reject replay, and retain the normal authentication mechanism. Never use a modulus belonging to a real RSA key.

Scope

The current pipeline combines trial division, Pollard-Brent rho, primality and perfect-power checks, and SIQS. It does not yet include ECM, so the fastest-class claim is specifically for balanced semiprimes. Unbalanced 192–256-bit composites with medium-size factors remain the main general-factorization gap.