TAOCP Vol 2: Seminumerical Algorithms · Week 69
TAOCP 4.6.2 Factorization of Polynomials: reading guide
Factoring polynomials modulo a prime (Berlekamp's algorithm and distinct-degree factorization) and then lifting to factor polynomials over the integers.
Time About 7 hours this week
Why it matters
One of the more specialized sections. It matters for computer algebra and coding theory; for most programmers the takeaway is that factoring polynomials is surprisingly tractable while factoring integers is not.
Before you start
- 4.6.1 Division of Polynomials
- Basic linear algebra mod p
How to approach it
Read the overview and follow one small worked example of Berlekamp's algorithm. Skim the rest. Spend extra time catching up if you are behind.
Exercises
Mostly M and HM exercises; do a couple of the low-rated ones and move on.
Traps
- Feeling you must master this. It is fine to come back later.