Complexity of computation in finite fields

S. B. Gashkov ; I. S. Sergeev

Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 4, pp. 95-131.

Résumé

We give a review of some works about the complexity of implementation of arithmetic operations in finite fields by Boolean circuits.

Bibliographie

[1] Akho A., Khopkroft D., Ulman D., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | MR

[2] Bleikhut R. E., Bystrye algoritmy tsifrovoi obrabotki signalov, Mir, M., 1989 | MR

[3] Bolotov A. A., Gashkov S. B., “O bystrom umnozhenii v normalnykh bazisakh konechnykh polei”, Diskret. mat., 13:3 (2001), 3–31 | DOI | MR | Zbl

[4] Bolotov A. A., Gashkov S. B., Frolov A. B., Elementarnoe vvedenie v ellipticheskuyu kriptografiyu: kriptograficheskie protokoly na ellipticheskikh krivykh, KomKniga, M., 2006

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

[6] Burtsev A. A., “O skhemakh dlya umnozheniya i invertirovaniya v kompozitnykh polyakh”, Chebyshëvskii sb., 7:1(17) (2006), 172–185 | MR | Zbl

[7] Burtsev A. A., “O slozhnosti bulevykh skhem dlya umnozheniya v konechnykh polyakh nechëtnoi kharakteristiki”, Materialy VI molodëzhnoi nauchnoi shkoly po diskretnoi matematike i eë prilozheniyam (Moskva, IPM RAN, aprel 2007), v. I, 2007, 13–16

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

[9] Burtsev A. A., Gashkov S. B., “O skhemakh dlya arifmetiki v kompozitnykh polyakh bolshoi kharakteristiki”, Chebyshëvskii sb., 7:1(17) (2006), 186–204 | MR | Zbl

[10] Vasilenko O. N., Teoretiko-chislovye algoritmy v kriptografii, Izd-vo MTsNMO, M., 2007

[11] Gashkov S. B., “Zamechaniya o bystrom umnozhenii mnogochlenov, preobrazovanii Fure i Khartli”, Diskret. mat., 12:3 (2000), 124–153 | DOI | MR | Zbl

[12] Gashkov S. B., Khokhlov R. A., “O glubine logicheskikh skhem dlya operatsii v polyakh $GF(2^n)$”, Chebyshëvskii sb., 4:4(8) (2003), 59–71 | MR | Zbl

[13] Gashkov S. B., Grinchuk M. I., Sergeev I. S., “O postroenii skhem summatorov maloi glubiny”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 14:1 (2007), 27–44 | MR | Zbl

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

[15] Gashkov S. B., Sergeev I. S., “O postroenii skhem logarifmicheskoi glubiny dlya invertirovaniya v konechnykh polyakh”, Diskret. mat., 20:4 (2008), 8–28 | DOI | MR | Zbl

[16] Gashkov S. B., Sergeev I. S., “O slozhnosti i glubine skhem dlya umnozheniya i invertirovaniya v nekotorykh polyakh $GF(2^n)$”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 2009, no. 4, 3–7 | MR

[17] Gashkov S. B., Sergeev I. S., “O slozhnosti umnozheniya i invertirovaniya v nekotorykh koltsakh mnogochlenov”, Materialy XI Mezhdunar. seminara “Diskretnaya matematika i eë prilozheniya” (Moskva, iyun 2012)

[18] Gashkov S. B., Chubarikov V. N., Arifmetika. Algoritmy. Slozhnost vychislenii, Nauka, M., 1996 | Zbl

[19] Grinchuk M. I., “Utochnenie verkhnei otsenki glubiny summatora i komparatora”, Diskretnyi analiz i issledovanie operatsii, 15:2 (2008), 12–22 | MR | Zbl

[20] Karatsuba A. A., Ofman Yu. P., “Umnozhenie mnogoznachnykh chisel na avtomatakh”, DAN SSSR, 145:2 (1962), 293–294

[21] Karatsuba A. A., “Slozhnost vychislenii”, Tr. Mat. in-ta RAN, 211, 1995, 186–202 | MR | Zbl

[22] Knut D., Iskusstvo programmirovaniya, v. 2, Poluchislennye algoritmy, Vilyams, M., 2004

[23] Lidl R., Niderraiter Kh., Konechnye polya, Mir, M., 1988 | Zbl

[24] Lupanov O. B., “O ventilnykh i kontaktno-ventilnykh skhemakh”, DAN SSSR, 111:6 (1956), 1171–1174 | MR | Zbl

[25] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Mosk. un-ta, M., 1984

[26] Maklellan Dzh. Kh., Reder Ch. M., Primenenie teorii chisel v tsifrovoi obrabotke signalov, Radio i cvyaz, M., 1983

[27] Noden P., Kitte K., Algebraicheskaya algoritmika, Mir, M., 1999

[28] Redkin N. P., “O minimalnoi realizatsii dvoichnogo summatora”, Problemy kibernetiki, 38, 1981, 181–216 | MR | Zbl

[29] Sergeev I. S., “O glubine skhem dlya mnogokratnogo slozheniya i umnozheniya chisel”, Materialy VI molodëzhnoi nauchnoi shkoly po diskretnoi matematike i eë prilozheniyam (Moskva, IPM RAN, aprel 2007), v. II, 2007, 40–45

[30] Sergeev I. S., “O postroenii skhem dlya perekhoda mezhdu polinomialnymi i normalnymi bazisami konechnykh polei”, Diskret. mat., 19:3 (2007), 89–101 | DOI | MR | Zbl

[31] Sergeev I. S., “Ob invertirovanii v konechnykh polyakh kharakteristiki 2 s logarifmicheskoi glubinoi”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 2007, no. 1, 28–33 | MR | Zbl

[32] Stolyarov G. K., Sposob parallelnogo umnozheniya v tsifrovykh vychislitelnykh mashinakh i ustroistvo dlya osuschestvleniya sposoba, Avt. svid-vo kl. 42, t. 14, No 126668, 1960

[33] Toom A. L., “O slozhnosti skhemy iz funktsionalnykh elementov, realizuyuschei umnozhenie tselykh chisel”, DAN SSSR, 150 (1963), 496–498 | MR | Zbl

[34] Khrapchenko V. M., “Ob asimptoticheskoi otsenke vremeni slozheniya parallelnogo summatora”, Problemy kibernetiki, 19, 1967, 107–120

[35] Khrapchenko V. M., “Nekotorye otsenki dlya vremeni umnozheniya”, Problemy kibernetiki, 33, 1978, 221–227 | Zbl

[36] Khrapchenko V. M., “Ob odnoi iz vozmozhnostei utochneniya otsenok dlya zaderzhki parallelnogo summatora”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 14:1 (2007), 87–93 | MR | Zbl

[37] Chashkin A. V., “Bystroe umnozhenie i slozhenie tselykh chisel”, Diskretnaya matematika i eë prilozheniya, v. II, Izd-vo TsPI pri mekh.-mat. f-te MGU, M., 2001, 91–110

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

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

[40] Agnew G. B., Mullin R. C., Onyszchuk I. M., Vanstone S. A., “An implementation for a fast public-key cryptosystem”, J. Cryptol., 3 (1991), 63–79 | DOI | MR | Zbl

[41] Ahmadi O., Menezes A., Irreducible polynomials of maximum weight, Preprint, 2005 | MR

[42] Ash D. W., Blake I. F., Vanstone S. A., “Low complexity normal bases”, Discrete Appl. Math., 25 (1989), 191–210 | DOI | MR | Zbl

[43] Avizienis A., “Signed-digit number representation for fast parallel arithmetic”, IEEE Trans. Electron. Comput., 10 (1961), 389–400 | DOI | MR

[44] Bailey D. V., Paar C., “Efficient arithmetic in finite fields extensions with application in elliptic curve cryptography”, J. Cryptol., 14 (2001), 153–176 | MR | Zbl

[45] Bajard J.-C., Imbert L., Plantard T., “Modular number systems: Beyond the Mersenne family”, SAC' 04, 11th Int. Workshop on Selected Areas in Cryptography, 2004, 159–169 | MR

[46] Baktir S., Kumar S., Paar C., Sunar B., “A state-of-the-art elliptic curve cryptographic processor operating in the frequency domain”, Mobile Networks Appl., 12:4 (2007), 259–270 | DOI

[47] Baktir S., Pelzl J., Wollinger T., Sunar B., Paar C., “Optimal tower fields for hyperelliptic curve cryptosystems”, Proc. IEEE 38th ACSSC, 2004

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

[49] Baktir S., Sunar B., “Achieving efficient polynomial multiplication in Fermat fields using fast Fourier transform”, Proc. ACMSE' 06, ACM Press, 2006, 549–554

[50] Baktir S., Sunar B., “Frequency domain finite field arithmetic for elliptic curve cryptography”, Proc. ISCIS 2006, Lect. Notes Comput. Sci., 4263, Springer, Berlin, 2006, 991–1001 | DOI

[51] Ballet S., Chaumine J., Pieltant J., Rolland R., On the tensor rank of multiplication in finite extensions of finite fields, 2011, arXiv: 1107.1184

[52] Barret P. D., “Implementing the Rivest, Shamir and Adleman public key encryption algorithm on a standard digital signal processor”, Advances in Cryptology, Proc. Crypto-86, Lect. Notes Comput. Sci., 263, Springer, Berlin, 1987, 311–323 | DOI | MR

[53] Barreto P. S. M. L., Galbraith S., O'Eigeartaigh C., Scott M., Efficient pairing computation on supersingular Abelian varieties, Cryptology ePrint Archive, Report 2004/375 http://eprint.iacr.org/2004/375

[54] Barreto P. S. L. M., Kim H. Y., Lynn B., Scott M., “Efficient algorithms for pairing-based cryptosystems”, Proc. Crypto-2002, Lect. Notes Comput. Sci., 2442, Springer, Berlin, 2002, 354–368 | DOI | MR | Zbl

[55] Beame P., Cook S., Hoover H., “Log depth circuits for division and related problems”, SIAM J. Comput., 15:4 (1986), 994–1003 | DOI | MR | Zbl

[56] Bernstein D. J., Multidigit Multiplication for Mathematicians, , 2004 http://cr.yp.to/papers.html#m3

[57] Bernstein D. J., “Batch binary Edwards”, Advances in Cryptology – CRYPTO 2009, 29th Annual Int. Cryptology Conf. (Santa Barbara, CA, USA, August 16–20, 2009), Proceedings, Lect. Notes Comput. Sci., 5677, ed. S. Halevi, Springer, Berlin, 2009, 317–336 | DOI | MR | Zbl

[58] Bernstein D. J., Lange T., “Type-II optimal polynomial bases”, Arithmetic of Finite Fields, Third International Workshop, WAIFI 2010 (Istanbul, Turkey, June 27–30, 2010), Proceedings, Lect. Notes Comput. Sci., 6087, Springer, Berlin, 2010, 41–61 | DOI | MR | Zbl

[59] Bertoni G., Guajardo J., Kumar S., Orlando G., Paar C., Wolinger T., “Efficient $GF(p^m)$ arithmetic architectures for cryptographic applications”, CT-RSA' 03, Proc. of the 2003 RSA Conf. on the Cryptographers' Track, Lect. Notes Comput. Sci., 2612, Springer, Berlin, 2003, 158–175 | DOI | MR | Zbl

[60] Blake I., Roth R., Seroussi G., Efficient arithmetic in $GF(2^n)$ through palindromic representation, HPL-98-134, Hewlett-Packard, 1998

[61] Blake I., Seroussi G., Smart N., Elliptic Curves in Cryptography, Cambridge Univ. Press, Cambridge, 1999 | MR | Zbl

[62] Blake I., Seroussi G., Smart N., Advances in elliptic curve cryptography, Cambridge Univ. Press, Cambridge, 2005 | MR | Zbl

[63] Brauer A., “On addition chains”, Bull. Am. Math. Soc., 45 (1939), 736–739 | DOI | MR | Zbl

[64] Brent R. P., Gaudry P., Thome E., Zimmerman P., Faster multiplication in $GF(2)[x]$, Preprint no. 6359, INRIA, 2007

[65] Brent R., Gustavson F., Yun D., “Fast solution of Toeplitz systems of equations and computation of Padé approximants”, J. Algorithms, 1 (1980), 259–295 | DOI | MR | Zbl

[66] Brent R., Kung H., “Fast algorithms for manipulating formal power series”, J. ACM, 25 (1978), 581–595 | DOI | MR | Zbl

[67] Canright D., A very compact Rijndael S-box, Technical Report NPS-MA-04-001, Naval Postgraduate School, 2004 http://edocs.nps.edu/npspubs/scholarly/TR/2004/NPS-MA-04-001.pdf

[68] Cantor D., “On arithmetic algorithms over finite fields”, J. Combin. Theory Ser. A, 50 (1989), 285–300 | DOI | MR | Zbl

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

[70] Chang K., Kim H., Kang J., Cho H., “An extension of TYT algorithm for $GF((2^n)^m)$ using precomputation”, Inform. Process. Lett., 92 (2004), 231–234 | DOI | MR | Zbl

[71] Chor B., Goldreich O., “An improved parallel algorithm for integer GCD”, Algorithmica, 5 (1990), 1–10 | DOI | MR | Zbl

[72] Chudnovsky D. V., Chudnovsky G. V., “Algebraic complexities and algebraic curves over finite fields”, J. Complexity, 4 (1988), 285–316 | DOI | MR | Zbl

[73] Cook S., On the minimum computation time of functions, Ph. D. Thesis, Harvard Univ., 1966

[74] De A., Kurur P. P., Saha C., Saptharishi R., “Fast integer multiplication using modular arithmetic”, Proc. 40th ACM Symp. on Theory of Computing, 2008, 499–506 | MR | Zbl

[75] Demenkov E., Kojevnikov A., Kulikov A. S., Yaroslavtsev G., “New upper bounds on the Boolean circuit complexity of symmetric functions”, Inform. Process. Lett., 110:7 (2010), 264–267 | DOI | MR | Zbl

[76] Doche C., “Redundant trinomials for finite fields of characteristic 2”, ACISP 2005, Lect. Notes Comput. Sci., 3574, Springer, Berlin, 2005, 122–133 | DOI | Zbl

[77] Dunne P. E., The Complexity of Boolean Networks, Academic Press, London, 1988 | MR | Zbl

[78] Duursma I., Lee H.-S., “Tate pairing implementation for hyperelliptic curves $y^2=x^p-x+d$”, Proc. Asiacrypt-2003, Lect. Notes Comput. Sci., 2894, Springer, Berlin, 2003, 111–123 | DOI | MR | Zbl

[79] Duursma I., Lee H.-S., Tate pairing implementation for tripartite key agreement, Cryptology ePrint Archive, Report 2003/053 http://eprint.iacr.org/2003/053

[80] Eberly W., “Very fast parallel polynomial arithmetic”, SIAM J. Comput., 18 (1989), 955–976 | DOI | MR | Zbl

[81] Erdem S., Yanik T., Koc C., “Polynomial basis multiplication over $GF(2^n)$”, Acta Appl. Math., 93 (2006), 33–55 | DOI | MR | Zbl

[82] Erdős P., “Remarks on number theory. III: On addition chains”, Acta Arith., 6 (1960), 77–81 | MR | Zbl

[83] Fan H., Hasan M. A., “Alternative to the Karatsuba algorithm for software implementation of $GF(2^n)$ multiplication”, Information Security, 3:2 (2009), 60–65 | DOI

[84] Feisel S., von zur Gathen J., Shokrollahi M. A., “Normal bases via general Gauss periods”, Math. Comput., 68:225 (1999), 271–290 | DOI | MR | Zbl

[85] Fürer M., “Faster integer multiplication”, Proc. 39th ACM STOC 2007 Conf., New York, 2007, 57–66 | MR | Zbl

[86] Gao S., von zur Gathen J., Panario D., “Gauss periods and fast exponentiation in finite fields”, Proc. Latin' 95 (Valparaiso, Chile), Lect. Notes Comput. Sci., 911, Springer, Berlin, 1995, 311–322 | DOI | Zbl

[87] Von zur Gathen J., “Inversion in finite fields”, J. Symbolic Comput., 9 (1990), 175–183 | DOI | MR | Zbl

[88] Von zur Gathen J., Gerhard J., “Arithmetic and factorization of polynomials over $GF(2)$”, Proc. ISSAC' 96, Zürich, 1996, 1–9 | Zbl

[89] Von zur Gathen J., Gerhard J., Modern Computer Algebra, Cambridge Univ. Press, Cambridge, 1999 | MR | Zbl

[90] Von zur Gathen J., Nöcker M., “Exponentiation in finite fields: theory and practice”, Applied Algebra, Proc. AAECC-12, Lect. Notes Comput. Sci., 1255, Springer, Berlin, 1997, 88–113 | DOI | MR | Zbl

[91] Von zur Gathen J., Nöcker M., “Fast arithmetic with general Gauss periods”, Theor. Comput. Sci., 315 (2004), 419–452 | DOI | MR | Zbl

[92] Von zur Gathen J., Shokrollahy M. A., Shokrollahy J., “Efficient multiplication using type 2 optimal normal bases”, Arithmetic of Finite Fields, First International Workshop, WAIFI 2007 (Madrid, Spain, June 21–22, 2007), Proceedings, Lect. Notes Comput. Sci., 4547, eds. C. Carlet, B. Sunar, Springer, Berlin, 2007, 55–68 | DOI | MR | Zbl

[93] Gaudry P., Kruppa A., Zimmermann P., “A GMP-based implementation of Schönhage–Strassen's large integer multiplication algorithm”, ISSAC' 07, Waterloo, Ontario, Canada, 2007

[94] Granger R., Page D., Stam M., “Hardware and software normal basis arithmetic for pairing based cryptography in characteristic three”, IEEE Trans. Comput., 54:7 (2005), 852–860 | DOI

[95] Grove E., Proofs with potential, Ph. D. Thesis, U. C. Berkeley, 1993

[96] Guajardo J., Güneysu T., Kumar S., Paar C., Pelzl J., “Efficient hardware implementation of finite fields with application to cryptography”, Acta Appl. Math., 93 (2006), 75–118 | DOI | MR | Zbl

[97] Hankerson D., López J. H., Menezes A., “Software implementation of elliptic curve cryptography over binary fields”, CHES 2000, Lect. Notes Comput. Sci., 1965, Springer, Berlin, 2000, 1–23 | DOI

[98] Hastad J., Leighton T., Division in $O(\log n)$ depth using $O(n^{1 + \epsilon})$ processors, , 1986 http://www.nada.kth.se/~johanh/paraldivision.pdf

[99] Huang X., Pan V., “Fast rectangular matrix multiplication and applications”, J. Complexity, 14 (1998), 257–299 | DOI | MR | Zbl

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

[101] Jungnickel D., Finite Fields. Structure and Arithmetic, Wissenschaftsverlag, Mannheim, 1993 | MR | Zbl

[102] Kaltofen E., Shoup V., “Subquadratic-time factoring of polynomials over finite fields”, Math. Comput., 67:223 (1998), 1179–1197 | DOI | MR | Zbl

[103] Kedlaya K., Umans C., “Fast modular composition in any characteristic”, Proc. 49th IEEE Symp. on Foundations of Comput. Sci., FOCS, 2008, 146–155

[104] Kerins T., Marnane W. P., Popovici E. M., Barreto P. S. L. M., “Efficient hardware for Tate pairing calculation in characteristic three”, Proc. CHES-2005, Lect. Notes Comput. Sci., 3659, Springer, Berlin, 2005, 412 | DOI

[105] Knuth D., “The analysis of algorithms”, Proc. Int. Congress of Math. (Nice, France, 1970), v. 3, Paris, 1971, 269–274 | MR | Zbl

[106] Kwon S., Efficient Tate pairing computation for supersingular elliptic curves over binary fields, Cryptology ePrint Archive, Report 2004/303 http://eprint.iacr.org/2004/303

[107] Lee E., Lee H.-S., Lee Y., Fast computation of Tate pairing on general divisors for hyperelliptic curves of genus 3, Cryptology ePrint Archive, Report 2006/125 http://eprint.iacr.org/2006/125

[108] Litow B. E., Davida G. I., “$ O(\log n) $ parallel time finite field inversion”, VLSI Algorithms and Architectures, Lect. Notes Comput. Sci., 319, Springer, Berlin, 1988, 74–80 | DOI | MR

[109] Massey J. L., Omura J. K., Apparatus for finite fields computation, US patent 4587627, 1986

[110] Mastrovito E. D., VLSI architectures for computation in Galois fields, Ph. D. Thesis, Linköping Univ., 1991

[111] Mateer T., Fast Fourier algorithms with applications, Ph. D. Thesis, Clemson Univ., 2008

[112] Menezes A. J., van Oorshot P. C., Vanstone S. A., Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997 | MR | Zbl

[113] Moenck R., “Fast computation of GCDs”, Proc. 5th Ann. ACM Symp. on Theory of Computing, 1973, 142–151 | MR | Zbl

[114] Möller N., “On Schönhhage's algorithm and subquadratic integer gcd computation”, Math. Comput., 77 (2008), 589–607 | DOI | MR | Zbl

[115] Morii M., Kasahara M., “Efficient construction of gate circuit for computing multiplicative inverses in $GF(2^n)$”, Trans. IEICE, 72:1 (1989), 37–42

[116] Mullin R. C., Onyszchuk I. M., Vanstone S. A., Wilson R. M., “Optimal normal bases in $GF(p^n)$”, Discrete Appl. Math., 22 (1988/1989), 149–161 | DOI | MR

[117] Negre C., Plantard T., Prime field multiplication in adapted modular system using Lagrange representation, Preprint, 2005

[118] Paar C., Effective VLSI architectures for bit paralel computation in Galois fields, Ph. D. Thesis, Universität GH Essen, 1994

[119] Paar C., Fan J. L., Efficient Inversion in Tower Fields of Characteristic Two, ISIT, Ulm, 1997

[120] Paar C., Fleischmann P., Roelse P., “Effective multiplier architectures for Galois fields $GF(2^{4n})$”, IEEE Trans. Comput., 47:2 (1998), 162–170 | DOI | MR

[121] Paar C., Fleischmann P., Soria-Rodriges P., “Fast arithmetic for public-key algorithms in Galois fields with composite exponents”, IEEE Trans. Comput., 48:10 (1999), 1025–1034 | DOI | MR

[122] Page D., Smart N. P., “Hardware implementation of finite fields of characteristic three”, Proc. CHES-2002, Lect. Notes Comput. Sci., 2523, Springer, Berlin, 2002, 529–539 | DOI | Zbl

[123] Paterson M., Pippenger N., Zwick U., “Optimal carry save networks”, Boolean Function Complexity, London Math. Soc. Lect. Note Ser., 169, Cambridge Univ. Press, Cambridge, 1992, 174–201 | MR

[124] Paterson M., Zwick U., “Shallow circuits and concise formulae for multiple addition and multiplication”, Comput. Complexity, 3 (1993), 262–291 | DOI | MR | Zbl

[125] Reif J., Tate S., “Optimal size integer division circuits”, SIAM J. Comput., 19:5 (1990), 912–925 | DOI | MR

[126] Reyhani-Masoleh A., Hasan M. A., “On effective normal basis multiplication”, Proc. IndiaCRYPT-2000, Lect. Notes Comput. Sci., 1977, Springer, Berlin, 2000, 213–224 | DOI | MR | Zbl

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

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

[129] Schönhage A., Strassen V., “Schnelle Multiplikation großer Zahlen”, Computing, 7 (1971), 271–282 | DOI | MR

[130] Seguin J. E., “Low complexity normal bases”, Discrete Appl. Math., 28 (1990), 309–312 | DOI | MR | Zbl

[131] Shparlinski I. E., Tsfasman M. A., Vladuts S. G., “Curves with many points and multiplication in finite fields”, Coding Theory and Algebraic Geometry, Lect. Notes Math., 1518, Springer, Berlin, 1992, 145–169 | DOI | MR

[132] Stehlé D., Zimmermann P., “A binary recursive GCD algorithm”, Proc. ANTS-VI (Burlington, USA, 2004), Lect. Notes Comput. Sci., 3076, Springer, Berlin, 2004, 411–425 | DOI | MR | Zbl

[133] Strassen V., “Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten”, Numer. Math., 20 (1973), 238–251 | DOI | MR | Zbl

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

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

[136] Umans C., “Fast polynomial factorization and modular composition in small characteristic”, Proc. 40th Symp. on Theory of Computing, STOC, 2008, 481–490 | MR | Zbl

[137] Wallace C. S., “A suggestion for a fast multiplier”, IEEE Trans. Electron. Comput., 13 (1964), 14–17 | DOI | Zbl

[138] Wegener I., The Complexity of Boolean Functions, Wiley, Stuttgart, 1987 | MR | Zbl

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