Nearly Optimal Algorithms for the Decomposition of Multivariate Rational Functions and the Extended L\"uroth's Theorem

The extended L"uroth’s Theorem says that if the transcendence degree of $\text{KK}({\mathsf{f}}_1,\dots ,{\mathsf{f}}_m)\mathrm{/}\text{KK}$ is 1 then there exists $f \in \KK(\underline{X})$suchthat$\KK($\mathsf{f}$_1,\dots,$\mathsf{f}$_m)$ is equal to $\text{KK}(f)$. In this paper we show how to compute $f$ with a probabilistic algorithm. We also describe a probabilistic and a deterministic algorithm for the decomposition of multivariate rational functions. The probabilistic algorithms proposed in this paper are softly optimal when $n$ is fixed and $d$ tends to infinity. We also give an indecomposability test based on gcd computations and Newton’s polytope. In the last section, we show that we get a polynomial time algorithm, with a minor modification in the exponential time decomposition algorithm proposed by Gutierez-Rubio-Sevilla in 2001.