Factor numbers.
Understand how.
An open-source implementation of a classic integer-factorization algorithm.
SIQS.NET is both a factorization workbench and an explorable implementation of the self-initializing quadratic sieve. It routinely factors composites in the 85–100 digit range on ordinary hardware — and every phase of the algorithm is visible, inspectable, and documented.
TL;DR — I just want to factor stuff
⏱ 2-minute read-
Install the .NET 10 SDK, then clone and build:
git clone https://github.com/JesHansen/siqs.net.git cd siqs.net dotnet build -c Release SIQS.slnx -
Point
qsat the number you want factored:dotnet run -c Release --project QS/QS.csproj -- 150478035830330483870744795468187571781390056303346096534807You'll see live progress for each phase — factor base, sieving, filtering, linear algebra, square root — and at the end the factorization:
[factor base] size, multiplier, and bound [sieving] relations found / needed (live) [filtering] matrix size before and after pruning [linear algebra] null-space dependencies found [square root] dependency attempts <N> = <factor1> * <factor2> job workspace: runs/<job-id> -
Prefer buttons over terminals? Start the web workbench and open
http://localhost:5078:dotnet run -c Release --project SIQS.UI/SIQS.UI.csproj --urls "http://localhost:5078"
That's the whole workflow. A prime input exits cleanly with “no non-trivial
factor”; Ctrl+C cancels a run and leaves its artifacts resumable with
--resume. Sensible defaults are chosen from the digit size of your number —
no tuning required. Curious what's happening under the hood?
Read the deep dive.
What you can do with it
A single solution that spans a working factorizer, a live web workbench, distributed sieving, and interactive learning material.
Factor an integer
Run a one-shot factorization from the qs command line or the web
Factorize page. Every parameter — factor-base bound, multiplier,
sieve interval, large-prime bounds, parallelism — has a sensible digit-size default
and a CLI override.
Watch a live run
Phase status, elapsed time per phase, relation counters, matrix dimensions, and run artifacts are all retained for inspection in the Jobs view. Interrupted runs resume from their workspace.
Distribute the sieve
Sieving dominates the cost, so the server can lease disjoint slices of polynomial work to volunteer clients over HTTP. Workers independently rebuild and verify the job parameters before sieving a single value.
Self-contained workers
Download single-file sieve clients for Windows x64 and Linux x64 straight from the workbench — no .NET runtime required on the worker machine.
Sieve School
A guided tour through a worked factorization, an animated sieve window, topic quizzes, and a historical timeline from Fermat and Kraitchik through Pomerance and RSA-129.
Stage-by-stage tools
Five focused CLI tools — qs-fb, qs-sieve,
qs-filter, qs-linalg, qs-sqrt — run each
pipeline phase standalone over plain text artifacts you can read and diff.
The pipeline at a glance
A factorization passes through five phases. Each is its own library with its own CLI tool, and each hands the next a plain UTF-8 text file — parsable by human and machine alike. The deep dive explains the mathematics of every step.
gcd(X − Y, N) reveals a factor.
Factor base qs-fb → factor_base.txt
Pick a multiplier, then collect the primes p for which the scaled target is a quadratic residue — the only primes that can ever divide a sieve value.
Sieving qs-sieve → relations_*.txt
Generate families of polynomials and sieve them over a symmetric interval, adding logarithmic weights where factor-base primes divide. Survivors become relations; near-misses become large-prime partials. This is the hot path — and the part that can be distributed.
Filtering qs-filter → filtered_matrix.txt
Combine partial relations through large-prime graph cycles, remove duplicates and singletons, and trim the result into a lean sparse matrix over GF(2).
Linear algebra qs-linalg → dependencies.txt
Run Block Lanczos over GF(2) to find non-empty sets of relations whose exponent vectors XOR to zero — each one a candidate congruence of squares.
Square root qs-sqrt → factors.txt
Reconstruct X and Y from a dependency, verify every exponent sum is even, and take GCDs against N. A non-trivial answer is your factor.
qs.exe, runs all five phases in a single process with live
console progress — the per-phase tools exist so you can study, debug, or benchmark any
stage in isolation against hand-crafted inputs.
The toolchain
The solution is deliberately divided by algorithmic responsibility — phase libraries with typed APIs, thin CLI front-ends, a shared contracts library, and an orchestration pipeline that both the console capstone and the web UI sit on top of.
| Component | What it is |
|---|---|
qs.exe | The capstone: factors a number end-to-end in one process with live progress, resumable workspaces, and meaningful exit codes. |
qs-fb, qs-sieve, qs-filter, qs-linalg, qs-sqrt | Standalone per-phase tools that read and write the documented text artifacts. |
SIQS.UI | Blazor web workbench: Factorize, Jobs & artifacts, Distributed coordination, Sieve School, and history. |
SIQS.Pipeline | Orchestration library — owns defaults, runs phases in order, tracks the job workspace, reports progress. |
SIQS.Overlord + qs-sieve-client | Distributed sieving: the coordinator leases work slices; the self-contained client verifies, sieves, and uploads relations. |
Factorbase, Sieving, Filtering, LinearAlgebra, SquareRoot | The five phase libraries — the actual mathematics, each with its own xUnit test project. |
CompositeGenerator | Generates fresh RSA-shaped semiprime targets: CompositeGenerator.exe 55 | qs.exe. |
SIQS.Benchmarks | BenchmarkDotNet harness isolating the hot kernels — Block Lanczos multiplies and the sieve fill/scan seam. |
Everything is a text file
Every phase writes plain UTF-8 artifacts — factor_base.txt,
relations_0000.txt, filtered_matrix.txt,
dependencies.txt, factors.txt — with documented, versioned
header contracts. You can open any intermediate state of a factorization in a text
editor, diff two runs, or feed a hand-edited file back into the next phase.
Distributed sieving
Sieving is embarrassingly parallel: disjoint polynomial families can be processed on different machines with no coordination beyond handing out assignments. SIQS.NET exploits that.
The Overlord coordinates
The server owns the job: it leases slices of polynomial indices, validates every uploaded relation, re-issues abandoned leases, and runs filtering, linear algebra, and square root centrally once enough relations arrive.
Workers verify, then trust
A client performs a protocol handshake and independently reconstructs the factor base and sieving parameters from the job descriptor. If its reconstruction disagrees with the server's, it declines the job.
Drop-in replacement
The distributed sieve produces byte-compatible relation artifacts, so the rest of the pipeline can't tell the difference between one machine and twenty.
# On each worker — download from the server's Distributed page, then:
.\qs-sieve-client.exe http://your-siqs-server:5078 # Windows
./qs-sieve-client http://your-siqs-server:5078 # LinuxGet started
Everything runs from a fresh clone with the .NET 10 SDK — no other dependencies.
# Build and test everything
dotnet build SIQS.slnx
dotnet test --solution SIQS.slnx
# Factor from the command line (add --parallelism 1 for reproducible artifacts)
dotnet run -c Release --project QS/QS.csproj -- <your composite>
# Explore the full workbench in a browser
dotnet run -c Release --project SIQS.UI/SIQS.UI.csproj --urls "http://localhost:5078"
# Generate a fresh 55-digit test target and factor it in one line
CompositeGenerator.exe 55 | qs.exe