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.