The Continued Fraction Factoring Method

Q: Why must the factor base exclude primes with (n/p) = -1?

Because Qi is congruent to a square times ±1 modulo n, so any prime dividing it must have n as a quadratic residue. Including the others would waste half the trial divisions on primes that can never divide a candidate.

Q: What if the GCD comes out trivial?

It happens about half the time, when X is congruent to plus or minus Y. Use another kernel vector; the vectors are independent, so a handful of surplus relations makes repeated failure vanishingly unlikely.

Q: Is CFRAC ever preferable now?

Rarely. Its residues are smaller than the quadratic sieve's, which helps for smaller n, but the inability to sieve outweighs that in nearly all cases. It remains of interest chiefly for understanding the lineage of the sieves.

Executive summary

The first algorithm to break the exponential barrier

The convergents of √n produce values Q_i that are congruent to squares modulo n and are unusually small — below 2√n. Small numbers are more likely to be smooth, so many of them factor completely over a fixed factor base. Combining a suitable subset by linear algebra over GF(2) produces a square on both sides, and a GCD splits n. This is the template every later sieve follows.

Learning objectives

Generate small residues from the continued fraction expansion.
Explain the role of smoothness and the factor base.
Set up and solve the GF(2) linear algebra step.
State the complexity and compare with the quadratic sieve.
Explain why sieving replaced trial division of residues.

Section 01Generating small residues

The convergents A_i/B_i of √n satisfy

A_i² − nB_i² = (−1)ⁱ⁺¹Q_i+1, |Q_i| < 2√n

So A_i² ≡ ±Q_i+1 modulo n, giving a congruence in which the right-hand side is guaranteed small. That bound is the whole advantage: a number below 2√n is vastly more likely to be smooth than a random residue modulo n.

Small is the point

Every sub-exponential factoring algorithm works by producing small values whose smoothness can be exploited. CFRAC gets them from the continued fraction; the quadratic sieve gets them from a polynomial near its root; the number field sieve gets them from two polynomials at once. The rest of the machinery is essentially the same.

Section 02Smoothness and the factor base

AlgorithmCFRAC relation collectionin: n, bound B → out: smooth relations

Choose a factor base of primes p ≤ B for which n is a quadratic residue, together with −1. Primes with (n/p) = −1 can never divide a Q_i.
Expand √n, generating pairs (A_i, Q_i).
Attempt to factor each Q_i completely over the factor base by trial division.
Keep the smooth ones; record the exponent vector modulo 2 together with A_i.
Continue until there are more relations than factor base elements.

Trial division is the bottleneck

Each candidate must be trial divided by the whole factor base, and most candidates are not smooth. The wasted effort on non-smooth candidates dominates the running time, and removing it is exactly what sieving achieves.

Section 03The linear algebra step

Each relation is a vector over GF(2) recording the parity of each prime's exponent. A subset summing to zero corresponds to a product of the Q_i that is a perfect square.

X² ≡ Y² (mod n) ⇒ gcd(X − Y, n) is a factor, with probability at least 1/2

Stage 01Build the matrixRows are relations, columns are factor base primes, entries are exponent parities.
Stage 02Find the kernelGaussian elimination over GF(2), or Block Lanczos and Wiedemann for large sparse systems.
Stage 03Form X and YX is the product of the A_i; Y is the square root of the product of the Q_i, computed from the halved exponents.
Stage 04Take the GCDIf it is trivial, use another kernel vector — each independent vector gives an independent chance.

Collect surplus relations

Each kernel vector gives a factorisation with probability about one half. Collecting several more relations than strictly necessary yields several independent kernel vectors, making failure negligible.

Section 04Complexity and legacy

L[1/2, √2]CFRAC complexity

L[1/2, 1]quadratic sieve complexity

L[1/3]number field sieve complexity

CFRAC was the first algorithm to achieve sub-exponential factoring and held the factoring records of the 1970s and early 1980s. It was superseded by the quadratic sieve, which produces candidates that can be tested for smoothness by sieving rather than by trial division — a change in the smoothness testing, not in the underlying strategy.

What actually changed

CFRAC's residues are smaller than the quadratic sieve's, which is an advantage. But its candidates arrive one at a time and must each be trial divided, whereas the quadratic sieve's arrive in an arithmetic progression that can be sieved. Sieving wins decisively.

ReferenceFrequently asked questions

Why must the factor base exclude primes with (n/p) = -1?

Because Q_i is congruent to a square times ±1 modulo n, so any prime dividing it must have n as a quadratic residue. Including the others would waste half the trial divisions on primes that can never divide a candidate.

What if the GCD comes out trivial?

It happens about half the time, when X is congruent to plus or minus Y. Use another kernel vector; the vectors are independent, so a handful of surplus relations makes repeated failure vanishingly unlikely.

Is CFRAC ever preferable now?

Rarely. Its residues are smaller than the quadratic sieve's, which helps for smaller n, but the inability to sieve outweighs that in nearly all cases. It remains of interest chiefly for understanding the lineage of the sieves.

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 The Continued Fraction 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 The Continued Fraction Factoring Method as a network of definitions and implications, not as a list of formulas. The working vocabulary on this page—section, continued, fraction, factoring, cfrac—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 The Continued Fraction Factoring Method?