Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 37 ยท Primality and Factoring

Fermat's Factorization and Pollard's p-1

Factor numbers with Fermat's difference of squares and Pollard's p-1 method, see when each one is fast or hopeless, and compare them with trial division.

Pollard's rho is not the only clever way to split a number. Two older ideas exploit special structure. Fermat's method is fast when the two factors are close together. Pollard's p-1 method is fast when one prime factor p has the property that p - 1 is made of small primes. Both are important for a reason beyond speed: they explain how RSA primes must be chosen, because a key that is easy for either method is broken.

We start with the baseline, trial division, then build the two newcomers and compare them on the same inputs.

Trial division and the square-root bound

If n is composite it has a divisor d with d โ‰ค โˆšn. Trying every d up to โˆšn is correct but takes O(โˆšn) steps. Skipping evens (and multiples of 3) reduces the work by a constant factor but not the growth rate.

Python Trial division with a wheel

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 13-digit product costs about a million loop steps. Add three digits to each factor and it costs a billion. Trial division does not scale, which is why the other methods exist.

Fermat's method: difference of squares

An odd number n = aยทb can be written as n = xยฒ - yยฒ = (x - y)(x + y) with x = (a + b)/2 and y = (b - a)/2. So we search for an x โ‰ฅ โŒˆโˆšnโŒ‰ such that xยฒ - n is a perfect square yยฒ. The first hit gives the factors x - y and x + y.

If the factors are close (a โ‰ˆ b โ‰ˆ โˆšn), then x is just above โˆšn and the search ends almost immediately. If one factor is small, the search is slow, even slower than trial division.

Python Fermat factorization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 1000003 ร— 1000033 the difference of the factors is only 30, so the loop needs very few steps. For 3 ร— 1000003 Fermat's method is hopeless: x has to climb to (3 + 1000003) / 2 โ‰ˆ 500003, which exceeds the limit of 100000 steps, so the function gives up.

The lesson for key generation: the two primes of an RSA modulus must not be close. If |p - q| is smaller than about n^(1/4), Fermat's method breaks the key in a flash.

Pollard's p-1 method

Suppose p is a prime factor of n and p - 1 is B-smooth, meaning all its prime factors are at most B. Then p - 1 divides M = B! (or the product of all prime powers up to B). By Fermat's little theorem, for any a coprime to p:

a^M โ‰ก 1 (mod p), so p | a^M - 1.

Since p | n as well, gcd(a^M - 1, n) is divisible by p. We never learn p directly, but the gcd extracts it. If the gcd comes out as n we overshot (every prime factor was smooth), so we lower B or switch strategy.

Python Pollard p-1 with stage-one bound B

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the smooth prime p the method succeeds with the tiny bound B = 20, because every prime factor of p - 1 is at most 13. When the factors of n have p - 1 containing a huge prime (as q - 1 does), it fails: the function returns None. The printed factorizations show why.

A stage-two sketch and Williams p+1

Real implementations add a second stage: allow one extra prime factor q between B1 and a larger B2 in p - 1. The idea is to compute x^q for each such prime and test the gcd. This extends reach cheaply. Williams' p+1 method is the mirror image, working when p + 1 is smooth, using Lucas sequences. Lenstra's elliptic curve method (ECM) generalizes both by replacing the group (Z/pZ)* with the group of an elliptic curve, whose order is random, giving many independent chances for smoothness.

Comparing the methods

Python Which method wins on which input?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table you get is the point of this lesson: no single method dominates. Close factors favour Fermat, smooth p - 1 favours p-1, and generic factors are Pollard rho's territory. Production factoring libraries run all of them, then ECM, then a sieve for the final hard cases.

flowchart TD
    N["Composite n"] --> T["Trial division by small primes"]
    T --> F["Fermat (close factors)"]
    F --> R["Pollard rho (factors up to ~20 digits)"]
    R --> P["p-1 and p+1 (smooth neighbours)"]
    P --> E["ECM"]
    E --> S["Quadratic or number field sieve"]

A typical factoring pipeline escalates from cheap to expensive methods.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Fermat's method is fastest when:

    The search starts at ceil(sqrt n) and ends when x equals the average of the two factors.
  2. 2. Pollard's p-1 method works well when:

    Then p - 1 divides B!, so a^(B!) โ‰ก 1 mod p, and the gcd with n exposes p.
  3. 3. What does gcd(a^M - 1, n) = n tell you in the p-1 method?

    You overshot: every factor p had p - 1 dividing M. Use a smaller bound or a different base.
  4. 4. Why must RSA primes p and q not be close to each other?

    If p and q are within about n^(1/4) of each other, Fermat's search ends after very few steps.

Summary

  • Trial division costs O(โˆšn); a wheel only improves the constant.
  • Fermat writes n = xยฒ - yยฒ and is quick when the factors are close together.
  • Pollard's p-1 exploits a smooth p - 1 through gcd(a^(B!) - 1, n).
  • Rho, Fermat and p-1 each win on different inputs; real software chains them, then ECM and sieves.
  • Safe RSA primes are far apart and have p - 1 with a large prime factor.

Next: Linear Diophantine Equations