On the existence of non-special divisors of degree $g$ and $g-1$ in algebraic function fields over $\F_q$

Abstract

We study the existence of non-special divisors of degree $g$ and $g-1$ for algebraic function fields of genus $g\ge 1$ defined over a finite field $\F_q$. In particular, we prove that there always exists an effective non-special divisor of degree $g\ge 2$ if $q\ge 3$ and that there always exists a non-special divisor of degree $g-1\ge 1$ if $q\ge 4$. We use our results to improve upper and upper asymptotic bounds on the bilinear complexity of the multiplication in any extension $\F_{q^n}$ of $\F_q$, when $q=2^r\ge 16$.

21 pages: added Remark 22 at the end of the paper