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

Given a positive integer \(n\), the author describes how to find an elliptic curve \(E\) over a finite field \(\mathbb{F}_ q\) with at least \(2n+2\) points together with a non-trivial point \(P\) defined over \(\mathbb{F}_{q^ n}\). In the final section it is explained how this can be used to obtain a fast multiplication algorithm in the field \(\mathbb{F}_{q^ n}\). Here the author follows an idea of \textit{D. V. Chudnovsky} and \textit{G. V. Chudnovsky} [Proc. Natl. Acad. Sci. USA 84, 1739-1743 (1987; Zbl 0644.68066)]. Especially noteworthy is Algorithm III-B on page 76, to obtain an elliptic curve over \(\mathbb{F}_ q\) with at least a given number of rational points. The author proves that his algorithm requires \(O(q^ 4)\) operations in \(\mathbb{F}_ q\). The exponent 4 is, at present, the highest value known to the reviewer.