Algebraic complexities and algebraic curves over finite fields (Q5903919)

The authors investigate the minimal algebraic complexities of multiplication in algebras over finite fields. This means that they assume that addition, subtraction and multiplication of two elements in that field cost constant time. For infinite fields these minimal complexities are known. It is shown that for finite fields the minimal complexities are larger. The authors use coding theory, and the algebraic geometrical methods used to construct Goppa codes, to find both upper and lower bounds for the minimal complexities. These bounds are both linear in the dimension of the algebra.