Optimal Algorithms for Multiplication in Certain Finite Fields Using Elliptic Curves

Abstract

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 $\mathbb{F}_{q^n } $ viewed as an $\mathbb{F}_q $-algebra is $2n$ if n satisfies $\frac{1}{2}q+1< n <\frac{1}{2}(q+1+ \epsilon (q))$. Here $\epsilon (q)$ is the greatest integer $ \leq 2\sqrt q $ which is prime to q if q is not a perfect square and $\epsilon (q) = 2\sqrt q $ if q is a perfect square.