Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 37 ยท Projects and Practice

Project: A Factoring Benchmark

Measure how trial division, Fermat, Pollard rho and p-1 scale with the size of the factors, plot the growth, and build a combined factoring pipeline.

Which factoring algorithm should you use? The honest answer is "it depends on the number", and in this project you will find out how. You will count the steps that trial division, Fermat's method and Pollard's rho need on semiprimes of growing size, plot the growth, and assemble a pipeline that tries cheap methods first.

We count steps (loop iterations) rather than seconds. Step counts are exactly reproducible, they do not depend on the speed of your computer, and they show the algorithmic growth rate clearly: โˆšp for trial division and rho (with different constants), and something erratic for Fermat.

Step 1: instrumented algorithms

Each function returns (factor, steps).

Python Step 1: three factoring methods that count their steps

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 this number, with two ~7-digit factors that are close, Fermat needs a single step, rho needs a few hundred, and trial division needs about half a million.

Step 2: scaling with the factor size

We now build semiprimes pยทq with p about 10^k and q the next prime far above (so Fermat cannot cheat), and record steps per method. Rho depends on the smaller factor; so do trial division and (for far-apart factors) Fermat.

Python Step 2: steps against the size of the smallest factor

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.

Trial division grows as p/2 (every ten times larger p means ten times more steps), rho grows as roughly โˆšp (about three times more steps for ten times larger p). At 7 digits the gap is already a factor of a thousand, and it keeps widening (we stop at 7 digits because trial division at 12 digits would take billions of steps).

Step 3: plot the growth

On a log-log plot a method with cost p^a is a straight line with slope a. Trial division should have slope 1, rho slope close to 1/2.

Python Step 3: log-log plot

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 printed slopes are close to 1.0 for trial division and noticeably lower for rho (roughly 0.5 to 0.6, with some noise because rho is randomized by the starting values).

Step 4: where Fermat and p-1 win

Now vary the shape of the input instead of its size. Fermat cares about how close the factors are; p-1 cares about the smoothness of p - 1.

Python Step 4: input shape matters

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.

Fermat is instant on close factors and hopeless on far ones, and p-1 only succeeds when one prime has a smooth p - 1.

Step 5: a pipeline

Real tools escalate. The pipeline below removes small primes, checks for perfect powers, tests primality and then rotates through methods, splitting recursively.

Python Step 5: a combined factoring pipeline

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 pipeline reproduces SymPy's factorization, and the log shows which method found each split. Production libraries add ECM and sieves for the final hard factors.

Extensions

  • Add Brent's batched gcd variant from the rho lesson and compare gcd counts.
  • Implement a Williams p+1 step for primes with smooth p + 1.
  • Measure real seconds with time.perf_counter and see how the order of the methods changes.
  • Try factoring RSA-style semiprimes of 40, 50 and 60 digits with SymPy and record the time: you will meet the wall that makes 2048-bit RSA safe.
flowchart LR
    N["n"] --> S["small primes"]
    S --> P{"prime?"}
    P -->|no| F["Fermat"]
    F --> M["p - 1"]
    M --> R["rho"]
    R --> N2["recurse on both parts"]

The benchmark pipeline, cheapest method first.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why count steps instead of seconds in a benchmark of algorithms?

    Step counts remove hardware noise, so the scaling law is visible.
  2. 2. On a log-log plot, trial division against p has slope about:

    Cost is proportional to p, so the log-log slope is 1.
  3. 3. When is Fermat's method fast?

    The search ends when x equals the average of the factors.
  4. 4. Why does a pipeline try cheap methods first?

    Cheap steps remove easy factors, so the expensive methods only see the hard core.

Summary

  • Counting steps shows growth rates: trial division ~p, rho ~โˆšp.
  • Input shape matters: Fermat likes close factors, p-1 likes smooth p - 1.
  • A pipeline removes small primes, tests for primality, then escalates through methods and recurses.
  • Factoring gets hard quickly, which is the basis for RSA key sizes.

Next: Practice: Number Theory Problem Set