Keywords: root finding, polynomials, algorithm
Prerequisites: 01018: Discrete Mathematics 2
Given a polynomial \(p \in \mathbb{F}_q[X]\), where \(\mathbb{F}_q\) is the finite field with \(q\) elements, we can find all the roots of \(p\) by trying the \(q\) possibilities. If \(p\) has low degree while \(q\) is big, that seems like an inefficient way of doing it. In this project you will work with a very clever algorithm, the Cantor–Zassenhaus algorithm, for finding the roots in roughly \(\deg p\log(q)\) computational steps!