On design of circuits of logarithmic depth for inversion in finite fields

S. B. Gashkov ; I. S. Sergeev

Diskretnaya Matematika, Tome 20 (2008) no. 4, pp. 8-28

Résumé

We suggest a method of realisation of inversion over the standard bases of finite fields $GF(p^n)$ by means of circuits over $GF(p)$ of complexity $O(\varepsilon^{-1}n^{w+\varepsilon})$ and depth $O(\varepsilon^{-1}\log n)$, where $\varepsilon>0$, and $w1.667$ is the exponent of multiplication of $\sqrt n\times\sqrt n$ and $\sqrt n\times n$ matrices. Inversion over Gaussian normal bases is realised by a circuit of complexity $O(\varepsilon^{-b}n^{1+c\varepsilon|\log\varepsilon|})$ and depth $O(\varepsilon^{-1}\log n)$, where $b,c$ are constants.