The fastest method for numbers that fit in a machine word
SQUFOF traverses the cycle of reduced binary quadratic forms of discriminant 4n, generated by the continued fraction expansion of √n, until it finds a form whose first coefficient is a perfect square. Reversing from the square root of that form and continuing the traversal reaches a form yielding a factor. All arithmetic stays within roughly the size of √n, so for n below about 1018 it runs entirely in single precision — which is why nothing else is faster in that range.
Learning objectives
- Describe the forward and reverse phases of SQUFOF.
- Explain why all quantities remain of size √n.
- State the expected running time and the role of multipliers.
- Identify the range in which SQUFOF is the method of choice.
Section 01The method
- Stage 01Forward cycleExpand √n as a continued fraction, generating reduced forms of discriminant 4n. Each step is a small number of single-precision operations.
- Stage 02Detect a square formWatch for a form whose leading coefficient is a perfect square Q = q². This is the signal that a factorisation is within reach.
- Stage 03ReverseConstruct the form with leading coefficient q and traverse the cycle in the reverse direction.
- Stage 04Extract the factorThe traversal reaches a form whose leading coefficient shares a non-trivial factor with n; a GCD completes the factorisation.
Every quantity in the expansion is bounded by about 2√n. For n below 1018 that fits in 64 bits, so the entire algorithm executes in machine arithmetic with no multiprecision library at all. That is the whole source of its speed.
Section 02Performance and multipliers
As with rho, the exponent is 1/4, but the constant factor is much smaller because each step is a handful of machine operations rather than multiprecision arithmetic. When the expansion fails to produce a usable square form, the algorithm is retried on kn for a small multiplier k, which changes the discriminant and hence the cycle.
| Method | Arithmetic | Memory | Best range |
|---|---|---|---|
| Trial division | Single precision | Table of primes | Under 1012 |
| SQUFOF | Single precision | O(1) | 1012 to 1018 |
| Pollard ρ | Multiprecision | O(1) | Factors up to 20 digits |
| ECM | Multiprecision | Moderate | Factors of 20 to 60 digits |
SQUFOF is not a general-purpose method — beyond its single-precision range its advantage evaporates. But within that band it remains the fastest known approach, which is why it survives in library code long after more general methods appeared.
Section 03Relation to the wider theory
SQUFOF is the class-group method of Shanks in disguise. The cycle of reduced forms is the principal cycle in the class group of discriminant 4n, and a square form is an ambiguous form — one of order dividing 2 in the class group. Ambiguous forms correspond precisely to factorisations of the discriminant.
An element of order 2 in the class group of discriminant D yields a splitting of D. SQUFOF finds one by walking the principal cycle; Shanks's class group method finds one by computing the 2-Sylow subgroup directly. The same mathematics, two search strategies.
ReferenceFrequently asked questions
Why does SQUFOF need multipliers?
Because for some n the principal cycle contains no usable square form within a reasonable number of steps. Multiplying n by a small k changes the discriminant and therefore the cycle, and one of a handful of multipliers almost always succeeds.
Is SQUFOF deterministic?
The traversal is deterministic for a given multiplier. The choice of multipliers introduces a search, but the process is systematic rather than random, and the running time is predictable within its range.
Why not use SQUFOF for larger numbers?
Once √n exceeds machine word size, every step requires multiprecision arithmetic and the constant-factor advantage disappears. At that point ECM and the sieves, whose complexity is fundamentally better, take over.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.