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