# 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](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:
```sh
cargo add rusqsieve@0.2.0
```
Install the native CLI:
```sh
cargo install rusqsieve --version 0.2.0
```
Or build the optimized native library and CLI from source:
```sh
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:
```rust
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](SPEC.md); breaking changes from 0.1 are summarized
in [CHANGELOG.md](CHANGELOG.md).
## Native C API
Unix and Windows builds export a minimal decimal-string interface from the
static and shared libraries:
```c
#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`:
```sh
sudo make install
```
The prefix and staging root are overridable:
```sh
make install PREFIX=/usr DESTDIR="$pkgdir"
```
`BINDIR`, `LIBDIR`, `INCLUDEDIR`, and `PKGCONFIGDIR` may also be overridden.
See [rusqsieve.h](rusqsieve.h) for the complete ownership, status, and
thread-safety contract.
## Browser and WebAssembly
Build the self-contained browser demo:
```sh
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:
```sh
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:
```sh
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](LICENSE-APACHE) and
[LICENSE-MPL](LICENSE-MPL).