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

What is it about?

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(ε^{−1}n^{w+ε}) and depth O(ε^{−1}log n) , where ɛ > 0, and w < 1.667 is the exponent of multiplication of \sqrt{n} × \sqrt{n} and \sqrt{n} × n matrices. Inversion over Gaussian normal bases is realised by a circuit of complexity O(ε^{−b}n^{1+cε|logε|}) and depth O(ε^{−1}log n) , where b, c are constants.

Featured Image