# Finding roots in polynomials of one variable over a finite field

## Finding roots in polynomials of one variable over a finite field

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!