Please kindly let me know if the question is not suitable for this forum or duplicated.
Assume all operations and polynomials are defined and done on $\mathbb{F}_q$, where $q$ is a large prime number of size $z$ bits.
Question: What is the complexity of factorizing a polynomial over $\mathbb{F}_q$? How does the size of $q$ play a role in the factorization complexity?