Week 69 of 125
TAOCP 4.6.2 Factorization of Polynomials
Sign up or sign in to tick these off and give this week a due date.
-
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.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.