Geodesic
On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic~2
Diskretnaya Matematika, Tome 25 (2013) no. 1, pp. 3-32.

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

@article{DM_2013_25_1_a0,
     author = {S. B. Gashkov and I. S. Sergeev},
     title = {On complexity and depth of {Boolean} circuits for multiplication and inversion over finite fields of characteristic~2},
     journal = {Diskretnaya Matematika},
     pages = {3--32},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2013_25_1_a0/}
}
TY  - JOUR
AU  - S. B. Gashkov
AU  - I. S. Sergeev
TI  - On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic~2
JO  - Diskretnaya Matematika
PY  - 2013
SP  - 3
EP  - 32
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2013_25_1_a0/
LA  - ru
ID  - DM_2013_25_1_a0
ER  - 
%0 Journal Article
%A S. B. Gashkov
%A I. S. Sergeev
%T On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic~2
%J Diskretnaya Matematika
%D 2013
%P 3-32
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2013_25_1_a0/
%G ru
%F DM_2013_25_1_a0
S. B. Gashkov; I. S. Sergeev. On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic~2. Diskretnaya Matematika, Tome 25 (2013) no. 1, pp. 3-32. http://geodesic.mathdoc.fr/item/DM_2013_25_1_a0/

[1] Schönhage A., “Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2”, Acta Inf., 7 (1977), 395–398 | DOI | MR

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

[3] Mateer T., Fast Fourier algorithms with applications, PhD Thesis, Clemson Univ., 2008

[4] Schönhage A., “Schnelle Berechnung von Kettenbruchentwicklungen”, Acta Inf., 1 (1971), 139–144 | DOI

[5] Strassen V., “The computational complexity of continued fractions”, SIAM J. Comput., 12 (1983), 1–27 | DOI | MR | Zbl

[6] Afanassiev V. B., Davydov A. A., “Finite field tower: iterated presentation and complexity of arithmetic”, Finite Fields Appl., 8 (2002), 216–232 | DOI | MR | Zbl

[7] Baktir S., Sunar B., “Optimal tower fields”, IEEE Trans. Comput., 53 (2004), 1231–1243 | DOI | Zbl

[8] Burtsev A. A., Gashkov I. B., Gashkov S. B., “O slozhnosti bulevykh skhem dlya arifmetiki v nekotorykh bashnyakh konechnykh polei”, Vestnik Moskovskogo universiteta, Ser. 1: Matematika, mekhanika, 2006, no. 5, 10–16 | MR | Zbl

[9] Gashkov S. B., Sergeev I. S., “O slozhnosti i glubine skhem dlya umnozheniya i invertirovaniya v nekotorykh polyakh $GF(2^n)$”, Vestnik Moskovskogo universiteta, Ser. 1: Matematika, mekhanika, 2009, no. 4, 3–7 | MR

[10] Gashkov S. B., Sergeev I. S., “Algoritmy bystrogo preobrazovaniya Fure”, Diskretnaya matematika i ee prilozheniya, v. V, IPM RAN, Moskva, 2009, 3–23

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

[12] Cooley J. W., Tukey J. W., “An algorithm for the machine calculation of complex Fourier series”, Math. Comput., 19 (1965), 297–301 | DOI | MR | Zbl

[13] Bleikhut R., Bystrye algoritmy tsifrovoi obrabotki signalov, Mir, Moskva, 1989 | MR

[14] Good I. J., “The interaction algorithm and practical Fourier analysis”, J. R. Statist. Soc. B, 20 (1958), 361–372 | MR | Zbl

[15] Cantor D., Kaltofen E., “On fast multiplication of polynomials over arbitrary algebras”, Acta Inf., 28 (1991), 693–701 | DOI | MR | Zbl

[16] Lidl R., Hideppaitep Kh., Konechnye polya, v. 1, Mir, Moskva, 1988 | Zbl

[17] Shënkhage A., Shtrassen V., “Bystroe umnozhenie bolshikh chisel”, Kiberneticheskii sbornik, 10, 1973, 87–98

[18] Sergeev I. S., “Regulyarizatsiya nekotorykh otsenok slozhnosti umnozheniya mnogochlenov”, Materialy VII molodezhnoi nauchnoi shkoly po diskretnoi matematike i ee prilozheniyam, v. II, IPM RAN, Moskva, 2009, 26–32

[19] Gashkov S. B., Sergeev I. S., “O primenenii metoda additivnykh tsepochek k invertirovaniyu v konechnykh polyakh”, Diskretnaya matematika, 18:4 (2006), 56–72 | DOI | MR | Zbl

[20] Bolotov A. A., Gashkov S. B., Frolov A. B., Chasovskikh A. A., Elementarnoe vvedenie v ellipticheskuyu kriptografiyu: algebraicheskie i algoritmicheskie osnovy, KomKniga, Moskva, 2006

[21] Trifonov P. V., Fedorenko S. V., “Metod bystrogo vychisleniya preobrazovaniya Fure nad konechnym polem”, Problemy peredachi informatsii, 39:3 (2003), 3–10 | MR | Zbl

[22] Wu X., Wagh M., Chen N., Wang I., Yan Z., “Composite cyclotomic Fourier transforms with reduced complexities”, IEEE Trans. Signal Proc., 59 (2011), 2136–2145 | DOI | MR

[23] Costa E., Fedorenko S. V., Trifonov P. V., “On computing the syndrome polynomial in Reed–Solomon decoder”, Eur. Trans. Telecomms, 15 (2004), 337–342 | DOI

[24] Zakharova T. G., “Vychislenie preobrazovaniya Fure v polyakh kharakteristiki 2”, Problemy peredachi informatsii, 28:2 (1992), 62–77 | MR | Zbl