Loading...
research 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.
Type
research article
Authors
Publication date
1992
Published in
Volume
21
Issue
6
Start page
1193
End page
1198
Subjects
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
January 26, 2007
Use this identifier to reference this record