Complexity of Boolean schemes for arithmetic in some towers of finite fields. (Russian, English) Zbl 1150.06315

Vestn. Mosk. Univ., Ser. I 2006, No. 5, 10-16 (2006); translation in Mosc. Univ. Math. Bull. 61, No. 5, 9-14 (2006).
In the paper it is proved that for any \(\epsilon>0\) and any \(m\), if \(n=m^s\) and \(s\geq s_\epsilon\), then in the field GF\((2^n)\) a basis can be taken for which scheme multiplication complexity is less than \(n^{1+\epsilon/2}\) and inversion complexity is less than \(n^{1+\epsilon}\). For some basis, when \(n=2\cdot 3^k\), complexity estimates \(n(\log_3 n)^{(\log_2\log_3n)/2+O(1)}\) for multiplication and estimates of the same order for inversion are obtained.


06E30 Boolean functions
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)