Berlekamp-Massey / Kitamasa Ladder¶
Who This Is For¶
Use this ladder when you already trust linear recurrences, but the matrix route feels too cubic or the recurrence itself must be recovered from a prefix first.
Warm-Up¶
- fixed-order recurrence notation
- modular arithmetic over one trusted prime field
- knowing exactly what the first
dterms mean
Core¶
- Kitamasa / characteristic-polynomial reduction for the
k-th term - Berlekamp-Massey discrepancy updates for shortest-recurrence recovery
Stretch¶
- move from "recurrence given" to "recurrence hidden in a prefix"
- compare this lane with matrix exponentiation and FPS / generating-function viewpoints
Retrieval Layer¶
- exact starter -> berlekamp-massey-kitamasa.cpp
- quick reminder sheet -> Berlekamp-Massey / Kitamasa hot sheet
- compare point -> Linear Recurrence hot sheet
Repo Anchors¶
Exit Criteria¶
You are ready to move on when you can:
- translate the recurrence into the repo coefficient convention without guessing
- explain why reducing powers of
xmodulo the recurrence replaces matrix powers - recover the shortest recurrence from a prefix with Berlekamp-Massey
- tell when the ordinary matrix route is still the better first tool