The problem of finding a nontrivial factor of a polynomial $f(x)$ over a finite field $\mathbb{F}_q$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the ... more >>>

In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree $d$ polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can ... more >>>