Modern Factoring Methods
The Continued Fraction Factorisation Method
CFRAC: generating small quadratic residues from the continued fraction expansion, and the congruence-of-squares framework it established.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0666
The continued fraction method was the first sub-exponential factoring algorithm to be practical. It established the framework — collect relations, do linear algebra, extract a congruence of squares — that the quadratic and number field sieves inherit.
The framework
If two numbers have equal squares modulo the target but are not congruent up to sign, their difference shares a non-trivial factor with the target.
Generating small residues
The convergents of the continued fraction expansion of the square root of the target produce numerators whose squares reduce to unusually small residues.
The algorithm
The continued fraction factoring method
- ExpandCompute the continued fraction of the square root of the target.
- Collect residuesEach convergent gives a residue to test.
- Test smoothnessTrial divide against the factor base.
- Build the matrixRows are exponent vectors modulo two.
- Find dependenciesA kernel vector gives a product that is a perfect square.
- ExtractForm the congruence of squares and take a GCD.
Exponents modulo two
Why sieving beat it
| Aspect | CFRAC | Quadratic sieve |
|---|---|---|
| Residue size | Smaller — better smoothness odds | Larger, growing across the interval |
| Smoothness testing | Individual trial division | Bulk sieving |
| Net effect | Superseded | Much faster in practice |
Historical importance
CFRAC factored numbers previously out of reach and demonstrated that the relation-collection framework worked. Its structure survives unchanged in every later sieve.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.