Shanks's SQUFOF Factoring Method

Executive summary

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 10¹⁸ 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.

Why everything stays small

Every quantity in the expansion is bounded by about 2√n. For n below 10¹⁸ 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

O(n^1/4)expected running time

O(1)memory

≤ 10¹⁸range of single-precision operation

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.

Comparison in the mid range
Method	Arithmetic	Memory	Best range
Trial division	Single precision	Table of primes	Under 10¹²
SQUFOF	Single precision	O(1)	10¹² to 10¹⁸
Pollard ρ	Multiprecision	O(1)	Factors up to 20 digits
ECM	Multiprecision	Moderate	Factors of 20 to 60 digits

Still used, in a narrow band

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.

Ambiguous forms are factorisations

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.

Handbook application: from concept to controlled practice

Purpose. This expanded section turns the original page into a practical handbook. It preserves the supplied material and adds a repeatable way to apply, check and review Shanks's SQUFOF Factoring Method. It does not replace a contract, legislation, a controlled standard, competent engineering judgement or specialist advice.

The operating aim is to turn a compact mathematical statement into a usable chain of definitions, claims, examples and checks. Read the original explanation first, then use the workflow and checks below to convert knowledge into evidence.

Treat Shanks's SQUFOF Factoring Method as a network of definitions and implications, not as a list of formulas. The working vocabulary on this page—squfof, method, square, section, factoring—should be made explicit before any proof or computation begins. Record the ambient set or structure, the permitted operations and the equality or equivalence relation in use. A compact theorem often changes meaning when the base field, finiteness condition, commutativity assumption or direction of an action changes.

For a proof, write the hypotheses as a checklist and mark the line at which each one is used. For a computation, state the representation of the input, the arithmetic model, the termination condition and the output invariant. For a classification problem, distinguish existence from uniqueness and distinguish an object from its representation. These separations prevent a correct local calculation from being mistaken for the general result.

A useful worked example should be small enough to inspect completely but rich enough to exercise the main mechanism. Compute the result in two ways where practical: symbolically and by substitution, structurally and numerically, or directly and through a normal form. Then include one near-miss example in which a hypothesis fails. The contrast explains why the theorem is shaped as it is and gives the reader a diagnostic pattern for later problems.

Verification is part of the mathematics. Check domains and codomains, substitute proposed solutions, test identity and zero cases, compare dimensions or cardinalities, and confirm that maps respect the required operations. In numerical work, report precision, conditioning and a residual rather than digits alone. In algorithmic work, separate mathematical correctness from implementation complexity and resource limits.

Step-by-step operating method

Fix the setting. State the objects, ambient structure, notation and assumptions before manipulating symbols.
Separate claims. Distinguish definitions, hypotheses, conclusions, equivalent conditions and consequences.
Choose a method. Select proof, construction, calculation or algorithm according to the question actually asked.
Work a small case. Use the smallest non-trivial example to expose the mechanism and test edge behaviour.
Verify independently. Substitute back, check invariants, test boundary cases or use an alternative derivation.

Worked-example protocol

Illustrative method—not a source theorem. Start with a small admissible input and list the definitions it must satisfy. Carry out each transformation on a separate line, citing the property that permits it. Preserve exact values until approximation is necessary. At the end, verify the output against the original definition and one invariant such as dimension, degree, determinant, order, norm or residual. Then alter one hypothesis and observe which step ceases to be valid. This protocol creates a reusable example without inventing a theorem-specific numerical answer.

Stage	Record	Quality check
Input	Objects, domain, notation, assumptions	Every symbol is defined
Method	Permitted operation or cited result at each step	All hypotheses hold
Output	Exact result and representation	Correct type, domain and form
Verification	Substitution, invariant or alternative derivation	Independent agreement
Boundary test	Zero, identity, degenerate or failed hypothesis	Scope is understood

Common failure modes and recovery actions

1. Watch for

Using a theorem without checking every hypothesis.

Recovery: Return to the governing definition or requirement and restate the decision in one sentence.

2. Watch for

Treating a suggestive example as a proof of the general case.

Recovery: Separate evidence from assumption, assign an owner and set a date for validation.

3. Watch for

Changing notation or conventions part-way through an argument.

Recovery: Run a small counterexample, boundary test, pilot or independent check before proceeding.

4. Watch for

Hiding a division-by-zero, convergence, finiteness or commutativity assumption.

Recovery: Record the consequence, decision and rationale, then update the controlled baseline.

5. Watch for

Reporting a computed result without a residual, substitution or structural check.

Recovery: Escalate when the issue affects safety, compliance, acceptance, material value or an agreed tolerance.

Review checklist

Can every symbol be traced to a definition or prior result?
Which hypothesis does each major step use?
Does the method cover zero, identity, degenerate and boundary cases?
Can the conclusion be checked by a second representation or calculation?
Are mandatory requirements distinguished from recommendations and illustrative values?
Are sources, assumptions, units, dates and versions recorded closely enough to reproduce the decision?
Have safety, legal, ethical, stakeholder and operational consequences been considered at the appropriate level?
Is there a named owner and a trigger for review, escalation, change or retirement?

Questions for deeper application

What is the most important distinction a practitioner must preserve when applying Shanks's SQUFOF Factoring Method?