Geodesic
An application of the method of additive chains to inversion in finite fields
Diskretnaya Matematika, Tome 18 (2006) no. 4, pp. 56-72.

Voir la notice de l'article provenant de la source Math-Net.Ru

We obtain estimates of complexity and depth of Boolean inverter circuits in normal and polynomial bases of finite fields. In particular, we show that it is possible to construct a Boolean inverter circuit in the normal basis of the field $\mathit{GF}(2^n)$ whose complexity is at most $(\lambda(n-1)+(1+o(1))\lambda(n)/\lambda(\lambda(n)))M(n)$ and the depth is at most $(\lambda(n-1)+2)D(n)$, where $M(n)$, $D(n)$ are the complexity and the depth, respectively, of the circuits for multiplication in this basis and $\lambda(n)=\lfloor\log_2n\rfloor$. 
@article{DM_2006_18_4_a5,
     author = {S. B. Gashkov and I. S. Sergeev},
     title = {An application of the method of additive chains to inversion in finite fields},
     journal = {Diskretnaya Matematika},
     pages = {56--72},
     publisher = {mathdoc},
     volume = {18},
     number = {4},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_4_a5/}
}
TY  - JOUR
AU  - S. B. Gashkov
AU  - I. S. Sergeev
TI  - An application of the method of additive chains to inversion in finite fields
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 56
EP  - 72
VL  - 18
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_4_a5/
LA  - ru
ID  - DM_2006_18_4_a5
ER  - 
%0 Journal Article
%A S. B. Gashkov
%A I. S. Sergeev
%T An application of the method of additive chains to inversion in finite fields
%J Diskretnaya Matematika
%D 2006
%P 56-72
%V 18
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2006_18_4_a5/
%G ru
%F DM_2006_18_4_a5
S. B. Gashkov; I. S. Sergeev. An application of the method of additive chains to inversion in finite fields. Diskretnaya Matematika, Tome 18 (2006) no. 4, pp. 56-72. http://geodesic.mathdoc.fr/item/DM_2006_18_4_a5/

[1] Agnew G. B., Beth T., Mullin R. C., Vanstone S. A., “Arithmetic operations in $\operatorname{\mathit{GF}}(2^m)$”, J. Crypt., 6 (1993), 3–13 | DOI | MR | Zbl

[2] Litow B., Davida G., “$O(\log n)$ parallel time finite field inversion”, Lecture Notes Computer Sci., 319, 1988, 74–80 | MR | Zbl

[3] Von zur Gathen J., “Inversion in finite fields using logarithmic depth”, J. Symb. Comput., 9 (1990), 175–183 | DOI | MR | Zbl

[4] Knut D., Iskusstvo programmirovaniya, t. 2: Poluchislennye algoritmy, Vilyams, Moskva, 2004

[5] Von zur Gathen J., Nöcker M., “Exponentiation in finite fields: theory and practice”, Lecture Notes Computer Sci., 1255, 1997, 88–113 | MR | Zbl

[6] Itoh T., Tsujii S., “A fast algorithm for computing multiplicative inverses in $\operatorname{\mathit{GF}}(2^n)$ using normal basis”, Inform. Comput., 78 (1988), 171–177 | DOI | MR | Zbl

[7] Takagi N., Yoshiki J., Takagi K., “A fast algorithm for multiplicative inversion in $\operatorname{\mathit{GF}}(2^n)$ using normal basis”, IEEE Trans. Comput., 50:5 (2001), 394–398 | DOI | MR

[8] Chang K., Kim H., Kang J., Cho H., “An extension of TYT algorithm for $\operatorname{\mathit{GF}}((2^n)^m)$ using precomputation”, Inform. Proc. Lett., 92 (2004), 231–234 | DOI | MR

[9] Yao A. C., “On the evaluation of powers”, SIAM J. Comput., 5 (1976), 100–103 | DOI | MR | Zbl

[10] Von zur Gathen J., Gerhard J., Modern computer algebra, Cambridge Univ. Press, Cambridge, 1999 | MR

[11] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, Moskva, 1984

[12] Massey J. L., Omura J. K., Apparatus for finite fields computation, US Patent Application 1986, No4587627

[13] Bolotov A. A., Gashkov S. B., “O bystrom umnozhenii v normalnykh bazisakh konechnykh polei”, Diskretnaya matematika, 13:3 (2001), 3–31

[14] Gao S., von zur Gathen J., Panario D., Shoup V., “Algorithm for exponentiation in finite field”, J. Symb. Comput., 29 (2000), 879–889 | DOI | MR | Zbl

[15] Gashkov S. B., Khokhlov R. A., “O glubine logicheskikh skhem dlya operatsii v polyakh $\operatorname{\mathit{GF}}(2^{n})$”, Chebyshevskii sbornik, 4:4(8) (2003), 59–71 | MR

[16] Pan V., “Complexity of parallel matrix computations”, Theor. Comput. Sci., 54 (1987), 65–85 | DOI | MR | Zbl