Once an integer is known to be composite, the next question is harder: can we actually find a nontrivial factor?
Primality testing and factorisation are closely related but computationally different. A compositeness witness can sometimes show that n is not prime without revealing any divisor. Factorisation asks for more: recover integers p and q with 1<p,q<n and n=pq, then continue until the required prime decomposition is obtained.
This guide develops the main algorithmic ideas behind factorisation: direct search, difference of squares, smoothness, pseudorandom collisions, gcd extraction, and the transition from elementary methods to the large-scale algorithms used for difficult inputs. The goal is not merely to name algorithms, but to understand what structural weakness each one is waiting to exploit.
This is Guide 4 in the Bukit Timah Tutor Computational Number Theory series. Return to the BTT Mathematics Hub for the wider Mathematics route.
Composite is a diagnosis. A factor is a recovered cause.
1. What integer factorisation asks for
Every integer n>1 has a prime factorisation unique up to order:
n = p₁^{e₁}p₂^{e₂}…p_k^{e_k}.
The fundamental theorem of arithmetic guarantees that this decomposition exists and is unique. It does not tell us how efficiently to find it.
That gap between existence and computation is the central theme of algorithmic number theory. A theorem may promise that an object is there; an algorithm must still locate it with finite resources.
2. Verification is easy once factors are known
If someone claims that 8051=83·97, verification is immediate: multiply 83 by 97 and check the product. If a complete prime factorisation is claimed, also verify that every listed factor is prime and that their powers multiply to n.
This creates the familiar asymmetry:
Finding a factor can be difficult; checking a proposed factor is cheap.
Many computational problems share this shape. Number theory gives especially clear examples because the certificate is so concrete.
3. Trial division: the baseline algorithm
The simplest factorisation method tests candidate divisors. If no divisor up to √n is found, n is prime.
factor_by_trial(n):
remove factors of 2
for each odd d with d·d ≤ n:
while n mod d = 0:
output d
n = n / d
if n > 1:
output n
A better implementation tests prime divisors rather than all odd integers. Trial division is excellent for small factors and as a preprocessing stage, but its worst-case search reaches about √n. Measured against the bit length of n, that becomes exponential growth.
4. Small-factor removal is still strategically useful
The fact that trial division is poor for hard large instances does not make it useless. Removing small prime factors early can simplify later algorithms dramatically.
- Even numbers are factored by 2 immediately.
- Divisibility by a table of small primes is cheap.
- Repeated powers can be stripped before more sophisticated work.
- If the remaining cofactor becomes prime, the process can stop.
Good computational pipelines often use cheap algorithms first, not because those algorithms solve every case, but because they eliminate easy cases at low cost.
5. Fermat factorisation: turn multiplication into a difference of squares
For odd n, suppose n=uv with u≤v. Then
n = uv = [(u+v)/2]^2 − [(v−u)/2]^2.
So if we can find integers x and y satisfying
n=x²−y²=(x−y)(x+y),
we have found factors.
Fermat’s method starts at x=⌈√n⌉ and increases x until x²−n becomes a perfect square.
Worked example: factor 5959
√5959 is a little above 77. Start with x=78.
78² − 5959 = 125 not a square 79² − 5959 = 282 not a square 80² − 5959 = 441 = 21².
Therefore
5959 = 80² − 21²
= (80−21)(80+21)
= 59·101.
Fermat factorisation works especially well when the two factors are close together, because then y=(v−u)/2 is small and x lies close to √n.
6. Why Fermat factorisation can also be slow
If n=pq with p much smaller than q, the required x=(p+q)/2 may lie far above √n. The algorithm may then need many unsuccessful square tests.
This teaches a recurring design principle:
A factorisation algorithm succeeds quickly when the hidden factors have the structure that algorithm is designed to exploit.
There is no single elementary method that is uniformly best for every composite integer.
7. Smooth numbers and why p−1 matters
An integer is B-smooth if all its prime factors are at most B. For example, 60=2²·3·5 is 5-smooth.
Smoothness is central to many factoring algorithms because multiplicative groups contain orders dividing numbers such as p−1. If p−1 factors entirely into small primes, exponentiation can accidentally force a residue to become 1 modulo p while not becoming 1 modulo the whole composite n.
A gcd can then extract p.
8. Pollard p−1 method
Suppose n has an unknown prime factor p and p−1 is B-smooth. Choose a base a coprime to n and an exponent M divisible by all prime powers up to the chosen smoothness bound. Then, because p−1 divides M, Fermat’s theorem gives
a^M ≡ 1 (mod p).
Therefore p divides a^M−1. Compute
d=gcd(a^M−1,n).
If 1<d<n, a nontrivial factor has been found.
Worked example: n=299
We know for checking that 299=13·23, but the algorithm does not. Take B=5 and M=lcm(1,2,3,4,5)=60. Choose a=2.
Because 13−1=12 divides 60, 2^60≡1 (mod 13). Compute 2^60 mod 299 by fast modular exponentiation, subtract 1, and take a gcd:
gcd(2^60−1,299)=13.
The factor 13 is recovered. The method succeeded because p−1 had the right smoothness profile.
9. Failure modes of Pollard p−1
Three outcomes are common:
- d=1: the chosen exponent has not captured the order modulo a useful factor.
- 1<d<n: success; d is a nontrivial factor.
- d=n: the exponent collapsed modulo every prime factor at once, giving no separation.
Changing the base, increasing the smoothness bound or switching algorithms may be appropriate. Failure does not imply that n is prime; it only means this particular structural attack did not separate a factor.
10. Pollard rho: create a collision modulo an unknown factor
Pollard’s rho algorithm takes a different approach. Choose a simple pseudorandom-looking recurrence such as
x_{k+1}=f(x_k)=x_k²+c mod n.
If n has a factor p, then the same sequence reduced modulo p lives in a set of only p residues. Eventually two sequence values collide modulo p even if they are different modulo n. When x_i≡x_j (mod p), p divides x_i−x_j.
Therefore
gcd(|x_i−x_j|,n)
may reveal p without our ever knowing which modulus caused the collision.
11. Cycle detection without storing the entire sequence
A straightforward collision search would store many previous values. Pollard rho commonly uses Floyd’s cycle-finding method instead: a tortoise advances one step at a time while a hare advances two.
x = seed
y = seed
repeat:
x = f(x)
y = f(f(y))
d = gcd(|x−y|, n)
until d ≠ 1
If d=n, that run has collapsed without isolating a factor; change the seed or polynomial and try again. If 1<d<n, d is a nontrivial factor.
12. Worked Pollard rho example: n=8051
Use f(x)=x²+1 mod 8051 with x=y=2.
Iteration 1: x = 5 y = 26 gcd(|5−26|,8051) = 1 Iteration 2: x = 26 y = 7474 gcd(|26−7474|,8051) = 1 Iteration 3: x = 677 y = 871 gcd(|677−871|,8051) = 97.
So 97 is a factor, and division gives the other factor 83:
8051=83·97.
The algorithm did not search divisors 2,3,4,…,97. It engineered a collision whose hidden modular structure became visible through a gcd.
13. Why the rho shape appears
When a deterministic function repeatedly maps a finite set into itself, the sequence eventually enters a cycle. Draw the preperiod as a tail and the cycle as a loop: the picture resembles the Greek letter ρ.
The birthday paradox suggests that a random-looking sequence modulo a factor p is likely to produce a collision after roughly √p samples. This explains why Pollard rho can be much better than trial division when n has a reasonably small hidden factor.
14. Factoring recursively
Finding one factor does not necessarily finish the job. If n=ab and either a or b is composite, continue factoring those cofactors.
factor(n):
if n = 1: stop
if n is prime: output n; stop
d = find_nontrivial_factor(n)
factor(d)
factor(n/d)
This design separates two subproblems:
- Primality testing: decide whether the current cofactor is finished.
- Factor discovery: split a composite cofactor into smaller pieces.
A practical factorisation system therefore combines the algorithms from the whole series rather than relying on one method in isolation.
15. Perfect powers should be detected deliberately
Numbers such as n=a^k contain repeated structure. Detecting perfect squares, cubes or higher powers can simplify the recursive process.
For example, 1048576=2^20. Treating this as a generic hard composite would ignore obvious structure. Integer-root algorithms can test whether n is an exact k-th power without relying on floating-point equality.
16. Difference-of-squares congruences
Fermat factorisation requires an actual equality x²−y²=n. More advanced methods relax this to a congruence:
x² ≡ y² (mod n).
Then n divides (x−y)(x+y). If x is not congruent to ±y modulo n, the gcds
gcd(x−y,n) gcd(x+y,n)
have a chance to expose nontrivial factors.
This simple identity sits underneath the quadratic sieve and, in a more elaborate algebraic form, the number field sieve.
17. The quadratic sieve idea
The quadratic sieve searches for many values whose residues factor completely over a small chosen factor base. Such values are called smooth relative to that base.
Represent the parity of prime exponents in each smooth factorisation as a vector over the two-element field. A linear dependency among these vectors gives a product whose prime exponents are all even, hence a square. That produces a congruence x²≡y² (mod n), after which gcd extraction may reveal a factor.
The method is a striking synthesis:
Number theory → smoothness search → linear algebra → gcd → factor.
18. The general number field sieve
For sufficiently large general integers, the general number field sieve is the dominant classical factoring framework. It extends the smoothness-and-congruence philosophy into algebraic number fields, where two related factorisation worlds are built and later combined.
The implementation is far beyond an elementary worked algorithm: polynomial selection, sieving, relation collection, filtering, large sparse linear algebra and square-root reconstruction each form substantial computational stages.
The conceptual continuity matters more here than the machinery. Even at the advanced level, the strategy is still to manufacture enough structured relations that a hidden factor becomes recoverable through a final arithmetic separation.
19. Special-purpose versus general-purpose factorisation
Some algorithms exploit special structure in one of the unknown factors; others are designed for general difficult inputs.
- Trial division: excellent when a factor is tiny.
- Fermat: strong when two factors are close.
- Pollard p−1: strong when p−1 is smooth for some factor p.
- Pollard rho: good for discovering comparatively small factors without scanning every divisor.
- Elliptic-curve method: powerful for finding factors whose size is moderate relative to an enormous composite; success depends on smooth group orders on chosen curves.
- Quadratic sieve: general-purpose for medium-to-large integers.
- General number field sieve: the major classical general-purpose method for the largest hard integers.
A mature system chooses algorithms according to the expected factor profile rather than treating every composite as the same object.
20. Complexity: magnitude is not input length
If n has k binary digits, then n is on the scale of 2^k. Trial division to √n therefore examines a range on the scale of 2^(k/2). That is exponential in k.
This is why “but we only have to go to the square root” is not a satisfactory complexity argument for very large integers. Square root is small relative to n, but still enormous relative to log n, the quantity measuring how many bits were supplied as input.
21. Subexponential does not mean polynomial
The best known classical general-purpose factoring algorithms are much faster than naive exponential search, but they are not known to run in polynomial time for arbitrary integers.
Algorithms such as the number field sieve are described as subexponential because their asymptotic growth lies between polynomial and ordinary exponential forms. This is a major improvement, but difficult instances still become extremely expensive as input sizes grow.
The absence of a known polynomial-time classical factoring algorithm is not a proof that none exists. Computational complexity distinguishes “no efficient algorithm is currently known” from “efficient computation has been mathematically ruled out.”
22. Quantum computation changes the theoretical landscape
Shor’s algorithm showed that integer factorisation can be performed in polynomial time on an ideal fault-tolerant quantum computer. The algorithm reduces factorisation to an order-finding problem that quantum Fourier techniques can solve efficiently.
This is a theoretical algorithmic result, not a statement that every large classical factoring challenge is presently easy in practice. Resource requirements, error correction and available hardware remain separate engineering questions.
The lesson for Mathematics is broader: computational difficulty depends not only on the problem, but also on the computational model being allowed.
23. Factorisation and cryptographic hardness
Some public-key systems have historically relied on the practical difficulty of factoring carefully generated large composite integers. The security reasoning is not “multiplication is one-way.” Multiplication is easy in both directions when the factors are already known. The asymmetry is that multiplying chosen large primes is efficient, while recovering those hidden factors from their product is believed to be computationally difficult for suitable classical parameter sizes.
For a Mathematics learner, the useful distinction is:
Easy to construct + easy to verify does not imply easy to invert.
24. Randomness as an algorithmic resource
Pollard rho, elliptic-curve methods and many practical primality routines use randomness or pseudorandom choices. Randomness is not an admission that the Mathematics is vague. It is often a deliberate strategy for avoiding adversarial structure or exploring many possible trajectories cheaply.
A randomized algorithm should still have a clear correctness story:
- What happens when it returns a factor?
- Can the factor be verified immediately?
- What does failure mean?
- Can the algorithm restart with different random choices?
- How does the probability of success change with repeated trials?
In factorisation, a returned nontrivial gcd is deterministic evidence even when random choices were used to discover it.
25. Building a practical factorisation pipeline
A robust educational pipeline might look like this:
- Normalise sign and handle 0, 1 and small exceptional cases.
- Strip small prime factors.
- Detect perfect powers.
- Run a fast primality test on the remaining cofactor.
- If composite, try Pollard rho for modest hidden factors.
- Use Pollard p−1 when smoothness is plausible or as a cheap auxiliary attempt.
- For harder larger cofactors, escalate to ECM, quadratic-sieve or number-field-sieve machinery according to size and context.
- Recursively factor every composite cofactor.
- Verify the complete product and primality of terminal factors.
No single line is the subject. The architecture is the subject: detect easy structure first, preserve certificates, escalate only when necessary, and verify the final decomposition independently.
26. Common mistakes
- Assuming a compositeness witness gives a factor. It may not.
- Calling trial division efficient because √n is smaller than n. Complexity must be measured against input bit length.
- Using Fermat factorisation without considering factor distance. Widely separated factors can make it slow.
- Interpreting d=1 in Pollard p−1 or rho as “prime.” It means only that this attempt did not split n.
- Forgetting to check d=n. That outcome gives no nontrivial factor.
- Stopping after the first split. Both cofactors may need further factorisation.
- Using floating-point square tests carelessly. Exact integer arithmetic is preferable.
- Trusting the factor list without multiplying it back. Final verification is cheap and should always be performed.
27. Practice set
- Factor 8051 by verifying the Pollard rho result 97.
- Use Fermat factorisation to factor 5959.
- Explain why Fermat factorisation is fast when factors are close.
- Factor 299 using the information gcd(2^60−1,299)=13.
- Why does Pollard p−1 care about the factorisation of p−1 rather than n−1?
- In Pollard rho, what does gcd(|x−y|,n)=1 mean?
- What does gcd(|x−y|,n)=n mean?
- Why can a collision modulo an unknown factor be useful even when x≠y modulo n?
- Explain why trial division to √n is exponential in the bit length of n.
- What is a B-smooth number?
- Why do quadratic-sieve style methods search for smooth relations?
- State the difference between primality testing and factorisation.
- Why is multiplying recovered factors an important final step?
- What does Shor’s algorithm change about the theoretical complexity of factoring?
28. Answers and checks
1. 8051/97=83, and 83·97=8051. Both 83 and 97 are prime, so the complete factorisation is 83·97.
2. 80²−5959=441=21², so 5959=(80−21)(80+21)=59·101.
3. If n=pq with p and q close, x=(p+q)/2 lies close to √n, so only a small number of x-values need testing.
4. The gcd supplies factor 13; 299/13=23. Thus 299=13·23.
5. The method tries to force a^M≡1 modulo one hidden prime factor p by making M a multiple of p−1. The structure of that factor’s multiplicative group is what matters.
6. No nontrivial common divisor has yet been exposed by that pair of sequence states.
7. The difference is divisible by every factor represented in n strongly enough that the gcd returns the whole modulus; the run has not isolated a proper factor.
8. If x≡y mod p, then p divides x−y. The gcd with n can recover p even though the two states remain distinct modulo the full composite n.
9. A k-bit integer is about 2^k, so √n is about 2^(k/2), an exponential function of k.
10. An integer whose prime factors are all at most B.
11. Smooth factorizations translate multiplicative information into parity vectors; dependencies among those vectors can construct a square congruence and lead to a gcd factor.
12. Primality testing asks whether n is prime; factorisation asks for the prime divisors and their multiplicities. A number can be proved composite without a factor being found.
13. It gives an independent exact check that the decomposition reconstructs the original integer.
14. On an ideal fault-tolerant quantum computer, Shor’s algorithm places integer factorisation in polynomial time, changing the computational model from the best known classical landscape.
29. What the four-guide series now reveals
The four computational number theory guides form one connected machine.
- The Euclidean algorithm gives gcds, Bézout certificates and modular inverses.
- Fast modular exponentiation makes enormous powers computationally manageable.
- CRT decomposes and reconstructs modular systems.
- Prime sieves generate structured sets efficiently.
- Miller–Rabin separates many composites from prime candidates without factoring them.
- Factorisation methods search for different structural weaknesses in composite integers.
- Verification closes the loop after every important computational claim.
Computational number theory is therefore not a catalogue of tricks. It is a discipline of representation, invariants, reduction, certificates, complexity and controlled return from abstract arithmetic to a verified answer.
30. Computational Number Theory series
- Guide 1: Euclidean Algorithm, Bézout Identity and Modular Inverses
- Guide 2: Fast Modular Exponentiation and the Chinese Remainder Theorem
- Guide 3: Prime Sieves, Probable Primes and Primality Testing
- Guide 4: Integer Factorisation, Pollard Methods and Computational Limits
Return to the Singapore Mathematics Hub for the wider BTT Mathematics library.