Finding roots in polynomials of one variable over a finite field

Finding roots in polynomials of one variable over a finite field

Johan S. R. Nielsen No Comment
Bachelor Projects

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!