Week 62 of 125
TAOCP 4.3.2 Modular Arithmetic
Sign up or sign in to tick these off and give this week a due date.
-
Representing big numbers by their remainders modulo several coprime moduli, so that addition and multiplication become independent small operations, then reconstructing the answer with the Chinese remainder theorem.
Time About 6 hours this week
Why it matters
Residue number systems are used in cryptography and in fast polynomial and integer arithmetic. CRT also shows up in competitive programming and hashing.
Before you start
- 4.3.1 The Classical Algorithms
- 1.2.4 Number theory
How to approach it
Implement CRT reconstruction for three small moduli and test it. Make sure you can compute a modular inverse with extended Euclid.
Exercises
Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.
Traps
- Moduli that are not pairwise coprime break the reconstruction.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.