Classical Primality and Factoring
Shanks's Square Forms Factorisation (SQUFOF)
SQUFOF: factoring by finding a square form in the cycle of an indefinite quadratic form, and why it excels for small inputs.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0656
SQUFOF factors an integer by traversing the cycle of an indefinite quadratic form until a square form appears. It is remarkably efficient for numbers up to about eighteen digits and uses essentially no memory.
The method
Traverse the cycle of reduced indefinite forms of discriminant equal to the number, or a small multiple. When a form with square first coefficient appears, reversing the traversal from its square root yields a factor.
SQUFOF
- Set upForm the principal indefinite form of the appropriate discriminant.
- Traverse forwardApply the reduction operator, watching for a square first coefficient — see indefinite reduction.
- Take the square rootConstruct the form with the square root as its first coefficient.
- Traverse backwardFrom that form until the cycle returns to an ambiguous form.
- Read the factorThe ambiguous form gives the factorisation.
Why it is fast in practice
| Property | Value |
|---|---|
| Complexity | Fourth root of the number |
| Memory | Essentially none |
| Arithmetic | Single-precision for inputs up to about 18 digits |
| Constants | Very small |
Multipliers
The range
Where it is used
SQUFOF is the standard method for the small factorisations that appear as subroutines throughout: splitting cofactors during smoothness testing, factoring small norms in ideal factorisation, and clearing residues in sieve methods.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.5.5. 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.