Home > 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.

- URL
- Export as: BibTeX | MARC | MARCXML | DC | EndNote | NLM | RefWorks | RIS
- View as: MARC | MARCXML | DC
- Add to your basket:

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