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

### MSC:

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

### Keywords:

scheme complexity; multiplication; complexity inversion