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, including browser execution across independent Web Workers without shared memory.

Version 0.2 exposes a deliberately small, safe Rust API and an opaque native C ABI. SIQS relations, matrix kernels, worker packets, scheduler state, primality policy, and mutable limbs remain private implementation details.

Performance status

On the fixed, factor-verified corpus and reference host, rusqsieve currently:

beats FLINT's single-threaded QSieve on every measured native tier from 160 through 240 bits;
factors the 192-, 224-, and 256-bit browser-shaped 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 strong candidate for the fastest browser SIQS in that range. This is intentionally not an unqualified world-record or "fastest general factorizer" claim: current competitor implementations still need same-browser, same-hardware measurements.

BENCHMARKING.md contains the inputs, factors, commands, measurement scope, and competitor protocol. The crate is not constant-time and must not be used where operand-dependent timing reveals a secret.

Installation

Add the Rust library:

cargo add rusqsieve@0.2.0

Install the native CLI:

cargo install rusqsieve --version 0.2.0

Or build the optimized native library and CLI from source:

make

The library is emitted as an rlib, static library, and platform shared library.

Rust API

The blocking factorization functions are available on Unix and Windows:

use rusqsieve::{FactorConfig, Natural, Parallelism, factor_with};

let input = Natural::<4>::from_decimal("360").unwrap();
let config = FactorConfig::default().with_parallelism(
    Parallelism::threads(4).expect("a nonzero worker count"),
);
let factors = factor_with(input.clone(), config).unwrap();

assert_eq!(factors.distinct_len(), 3);
assert_eq!(factors.total_len(), 6);
assert_eq!(
    factors
        .expanded()
        .map(ToString::to_string)
        .collect::<Vec<_>>(),
    ["2", "2", "2", "3", "3", "5"],
);
assert!(factors.verify_product(&input));

Use factor for defaults, factor_with for configuration, or factor_with_progress for read-only progress snapshots and cooperative cancellation. The ordinary no-observer path is separately monomorphized so callback and progress-clock machinery is compiled out.

The default Natural has a 1024-bit storage capacity. This is not a claim that hard 1024-bit semiprimes are practical; NFS is the appropriate algorithm at that scale. Arithmetic operators on Natural wrap at capacity, while checked_* methods report overflow.

All supported public items are covered by rustdoc, enforced with deny(missing_docs). The complete 0.2 contract and implementation architecture are documented in SPEC.md; breaking changes from 0.1 are summarized in CHANGELOG.md.

Native C API

Unix and Windows builds export a minimal decimal-string interface from the static and shared libraries:

#include <stdio.h>
#include "rusqsieve.h"

int main(void) {
    rusqsieve_factors *factors = rusqsieve_factors_new();
    if (factors == NULL)
        return 1;

    int status = rusqsieve_factor("360", 0, factors);
    if (status == RUSQSIEVE_OK) {
        for (size_t i = 0; i < rusqsieve_factors_len(factors); ++i)
            puts(rusqsieve_factors_get(factors, i));
    }

    rusqsieve_factors_free(factors);
    return status;
}

The result type is completely opaque and Rust-owned. Factor strings are borrowed until the next call using that result or until rusqsieve_factors_free; callers must not free individual strings. threads == 0 selects available parallelism capped at 48.

Install libraries, CLI, header, and pkg-config metadata under /usr/local:

sudo make install

The prefix and staging root are overridable:

make install PREFIX=/usr DESTDIR="$pkgdir"

BINDIR, LIBDIR, INCLUDEDIR, and PKGCONFIGDIR may also be overridden. See rusqsieve.h for the complete ownership, status, and thread-safety contract.

Browser and WebAssembly

Build the self-contained browser demo:

make docs
make serve

The generated docs/ directory can be deployed directly to GitHub Pages. It contains scalar and SIMD128 Wasm modules; the frontend attempts SIMD first and falls back to scalar on older engines.

The browser architecture uses one coordinator Wasm instance and an independent Wasm instance in each Web Worker. Workers rebuild the same deterministic SIQS context and return serialized polynomial-family relations. The coordinator merges families deterministically, filters the matrix, solves for dependencies, and extracts a verified nontrivial factor.

Notable performance work includes:

target-fitted SIQS polynomials and Gray-code root updates;
translated, sorted roots and a paired root-difference stride loop;
byte logarithmic scores with word-at-a-time candidate rejection;
multiply-shift-gated survivor division;
single/double-large-prime relation combination;
deterministic low-weight sparse matrix elimination;
compact residual row-echelon solving;
scoped Wasm SIMD128 XOR acceleration;
two-family jobs and a measured 48-worker cap.

Whole-program Wasm SIMD and Binaryen wasm-opt -O3/-Oz are not used because they regressed the measured sieve.

Command-line interface

qs-factor reads one unsigned decimal integer from standard input and prints the sorted prime factors, including repetitions, one per stdout line:

printf '%s\n' 360 | qs-factor --threads auto --progress auto

Progress and elapsed time are written only to stderr, keeping stdout machine-readable. The factorization of one succeeds with no factor lines; zero and malformed input are errors.

RSA challenge proof-of-work

The balanced-semiprime SIQS path is the performance-critical deployment target for sign-in proof-of-work. Challenges must use fresh, similarly sized random primes, be bound to the intended session, expire, and be replay-protected. A returned factor must be nontrivial, divide the challenge, and reconstruct it with its cofactor.

Proof-of-work is resource pricing, not authentication. Retain the normal authentication mechanism, and never use a modulus belonging to a real RSA key.

ECM is not part of the 0.2 default path. If added later, it must be opt-in behind a non-default feature and shipped in a separate general-purpose Wasm artifact. The balanced-RSA artifact must contain no ECM code or initialization; the fixed 192/224/256-bit corpus remains an A/B gate for runtime, download size, compilation, startup, and code-cache footprint.

Scope and limitations

The current pipeline combines trial division, Pollard–Brent rho, primality and perfect-power checks, and SIQS. It is strongest on balanced semiprimes. Unbalanced 192–256-bit composites with medium-size factors remain the main general-factorization gap because ECM is absent.

The current linear algebra uses structured sparse elimination followed by a compact row-echelon solve; it is not a true block-Lanczos recurrence. That becomes a future concern for matrices beyond the current practical range.

Release builds

build-release.sh creates versioned archives for Linux GNU/musl, FreeBSD, Windows MSVC, Apple arm64, and WebAssembly:

SDKROOT=../MacOSX15.4.sdk ./build-release.sh

It uses cross-rs for Linux and FreeBSD, xwin for MSVC, cargo-zigbuild for Apple, and native Cargo for Wasm. Native archives contain the target-appropriate libraries, CLI, C header, pkg-config metadata, licenses, changelog, and an elevation-aware installer. The Wasm archive contains the deployable frontend and both scalar and SIMD128 modules.

Pass target triples as arguments to build a subset. Run ./build-release.sh --help for the supported list and environment overrides.

License

Licensed under Apache-2.0 OR MPL-2.0; see LICENSE-APACHE and LICENSE-MPL.

rusqsieve 0.2.0