01 Primality test
Miller-Rabin
Deterministic below 2⁶⁴. Identifies primes before any factoring work begins.
< 2⁶⁴ O(k · log³ n)
Deterministic · Reproducible · Zero dependencies
Factorisation
that just
works.
A single Python API for the entire factorisation stack — Miller-Rabin, Pollard's Rho, ECM, Quadratic Sieve, SIQS, GNFS — automatically composed into an adaptive pipeline.
Python 3.10+ · MIT licensed · Used in crypto, math-ed & CTF tooling
factorise.py
deterministic · v0.7.0
1 from factorise import factorise, is_prime
2
3 › factorise(123456789)4 3² · 3607 · 3803Pipeline
- Trial divisionskip
- Miller-Rabincomposite
- Pollard p-1—
- Pollard's Rho (Brent)●
- ECM·
- QS / SIQS·
- GNFS·
seeds tried12
wall time8.4 ms
01
0
runtime deps
stdlib only
02
9
algorithms
one API
03
2⁶⁴
verified
Miller-Rabin
04
97%
test coverage
hypothesis props
The pipeline
One API. Nine algorithms.
factorise escalates from fast, cheap methods to heavyweight sieves, stopping the moment a factor is found. You don't pick — it does.
02 Small factors
Trial Division
Strips tiny prime factors first. Bound is configurable; defaults to 10,000.
≤ 10⁴ O(√B / log B)
03 Smooth primes
Pollard p-1
Efficient when p-1 is B-smooth. Bound configurable up to millions.
mid inputs O(B · log B)
04 General purpose
Pollard's Rho (Brent)
Cycle-detection with Brent's improvement. The workhorse of mid-size integers.
< 10¹⁸ O(n^(1/4))
05 Medium factors
ECM
Elliptic curves. Tunable curve count. The bridge between Pollard's and sieves.
~30 digits sub-exp
06 Large semi-primes
Quadratic Sieve
Classical sieve. Reliable up to ~70 digits with a tuned relation budget.
< 70 digits L(½)
07 Self-initializing
SIQS
Knuth-Schroeppel optimised sieve. Faster than QS in practice on typical inputs.
< 80 digits L(½)
08 Massive inputs
GNFS
Sub-exponential. Adapter shells out to `msieve` for the heaviest workloads.
> 80 digits L(⅓)
Built for engineers
Engineered with the same care as the algorithms it runs.
Deterministic by design
Every result is reproducible. No random walks, no probabilistic answers — just correct factorisation every call.
Zero dependencies
Pure Python and the standard library. Drop it into any environment without supply-chain risk.
Adaptive engine
The hybrid router picks the right algorithm for every input size automatically.
Strictly typed
PEP 484 hints across the public API. Plays nicely with mypy, pyright, and your IDE.
Battle-tested
97% coverage with Hypothesis property tests, regression sweeps, and CI-enforced benchmarks.
New
Adaptive hybrid engine
A router inspects your input and dispatches to the optimal stage. Configure thresholds, or just let it pick.
Read the docs Code-first
Read like math.
Write like Python.
A single, consistent API. Functional when you want it concise, a pipeline when you want control. No surprises.
Result objects
Get .factors, .powers and a printable .expression().
CLI included
factorise 123456789 --verbose for ops and debugging.
Reproducible
Optional seeding makes Pollard-Brent retries byte-identical.
01 · One-liner python
from factorise import factorise
result = factorise(123456789)
print(result.expression())
# '3^2 * 3607 * 3803' 02 · Pipeline python
from factorise import FactorisationPipeline, PipelineConfig
pipeline = FactorisationPipeline(
PipelineConfig(trial_division_bound=10_000,
pm1_bound=10**6,
ecm_curves=50)
)
result = pipeline.attempt(10**18 + 9) 03 · Hybrid engine python
from factorise import (
HybridFactorisationEngine, HybridConfig,
)
engine = HybridFactorisationEngine(HybridConfig())
# Routes automatically by input size
result = engine.attempt(n) Get started in seconds
One line of pip.
A lifetime of correct answers.
factorise runs on any modern Python. No compilers, no system libraries, no surprises.
$
pip install factorise $
factorise 123456789 --verbose $
python -c "from factorise import factorise; print(factorise(10**18+9).expression())"
Factorise anything.
Confidently.
Open-source, MIT-licensed, and built for the engineers who can't afford to be wrong.