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.


Published in:
SIAM Journal of Computing, 21, 6, 1193-1198
Year:
1992
Keywords:
Laboratories:




 Record created 2007-01-26, last modified 2018-03-17

External link:
Download fulltext
URL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)