Expert factorization laboratory¶
Numerisect is a user interface over existing number-theory libraries. This page documents the expert factorization tools and, for each one, names the routine that performs the computation.
| Operation | Performed by |
|---|---|
| SQUFOF | numerisect-squfof, a C program in this project using GMP |
| Pollard rho, p−1, p+1, ECM, SIQS, NFS, SNFS, Fermat, bounded trial division | YAFU's rho, pm1, pp1, ecm, siqs, nfs, snfs, fermat, trial |
| ECM campaigns | GMP-ECM with -save, -resume, -c, -sigma, -param |
| Staged Mersenne factor hunt | PARI/GP progression search and reconciliation; GMP-ECM -pm1, -pp1, and ECM curves |
| Special forms, algebraic and Aurifeuillean factors, SNFS suitability | PARI/GP ispower, polcyclo, factor |
| Strategy advice and the decision tree | PARI/GP isprime, factor, ispower |
| Algorithm traces | PARI/GP Mod, gcd, forprime |
| Primality certificates | PARI/GP primecert, primecertisvalid, primecertexport |
| General factorization | YAFU, Msieve, CADO-NFS |
Why SQUFOF is written in C here¶
The project policy is to use an existing library routine, and to write optimized C or C++ with GMP or FLINT only when no library provides one. SQUFOF is that case. It was verified absent from every installed engine:
yafu 'squfof' is an unrecognized variable or function in this build
PARI/GP squfof is not a function in function call
Msieve implements MPQS and NFS only
GMP-ECM implements ECM, P-1 and P+1 only
numerisect/native/numerisect_squfof.c therefore supplies it. GMP is used for input
parsing and the range check; the cycle itself runs in 64-bit registers with 128-bit
intermediate products, which is what makes SQUFOF fast. The helper is compiled on
demand into data/tools/bin/numerisect-squfof and rebuilt automatically whenever the
source is newer, exactly like the FLINT zeta helper.
Scope and honest limits¶
Inputs must be below 2^62. Above that, the multiplier-scaled discriminant leaves the 64-bit range and SQUFOF stops being competitive with SIQS in any case; such inputs are rejected with an explicit message rather than answered incorrectly. Route them to YAFU, Msieve, or CADO-NFS.
A run that finds no factor reports status: exhausted. That is inconclusive. It is
not a claim that the input is prime, and Numerisect never presents it as one. On a
sample of 150 random semiprimes below 2^62, the helper split 146 and was inconclusive
on 4, with no incorrect answers.
curl --cookie jar --header 'Content-Type: application/json' \
--data '{"expression":"11111111111"}' \
http://127.0.0.1:8765/api/factor-lab/squfof
SQUFOF is also selectable as the squfof job backend. Both parts of the split are
labelled prime or composite by PARI/GP's isprime; the C helper never labels primality
itself.
Where SQUFOF comes from¶
SQUFOF is a statement about binary quadratic forms: it walks the principal cycle of
forms of discriminant 4kN looking for an ambiguous form, one with a | b or
a = c, whose class is its own inverse. The leading coefficient of such a form in the
principal cycle exposes a factor of N.
The forms laboratory shows that cycle directly. Enumerating the reduced
forms of D = 7268 = 4 · 1817 gives a principal cycle of 28 forms containing
Qfb(23, 46, −56); 23 divides 46, and 23 is exactly the factor of
1817 = 23 × 79 the C helper extracts. That page also covers the continued fractions
behind CFRAC, which the classical-methods page below runs; SIQS still supersedes it at
every size, so it is offered for what it shows rather than as the fast path.
Coppersmith: recovering a factor from part of it¶
Every other method here scales with the size of \(N\). This one scales with how much of a factor is unknown, which is why it reaches sizes nothing else does:
| \(N\) | Factor sought | Bits unknown | Result |
|---|---|---|---|
| 155 digits | 256-bit \(p\) | 100 | recovered |
| 309 digits (1024-bit) | 512-bit \(p\) | 200 | recovered, in milliseconds |
POST /api/factor-lab/coppersmith asks PARI/GP's zncoppersmith for every integer
\(x\) with \(|x| \le X\) such that \(\gcd(N, P(x))\) reaches a stated bound. With
\(P(x) = \text{known} + x\) that is the classical partial-key-exposure attack: supply the
leading bits of a prime factor and the rest follows from lattice reduction, with no
sieving at all. Each root is reported with \(\gcd(N, P(x))\) — the divisor itself — its
cofactor, and PARI's primality verdict on both.
The proven window is part of the answer. The method is valid only while \(X \le \exp\!\left((\log B)^2 / (\deg P \cdot \log N)\right)\), where \(B\) is the lower bound on the divisor. That limit is computed by the engine and reported alongside the result. A request outside it is refused before the engine is called, because PARI raises "bound too large" rather than returning nothing, and because a search that never ran must not be presented as a search that found nothing.
A wrong premise finds nothing. If the supplied leading bits are not in fact the factor's, no root yields a proper divisor and the result says so. Within the window that is evidence about the polynomial and bound given — not about the modulus.
The divisor bound may be left at 0, in which case PARI/GP derives it: for \(\text{known} + x\) the divisor has about as many bits as the known part. No bit length is computed outside an engine.
NFS polynomial selection¶
Selection is the first phase of the number field sieve and the one whose result is
reused: a better polynomial shortens sieving, filtering and linear algebra alike. Both
installed NFS engines expose it, and until now neither set of controls was reachable —
only the choice of CADO params.cNN was.
Msieve, as its own job. The msieve_poly strategy runs selection alone and reports
the polynomial it chose, with the quality metrics Msieve prints and the coefficients in
its own field order, ready to paste into a factor-base file:
| Field | Meaning | Bounds |
|---|---|---|
polyselect_stage |
full, or one stage: stage1, size, root |
only full finishes a polynomial |
degree |
polydegree |
4 to 6 |
deadline |
poly_deadline, seconds |
1 to 86,400 |
min_coeff, max_coeff |
leading-coefficient range for stage 1 | 1 to 10^18, and min ≤ max |
stage1_norm, stage2_norm |
maximum norm per stage | 1 to 10^30 |
min_evalue |
minimum score of a saved polynomial | 1 to 10^30 |
A single stage saves candidates rather than finishing a polynomial, and is reported that way: the job says how many candidates were saved and claims no polynomial. A full run that ends without one is an error, not an empty success.
CADO, inside a factoring run. The same request field tunes selection for the cado
and hybrid strategies, passed as tasks.polyselect.<key> overrides, which
cado-nfs.py accepts on the command line: degree, P, admin, admax, incr,
nrkeep, adrange, nq, sopteffort and ropteffort. Ranges come from the installed
params.cNN files.
Each set is validated against the engine that will receive it, when the job is created rather than when a worker starts, so an Msieve-only parameter cannot be queued for a CADO job or the reverse. The stored options are validated again on a resume.
A selection job reports; it does not factor. Its result is a polynomial, so the
completeness check that every factorization must pass — the factors multiply back to the
input — cannot apply, and the saved report says Report for N rather than stating a false
equation. The same now holds for tune, which measures a crossover: before this it was
marked failed on every successful run.
Classical methods: CFRAC, Lehman and Hart¶
Three methods that no installed engine provides, in numerisect-classic (C/GMP) through
POST /api/factor-lab/classic. None is here to win a race — the engines are faster on
almost any input — and each answers something they cannot:
| Method | Bound | What it is for |
|---|---|---|
| CFRAC (Morrison–Brillhart, 1975) | factor-base bound, default 2,000 | The first subexponential method. Relations come from the continued fraction of √N, so it needs no sieving interval at all, and the dependency it finds is a congruence of squares a reader can check by hand. Factors a 26-digit semiprime in 0.05 s and a 32-digit one in 0.27 s. |
| Lehman (1974) | none; fixed at N^(⅓) | Deterministic, with a proven O(N^(⅓)) bound. Exhausting its range proves no factor of the shape it searches exists, which no probabilistic method here can offer. |
| Hart (2012) | iteration limit, default 10⁶ | One square root, one squaring and one reduction per iteration. Strongest exactly where rho and ECM are weakest: N with two close factors. 1000003 × 1000033 falls out on the first iteration. |
CFRAC expands √N with the standard recurrences, keeps the Q_i that factor completely
over a base of −1 and the primes for which N is a quadratic residue, and reduces the
exponent vectors mod 2 over GF(2). Any dependency gives X² ≡ Y² (mod N) and the split
from gcd(X − Y, N).
Every reported divisor is verified by division before it is printed, and primality of
each part is decided afterwards by PARI/GP isprime — the methods find divisors, never
proofs of primality. Exhausting a bound is reported as exhausted and is explicitly not
evidence that the input is prime; a wall-clock expiry is reported as timeout and
distinguished from both.
Strategy adviser and decision tree¶
PARI/GP tests the input for primality, strips factors below 10^6 by bounded trial division, checks the cofactor for a perfect power, and returns the full decision path alongside the recommended engine.
The expected remaining factor size is a planning estimate, not a proven bound. With no ECM completed it is the balanced-semiprime split, one third of the cofactor's digits. With ECM completed to t digits it is at least t, because ECM to that depth makes a smaller factor unlikely. The response states which basis was used.
Routing thresholds: below 20 digits SQUFOF or SIQS, below 60 digits SIQS, below 95 digits an ECM pretest then SIQS, and CADO-NFS above that.
The path is drawn rather than listed: each question PARI/GP answered is a node, its answer sits beside it, the consequence the engine stated labels the connector to the next node, and the recommendation is the terminal node. Small factors appear on the question that found them. The browser answers no question and infers no step — it draws the steps the response contains, and nothing when there are none. The table of the same rows remains below the diagram for reading or copying.
Special forms, algebraic and Aurifeuillean factors¶
Recognises perfect powers via ispower, values a^k ± 1 by applying ispower directly
to n+1 and n−1 with no base limit, and cyclotomic values Φ_k(a) for bases to 200 and
k to 60. Every algebraic factor reported
is obtained by factoring Φ_n(b) with PARI and is verified to divide the input before
it is shown.
For 2^101 − 1 this returns the SNFS polynomial x^101 − 1, difficulty 30, and the two algebraic factors 7432339208719 and 341117531003194129, which is the known factorization of M101.
A search that exceeds its time budget reports complete: false and is inconclusive: it
does not assert that no special form exists.
Algorithm traces¶
Bounded step traces of Pollard rho, Pollard p−1, and ECM stage 1, computed by PARI/GP so that each step's state, quantity, and gcd can be shown. These exist to teach the algorithms. They are not the production factoring path; Numerisect factors with YAFU, Msieve, GMP-ECM, and CADO-NFS. Traces are capped at 500 steps and mark truncation explicitly.
Batch primality certificates¶
For each supplied factor, PARI/GP decides primality with isprime, builds a certificate
with primecert, and re-checks it independently with primecertisvalid. A composite
input is reported as not prime and not certified, never as a failure. POST
/api/jobs/{id}/certificates does the same for every prime factor of a completed
factorization.
YAFU expert parameters¶
Only flags the installed YAFU build accepts are offered, verified against yafu -h:
| Field | Flag | Field | Flag |
|---|---|---|---|
b1_pm1, b2_pm1 |
-B1pm1, -B2pm1 |
siqs_factor_base |
-siqsB |
b1_pp1, b2_pp1 |
-B1pp1, -B2pp1 |
siqs_trial_bound |
-siqsTF |
b1_ecm, b2_ecm |
-B1ecm, -B2ecm |
siqs_relations |
-siqsR |
rho_max |
-rhomax |
siqs_timeout |
-siqsT |
fermat_max |
-fmtmax |
siqs_blocks |
-siqsNB |
sigma |
-sigma |
siqs_multiplier |
-siqsM |
Every value is range-checked and passed as a separate argv entry. Engine commands are argument arrays; nothing is ever interpolated into a shell string.
They are set under YAFU expert bounds on the factor page, or as yafu_options in a
POST /api/jobs body. A field the server does not know, or a value out of range, is
refused when the job is created rather than queued and then failed; the stored options
are validated again on a resume. Leave a field empty to let YAFU choose.
ECM campaign manager¶
ecm_campaign is a job backend that runs GMP-ECM with explicit parameters and
resumes where it left off. GMP-ECM performs the whole computation, including
deciding whether the factor and cofactor are prime; Numerisect only supplies the
parameters, streams the log, and records the outcome.
| Field | Meaning | Bounds |
|---|---|---|
ecm_b1 |
stage-1 bound | 100 to 10^12 |
ecm_b2 |
stage-2 bound or min-max interval |
GMP-ECM syntax |
ecm_curves |
curves to run (-c) |
1 to 1,000,000 |
ecm_sigma |
curve parameter (-sigma), optionally param:sigma |
GMP-ECM syntax |
ecm_param |
parametrization (-param) |
0 to 3 |
ecm_maxmem |
stage-2 memory cap in MB (-maxmem) |
16 to 1,048,576 |
ecm_stage2_steps |
stage-2 steps (-k); more steps need less memory |
1 to 1,000 |
ecm_base2 |
special base-2 reduction (-base2) |
−10^7 to 10^7 |
ecm_group_order |
known divisor of the group order (-go) |
GMP-ECM expression |
ecm_base2 follows GMP-ECM's own convention: a positive n means the input divides
2^n + 1, a negative one means it divides 2^|n| − 1. It replaces a general division by a
reduction modulo that form, which is the point for Cunningham-style cofactors. GMP-ECM
warns and falls back when the input does not actually divide the stated form.
ecm_group_order is a divisor of q − 1 already known from the number's shape. It is
meaningful for P−1 and P+1, where the group order is q ∓ 1; it is refused for ECM,
where no curve order is known in advance.
Stage-1 residues are written to ecm-residues.txt inside the job directory with
-save. If the job is cancelled and restarted, Numerisect passes -resume with that
file so completed curves are not repeated. Progress is recorded as ecm_curves_done.
Reconciliation. GMP-ECM peels factors off across successive curves and prints each
one as it is found, so the raw list can overlap and need not multiply to the input.
Passing that list to the job unchanged would produce an inconsistent factorization.
PARI/GP therefore reconciles it (fl_reconcile): it divides the candidates out,
reports the prime powers actually present, decides primality, and returns the remaining
cofactor. Nothing is divided out in Python. The recorded parts always multiply back to
the input, and a composite cofactor is flagged so it can be continued as a child job.
The dedicated Mersenne hunt applies the same boundary to \(M_p=2^p-1\). It first
exhausts \(q=2kp+1\) for prime \(p\), or every \(q=2kd+1\) progression for
\(d>1\) dividing an odd composite \(p\), then gives the exact cofactor to
GMP-ECM's P−1, P+1, and ECM modes. PARI/GP rebuilds and reconciles the inventory after
each discovery. The report contains the exact cofactor and says complete only when
every remaining part is rigorously prime; exhausted bounds remain inconclusive.
A campaign that finishes its curves without splitting the input reports an explicit inconclusive failure telling the user to raise B1 or the curve count, or to switch to SIQS or NFS. It never implies the input is prime.
Engine tuning¶
POST /api/factor-lab/tune queues a job that runs YAFU's own tune, which works
through progressively larger inputs and measures where SIQS stops beating NFS on this
machine. Numerisect supplies the thread count and the siever directory, then reads the
tune_info line YAFU writes and reports the crossover it found.
The result is a suggestion. Numerisect never rewrites its own configuration. The response tells you the measured crossover, the threshold currently in force, and the environment variable to set if you agree:
Tuning needs the GGNFS lattice sievers, which YAFU uses for the NFS side of the
measurement. Numerisect searches its managed tools, ~/ggnfs/bin, /usr/local/bin and
/usr/bin, and tests candidate binaries before use. Set NUMERISECT_GGNFS_DIR only to
override that discovery with a particular directory. If no usable siever is found, the
route returns 503 rather than running a partial measurement. A run takes many minutes,
so it is a cancellable job rather than a synchronous request, and the measured crossover
appears as a warning on the finished job.
The measurement reflects this machine, this thread count and these engine builds. It is not a general statement about the engines, and it goes stale when an engine is rebuilt.
API routes¶
POST /api/factor-lab/squfof
POST /api/factor-lab/special-form
POST /api/factor-lab/strategy
POST /api/factor-lab/trace
POST /api/factor-lab/certificates
POST /api/factor-lab/tune
POST /api/jobs/{id}/certificates
Every route saves a plain-text report and returns its exact output/<filename> path.