Infoscience

Journal article

# Optimal algorithms for multiplication in certain finite fields using elliptic curves

Using the results given in [D,. V. Chudnovsky and G. V Chudnovsky, Proc. Nat. Acad. Sci. USA, 84 (1987), pp. 1739-1743] and [W. C. Waterhouse, Ann. Sci. École Norm. Sup., 4 (1969), pp. 521560], it is proven that the rank (= bilinear complexity of multiplication) of the finite field $mathbbF_q^n$ viewed as an $mathbbF_q$-algebra is $2n$ if $n$ satisfies $frac12q+1< n <frac12(q+1+ epsilon (q))$. Here $epsilon (q)$ is the greatest integer $leq 2sqrt q$ which is prime to $q$ if $q$ is not a perfect square and $epsilon (q) = 2sqrt q$ if $q$ is a perfect square.