Week 67 of 125
TAOCP 4.5.4 Factoring into Primes
Sign up or sign in to tick these off and give this week a due date.
-
Methods for factoring integers and testing primality: trial division, Fermat's method, Pollard's rho, probabilistic primality testing, and the connection to public-key cryptography (RSA), plus a look at more advanced sieving methods.
Time About 10 hours this week
Why it matters
Primality testing and the hardness of factoring are the foundation of RSA. Pollard rho is also a neat use of cycle detection.
Before you start
- 4.5.2 The Greatest Common Divisor
- 4.3.2 Modular Arithmetic
How to approach it
Implement trial division, Pollard rho (with Floyd's cycle detection) and a Miller-Rabin primality test. Factor some 20-digit numbers. Read the advanced methods for the ideas only.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Overflow in modular multiplication. Use 128-bit intermediates or bignums.
- Treating a probabilistic test as deterministic.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.