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

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