Efficient randomized generation of optimal algorithms for multiplication in certain finite fields

Let $N_{max}(q)$ denote the maximum number of points of an elliptic curve over $F_q$ . Given a prime power $q=p^f$ and an integern satisfying $\frac{1}{2}q+1 < n le (N_{max}(q)2)/2$, we present an algorithm which on inputq andn produces an optimal bilinear algorithm of length $2n$ for multiplication in $F_q^n / F_q$. The algorithm takes roughly $O(q^4+n^4 \log q) F_q$-operations or equivalently $O((q^4+n^4 log q)f^2 \log^2 p)$ bit- operations to compute the output data.


Published in:
Computational Complexity, 2, 1, 67-96
Year:
1992
Keywords:
Laboratories:




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

External link:
Download fulltext
URL
Rate this document:

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