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.