Geodesic
An application of the method of additive chains to inversion in finite fields
Diskretnaya Matematika, Tome 18 (2006) no. 4, pp. 56-72
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2006},
     volume = {18},
     number = {4},
     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
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
%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