Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field

We analyze the behavior of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field F_q of q elements when the highest-degree polynomial g is fixed. Considering all the elements f of fixed degree, we establish asymptotically optimal bounds in terms of q for the number of elements f which are relatively prime with g and for the average degree of gcd(g,f). The accuracy of our estimates is confirmed by practical experiments. We also exhibit asymptotically optimal bounds for the average-case complexity of the Euclidean algorithm applied to pairs (g,f) as above.

The distribution of factorization patterns on linear families of polynomials over a finite field

We obtain estimates on the number $|mathcal{A}_{boldsymbol{lambda}}|$ of elements on a linear family $mathcal{A}$ of monic polynomials of $mathbb{F}_q[T]$ of degree $n$ having factorization pattern $boldsymbol{lambda}:=1^{lambda_1}2^{lambda_2}cdots n^{lambda_n}$. We show that $|mathcal{A}_{boldsymbol{lambda}}|= mathcal{T}(boldsymbol{lambda}),q^{n-m}+mathcal{O}(q^{n-m-{1}/{2}})$, where $mathcal{T}(boldsymbol{lambda})$ is the proportion of elements of the symmetric group of $n$ elements with cycle pattern $boldsymbol{lambda}$ and $m$ is the codimension of $mathcal{A}$. Furthermore, if the family $mathcal{A}$ under consideration is sparse, then $|mathcal{A}_{boldsymbol{lambda}}|= mathcal{T}(boldsymbol{lambda}),q^{n-m}+mathcal{O}(q^{n-m-{1}})$. Our estimates hold for fields $mathbb{F}_q$ of characteristic greater than 2. We provide explicit upper bounds for the constants underlying the $mathcal{O}$--notation in terms of $boldsymbol{lambda}$ and $mathcal{A}$ with good behavior. Our approach reduces the question to estimate the number of $mathbb{F}_q$--rational points of certain families of complete intersections defined over $mathbb{F}_q$. Such complete intersections are defined by polynomials which are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning their singular locus, from which precise estimates on their number of $mathbb{F}_q$--rational points are established.

On the value set of small families of polynomials over a finite field, I

We obtain an estimate on the average cardinality of the value set of any family of monic polynomials of Fq[T] of degree d for which s consecutive coefficients a_{d-1},..., a_{d-s} are fixed. Our estimate holds without restrictions on the characteristic of Fq and asserts that V(d,s,bfs{a})=mu_d.q+mathcal{O}(1), where V(d,s,bfs{a}) is such an average cardinality, mu_d:=sum_{r=1}^d{(-1)^{r-1}}/{r!} and bfs{a}:=(a_{d-1},.., d_{d-s}). We provide an explicit upper bound for the constant underlying the mathcal{O}--notation in terms of d and s with good behavior. Our approach reduces the question to estimate the number of Fq--rational points with pairwise--distinct coordinates of a certain family of complete intersections defined over Fq. We show that the polynomials defining such complete intersections are invariant under the action of the symmetric group of permutations of the coordinates. This allows us to obtain critical information concerning the singular locus of the varieties under consideration, from which a suitable estimate on the number of Fq--rational points is established.