Self-Initializing Quadratic Sieve · C# / .NET 10

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 qs at the number you want factored:

dotnet run -c Release --project QS/QS.csproj -- 150478035830330483870744795468187571781390056303346096534807

You'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.

View source on GitHub How the sieve works →

Real numbers, real hardware

Each row below is a single end-to-end factorization of a fresh, balanced semiprime — two prime factors of equal length, the hardest split for a given digit count — run with the default auto-tuned parameters. No cherry-picking, no warm caches.

AMD Ryzen 7 5800X · 8C/16T 32 GB RAM .NET 10 · Release build default parameters

Composite	Factor split	Wall-clock time
`C25`	13 × 13 digits	0.8 s
`C35`	18 × 18 digits	0.6 s
`C45`	23 × 23 digits	1.6 s
`C55`	28 × 28 digits	2.9 s
`C65`	33 × 33 digits	6.1 s
`C75`	38 × 38 digits	22.8 s
`C85`	43 × 43 digits	3 m 17 s
`C93`	47 × 47 digits	11 m 7 s

These are timings for individual factorizations, not guarantees for every integer of that size. The quadratic sieve's cost is dominated by the size of the number, but it also varies from one composite to the next, and the sub-second rows are dominated by process start-up and JIT warm-up rather than the sieve itself. Treat the table as a feel for the growth curve on ordinary desktop hardware — each step of ten digits multiplies the work several-fold — not as a benchmark you should expect to reproduce to the second.

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.

See the workbench

The SIQS.UI Blazor app is the easiest way to explore the system — start a run, watch every phase, browse archived jobs and their artifacts, hand sieving out to other machines, and learn the method. Here is what it looks like before you clone anything.

The Factorize page: a target-N field, an advanced-parameters panel, and a recent-jobs list. — **Factorize.** Start a one-shot run from the browser. Every tuning knob has a digit-size default and an override behind *Advanced parameters*.

The Jobs list showing seven completed factorizations with sizes, durations, and factors. — **Jobs.** Every factorization, live and archived — target size, status, wall-clock duration, and the discovered factors, filterable by kind and status.

A job-details page: a five-phase timeline, the factor result, and a per-phase counters table. — **Job details.** A per-phase timeline with elapsed times, the final congruence-of-squares result, and the complete counter set every stage recorded — factor-base size, relations found, matrix dimensions, Block Lanczos dependencies, and more.

The Distributed page: submit a composite and download self-contained Windows and Linux sieve clients. — **Distributed.** Submit a job whose sieving is shared across machines, and download self-contained **Windows x64** and **Linux x64** workers — no .NET runtime required on the worker.

Sieve School: a guided tour and a quiz, with a table mapping tour steps to pipeline phases. — **Sieve School.** A guided tour through a worked factorization and a randomized quiz, each step linked to the pipeline phase it explains.

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.

X² ≡ Y² (mod N)

The whole machine exists to build one congruence of squares. When X ≢ ±Y, 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.

One command, 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          # Linux

The distributed API is designed for a trusted LAN. If you expose a server beyond one, put it behind authentication, TLS, firewalling, and rate limits.

Get 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

Full README & source Understand the algorithm →

SIQS.NET is intended for education, experimentation, benchmarking, and factoring integers you are authorized to factor. It owes an enormous debt to msieve and YAFU — extraordinary factoring software well worth studying.

Factor numbers.Understand how.