Efficient and optimal exponentiation in finite fields (Q685709): Difference between revisions

The problem of the efficient exponentiation in a finite field \(\mathbb F_{q^ n}\) of order \(q^ n\) by arithmetic circuits over \(\mathbb F_{q^ n}\) is considered, where \(q\) is a prime power and \(n \geq 1\). The basic assumption of the computational model is that \(q\)-th powers can be computed for free. An algorithm using size about \(n/ \log_ qn\) and depth about \(\log_ 2n\) is presented. For \(q=2\) this is a slight improvement on a result of \textit{D. R. Stinson} [SIAM J. Comput. 19, 711--717 (1990; Zbl 0697.68049)]. A counting argument shows that the size cannot be improved below essentially \({1 \over 3}n/ \log_ qn\). A detailed study of the depth is carried out by using addition chains with free multiples of \(q\). Note: the references Jedwab and Mitchell (1989) [J. Jedwab and C. J. Mitchell, Minimum weight modified signed-digit representations and fast exponentiation, Electron. Lett. 25, 1171--1172 (1989; Zbl 0709.94699)] and Takagi et al. (1985) [N. Takagi et al., IEEE Trans. Comput. 34, 789--796 (1985; Zbl 0565.94021)] occur in the text, e.g. on p. 362, but they are not included in the bibliography, and so the reader cannot follow them up.