We prove that van Hoeij’s original algorithm to factor univariate polynomials over the rationals runs in polynomial time, as well as natural variants. In particular, our approach also yields polynomial time complexity results for bivariate polynomials over a finite field.

Let $K$ be a number field containing, for some prime $\ell$, the $\ell$-th roots of unity. Let $L$ be a Kummer extension of degree $\ell$ of $K$ characterized by its modulus $𝔪$and its norm group. Let $K_{𝔪}$ be the compositum of degree $\ell$ extensions of $K$ of conductor dividing $𝔪$. Using the vector-space structure of $Gal(K_{𝔪}/K)$, we suggest a modification of the rnfkummer function of PARI/GP which brings the complexity of the computation of an equation of $L$ over $K$ from exponential to linear.

Let $𝒪$ be the maximal order of the cubic field generated by a zero $\epsilon$ of $x^3+(\ell -1)x^2-\ell x-1$ for $\ell \in \mathbb{Z}$, $\ell \ge 3$. We prove that $\epsilon ,\epsilon -1$ is a fundamental pair of units for $𝒪$, if $[𝒪:\mathbb{Z}[\epsilon \left]\right]\le \ell /3.$