On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry

S. Ballet   ; J. Pieltant   ; M. Rambaud   ; H. Randriambololona   ; R. Rolland   ; J. Chaumine

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 76 (2021) no. 1, pp. 29-89

Résumé

In this paper, we give a survey of the known results concerning the tensor rank of multiplication in finite extensions of finite fields, enriched with some unpublished recent results, and we analyze these to enhance the qualitative understanding of the research area. In particular, we identify and clarify certain partially proved results and emphasise links with open problems in number theory, algebraic geometry, and coding theory. Bibliography: 92 titles.

Détail

Keywords: finite field, tensor rank of multiplication, function field.

Bibliographie

[1] N. Arnaud, Evaluation dérivée, multiplication dans les corps finis et codes correcteurs, PhD thesis, Univ. de la Méditerranée, Inst. Math. de Luminy, 2006

[2] K. Atighehchi, S. Ballet, A. Bonnecaze, R. Rolland, “Effective arithmetic in finite fields based on Chudnovsky's multiplication algorithm”, C. R. Math. Acad. Sci. Paris, 354:2 (2016), 137–141 | DOI | MR | Zbl

[3] K. Atighehchi, S. Ballet, A. Bonnecaze, R. Rolland, “Arithmetic in finite fields based on the Chudnovsky–Chudnovsky multiplication algorithm”, Math. Comp., 86:308 (2017), 2975–3000 | DOI | MR | Zbl

[4] R. C. Baker, G. Harman, J. Pintz, “The difference between consecutive primes. II”, Proc. London Math. Soc. (3), 83:3 (2001), 532–562 | DOI | MR | Zbl

[5] S. Ballet, Complexité bilinéaire de la multiplication dans les corps finis par interpolation sur des courbes algébriques, PhD thesis, Univ. de la Méditerranée, Inst. Math. de Luminy, 1998

[6] S. Ballet, “Curves with many points and multiplication complexity in any extension of $\mathbb{F}_q$”, Finite Fields Appl., 5:4 (1999), 364–377 | DOI | MR | Zbl

[7] S. Ballet, “Quasi-optimal algorithms for multiplication in the extensions of $\mathbb{F}_{16}$ of degree $13$, $14$, and $15$”, J. Pure Appl. Algebra, 171:2-3 (2002), 149–164 | DOI | MR | Zbl

[8] S. Ballet, “Low increasing tower of algebraic function fields and bilinear complexity of multiplication in any extension of $\mathbb{F}_q$”, Finite Fields Appl., 9:4 (2003), 472–478 | DOI | MR | Zbl

[9] S. Ballet, “An improvement of the construction of the D. V. and G. V. Chudnovsky algorithm for multiplication in finite fields”, Theoret. Comput. Sci., 352:1-3 (2006), 293–305 | DOI | MR | Zbl

[10] S. Ballet, “A note on the tensor rank of the multiplication in certain finite fields”, Algebraic geometry and its applications, SAGA (Papeete, 2007), Ser. Number Theory Appl., 5, World Sci. Publ., Hackensack, NJ, 2008, 332–342 | DOI | MR | Zbl

[11] S. Ballet, “On the tensor rank of the multiplication in the finite fields”, J. Number Theory, 128:6 (2008), 1795–1806 | DOI | MR | Zbl

[12] S. Ballet, N. Baudru, A. Bonnecaze, M. Tukumuli, On the effective construction of asymmetric Chudnovsky multiplication algorithms in finite fields without derivated evaluation, 2016, 23 pp., arXiv: 1611.02883

[13] S. Ballet, N. Baudru, A. Bonnecaze, M. Tukumuli, “On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation”, C. R. Math. Acad. Sci. Paris, 2017, no. 355, 729–733 | DOI | MR | Zbl

[14] S. Ballet, A. Bonnecaze, Thanh-Hung Dang, “On the scalar complexity of Chudnovsky$^2$ multiplication algorithm in finite fields”, Algebraic informatics, CAI 2019 (Niš, 2019), Lecture Notes in Comput. Sci., 11545, Springer, Cham, 2019, 64–75 | DOI | MR | Zbl

[15] S. Ballet, A. Bonnecaze, M. Tukumuli, “On the construction of elliptic Chudnovsky-type algorithms for multiplication in large extensions of finite fields”, J. Algebra Appl., 15:1 (2016), 1650005, 26 pp. | DOI | MR | Zbl

[16] S. Ballet, J. Chaumine, “On the bounds of the bilinear complexity of multiplication in some finite fields”, Appl. Algebra Engrg. Comm. Comput., 15:3-4 (2004), 205–211 | DOI | MR | Zbl

[17] S. Ballet, J. Chaumine, J. Pieltant, “Shimura modular curves and asymptotic symmetric tensor rank of multiplication in any finite field”, CAI'13: Algebraic informatics, Lecture Notes in Comput. Sci., 8080, Springer, Heidelberg, 2013, 160–172 | DOI | MR | Zbl

[18] S. Ballet, D. Le Brigand, “On the existence of non-special divisors of degree $g$ and $g-1$ in algebraic function fields over $\mathbb{F}_q$”, J. Number Theory, 116:2 (2006), 293–310 | DOI | MR | Zbl

[19] S. Ballet, D. Le Brigand, R. Rolland, “On an application of the definition field descent of a tower of function fields”, Arithmetics, geometry, and coding theory, AGCT 2005 (Marseilles, 2005), Sémin. Congr., 21, Soc. Math. France, Paris, 2010, 187–203 | MR | Zbl

[20] S. Ballet, J. Pieltant, “On the tensor rank of multiplication in any extension of $\mathbb{F}_2$”, J. Complexity, 27:2 (2011), 230–245 | DOI | MR | Zbl

[21] S. Ballet, J. Pieltant, “Tower of algebraic function fields with maximal Hasse–Witt invariant and tensor rank of multiplication in any extension of $\mathbb{F}_2$ and $\mathbb{F}_3$”, J. Pure Appl. Algebra, 222:5 (2018), 1069–1086 ; (2014), 15 pp., arXiv: 1201.3258 | DOI | MR | Zbl

[22] S. Ballet, J. Pieltant, M. Rambaud, J. Sijsling, “On some bounds for symmetric tensor rank of multiplication in finite fields”, Arithmetic, geometry, cryptography and coding theory, Contemp. Math., 686, Amer. Math. Soc., Providence, RI, 2017, 93–121 | DOI | MR | Zbl

[23] S. Ballet, C. Ritzenthaler, R. Rolland, “On the existence of dimension zero divisors in algebraic function fields defined over $\mathbb{F}_q$”, Acta Arith., 143:4 (2010), 377–392 | DOI | MR | Zbl

[24] S. Ballet, R. Rolland, “Multiplication algorithm in a finite field and tensor rank of the multiplication”, J. Algebra, 272:1 (2004), 173–185 | DOI | MR | Zbl

[25] S. Ballet, R. Rolland, “On the bilinear complexity of the multiplication in finite fields”, Arithmetic, geometry and coding theory, AGCT 2003 (Luminy, 2003), Sémin. Congr., 11, Soc. Math. France, Paris, 2005, 179–188 | MR | Zbl

[26] S. Ballet, R. Rolland, “Families of curves over any finite field attaining the generalized Drinfeld–Vladut bound”, Publ. Math. Besançon Algèbre Théorie Nr., 2011 (2011), 5–18 | DOI | MR | Zbl

[27] S. Ballet, A. Zykin, “Dense families of modular curves, prime numbers and uniform symmetric tensor rank of multiplication in certain finite fields”, Des. Codes Cryptogr., 87:2-3 (2019), 517–525 | DOI | MR | Zbl

[28] R. Barbulescu, J. Detrey, N. Estibals, P. Zimmermann, “Finding optimal formulae for bilinear maps”, Arithmetic of finite fields, Lecture Notes in Comput. Sci., 7369, Springer, Heidelberg, 2012, 168–186 | DOI | MR | Zbl

[29] U. Baum, M. A. Shokrollahi, “An optimal algorithm for multiplication in $\mathbb{F}_{256}/\mathbb{F}_4$”, Appl. Algebra Engrg. Comm. Comput., 2:1 (1991), 15–20 | DOI | MR | Zbl

[30] R. W. Brockett, D. Dobkin, “On the optimal evaluation of a set of bilinear forms”, Linear Algebra Appl., 19:3 (1978), 207–235 | DOI | MR | Zbl

[31] M. R. Brown, D. P. Dobkin, “An improved lower bound on polynomial multiplication”, IEEE Trans. Comput., C-29:5 (1980), 337–340 | DOI | MR | Zbl

[32] N. Bshouty, “Testers and their applications”, Electronic Colloquium on Computational Complexity (ECCC), 2012, TR12-011, 108 pp., \par https://eccc.weizmann.ac.il/report/2012/011/

[33] N. Bshouty, “Multilinear complexity is equivalent to optimal tester size”, Electronic Colloquium on Computational Complexity (ECCC), 2013, TR13-011, 39 pp. https://eccc.weizmann.ac.il/report/2013/011/

[34] N. H. Bshouty, M. Kaminski, “Multiplication of polynomials over finite fields”, SIAM J. Comput., 19:3 (1990), 452–456 | DOI | MR | Zbl

[35] P. Bürgisser, M. Clausen, M. A. Shokrollahi, Algebraic complexity theory, Grundlehren Math. Wiss., 315, Springer-Verlag, Berlin, 1997, xxiv+618 pp. | DOI | MR | Zbl

[36] I. Cascudo, R. Cramer, Chaoping Xing, “The torsion-limit for algebraic function fields and its application to arithmetic secret sharing”, Advances in cryptology – CRYPTO 2011 (Santa Barbara, CA, 2011), Lecture Notes in Comput. Sci., 6841, Springer, Heidelberg, 2011, 685–705 | DOI | MR | Zbl

[37] I. Cascudo, R. Cramer, Chaoping Xing, “Torsion limits and Riemann–Roch systems for function fields and applications”, IEEE Trans. Inform. Theory, 60:7 (2014), 3871–3888 | DOI | MR | Zbl

[38] I. Cascudo, R. Cramer, Chaoping Xing, An Yang, “Asymptotic bound for multiplication complexity in the extensions of small finite fields”, IEEE Trans. Inform. Theory, 58:7 (2012), 4930–4935 | DOI | MR | Zbl

[39] M. Cenk, F. Özbudak, “On multiplication in finite fields”, J. Complexity, 26:2 (2010), 172–186 | DOI | MR | Zbl

[40] M. Cenk, F. Özbudak, “Multiplication of polynomials modulo $x^n$”, Theoret. Comput. Sci., 412:29 (2011), 3451–3462 | DOI | MR | Zbl

[41] J. Chaumine, Corps de fonctions algébriques et algorithme de D. V. et G. V. Chudnovsky pour la multiplication dans les corps finis, PhD thesis, Univ. de la Polynésie Française, 2005, 93 pp.

[42] J. Chaumine, “Complexité bilinéaire de la multiplication dans des petits corps finis”, C. R. Math. Acad. Sci. Paris, 343:4 (2006), 265–266 | DOI | MR | Zbl

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

[44] D. Coppersmith, S. Winograd, “Matrix multiplication via arithmetic progressions”, STOC' 87 Proceedings of the nineteenth annual ACM symposium on theory of computing, ACM, New York, NY, 1987, 1–6 | DOI

[45] J.-M. Couveignes, R. Lercier, “Elliptic periods for finite fields”, Finite Fields Appl., 15:1 (2009), 1–22 | DOI | MR | Zbl

[46] H. F. de Groote, “Characterization of division algebras of minimal rank and the structure of their algorithm varieties”, SIAM J. Comput., 12:1 (1983), 101–117 | DOI | MR | Zbl

[47] F. Diamond, J. Shurman, A first course in modular forms, Grad. Texts in Math., 288, Springer-Verlag, New York, 2005, xvi+436 pp. | DOI | MR | Zbl

[48] V. Ducet, Construction of algebraic curves with many rational points over finite fields, PhD thesis, Univ. d'Aix-Marseille, Inst. Math. de Luminy, 2013, 100 pp. http://iml.univ-mrs.fr/~kohel/phd/thesis_ducet.pdf

[49] A. W. Dudek, “An explicit result for primes between cubes”, Funct. Approx. Comment. Math., 55:2 (2016), 177–197 | DOI | MR | Zbl

[50] N. D. Elkies, “Explicit modular towers”, Proceedings of the Thirty-fifth annual Allerton conference on communication, control and computing (Allerton House, Monticello, IL, 1997), Univ. of Illinois, Urbana-Champaign, 1997, 23–32

[51] N. D. Elkies, “Shimura curves computations”, Algorithmic number theory, ANTS-III (Portland, OR, 1998), Lecture Notes in Comput. Sci., 1423, Springer, Berlin, 1998, 1–47 | DOI | MR | Zbl

[52] N. D. Elkies, “Explicit towers of Drinfeld modular curves”, European congress of mathematics (Barcelona, 2000), v. 2, Progr. Math., 202, Birkhäuser, Basel, 2001, 189–198 | DOI | MR | Zbl

[53] N. D. Elkies, “Shimura curves for level-3 subgroups of the (2,3,7) triangle group, and some other examples”, Algorithmic number theory, ANTS-VII (Berlin, 2006), Lecture Notes in Comput. Sci., 4076, Springer, Berlin, 2006, 302–316 | DOI | MR | Zbl

[54] N. Estibals, Algorithmes et arithmétique pour l'implémentation de couplages cryptographiques, PhD thesis, Univ. de Lorraine, Nancy, 2013, 219 pp. https://tel.archives-ouvertes.fr/tel-00924743

[55] C. M. Fiduccia, Y. Zalcstein, “Algebras having linear multiplicative complexities”, J. Assoc. Comput. Mach., 24:2 (1977), 311–331 | DOI | MR | Zbl

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

[57] A. Garcia, H. Stichtenoth, “A tower of Artin–Schreier extensions of function fields attaining the Drinfeld–Vladut bound”, Invent. Math., 121:1 (1995), 211–222 | DOI | MR | Zbl

[58] A. Garcia, H. Stichtenoth, H.-G. Rück, “On tame towers over finite fields”, J. Reine Angew. Math., 2003:557 (2003), 53–80 | DOI | MR | Zbl

[59] V. D. Goppa, “Codes on algebraic curves”, Soviet Math. Dokl., 24 (1981), 170–172 | MR | Zbl

[60] V. Goppa, “Algebraico-geometric codes”, Math. USSR-Izv., 21:1 (1983), 75–91 | DOI | MR | Zbl

[61] E. Hallouin, “Computation of a cover of Shimura curves using a Hurwitz space”, J. Algebra, 321:2 (2009), 558–566 | DOI | MR | Zbl

[62] T. Hasegawa, An explicit Shimura tower of function fields over a number field: an application of Takeuchi's list, 2017, 8 pp., arXiv: 1701.07551

[63] Y. Ihara, “Some remarks on the number of rational points of algebraic curves over finite fields”, J. Fac. Sci. Univ. Tokyo Sect. IA Math., 28:3 (1981), 721–724 | MR | Zbl

[64] A. Lempel, G. Seroussi, S. Winograd, “On the complexity of multiplication in finite fields”, Theoret. Comput. Sci., 22:3 (1983), 285–296 | DOI | MR | Zbl

[65] C. Levrat, Tours de courbes de Shimura, Master's thesis, Univ. Paris-Saclay, Univ. de Versailles Saint-Quentin, Paris, 2018, 37 pp., \par https://perso.telecom-paristech.fr/rambaud/teaching/

[66] D. Mumford, Abelian varieties, Tata Inst. Fund. Res. Stud. Math., 5, Oxford Univ. Press, London, 1970, viii+242 pp. | MR | Zbl | Zbl

[67] M. Musty, S. Schiavone, J. Sijsling, J. Voight, “A database of Belyi maps”, Proceedings of the thirteenth algorithmic number theory symposium, ANTS XIII (Univ. of Wisconsin-Madison, WI, 2018), Open Book Ser., 2, Math. Sci. Publ., Berkeley, CA, 2019, 375–392 | DOI | MR | Zbl

[68] J. Pieltant, Tours de corps de fonctions algébriques et rang de tenseur de la multiplication dans les corps finis, PhD thesis, Univ. d'Aix-Marseille, Inst. Math. de Luminy, 2012, 96 pp. http://iml.univ-mrs.fr/theses/files/pieltant-these.pdf

[69] J. Pieltant, H. Randriam, “New uniform and asymptotic upper bounds on the tensor rank of multiplication in extensions of finite fields”, Math. Comp., 84:294 (2015), 2023–2045 | DOI | MR | Zbl

[70] M. Rambaud, “Finding optimal Chudnovsky–Chudnovsky multiplication algorithms”, Arithmetic of finite fields, WAIFI 2014 (Gebze, 2014), Lecture Notes in Comput. Sci., 9061, Springer, Cham, 2015, 45–60 | DOI | MR | Zbl

[71] M. Rambaud, Shimura curves and bilinear multiplication algorithms in finite fields, PhD thesis, Télécom ParisTech, 2017

[72] H. Randriam, “Hecke operators with odd determinant and binary frameproof codes beyond the probabilistic bound?”, Proceedings of the IEEE information theory workshop, ITW'10 (Dublin, 2010), IEEE, Piscataway, NJ, 2010, 1–5 | DOI | Zbl

[73] H. Randriam, Diviseurs de la forme 2D-G sans sections et rang de la multiplication dans les corps finis, 2011, 35 pp., arXiv: 1103.4335

[74] H. Randriambololona, “Bilinear complexity of algebras and the Chudnovsky–Chudnovsky interpolation method”, J. Complexity, 28:4 (2012), 489–517 | DOI | MR | Zbl

[75] H. Randriambololona, “$(2,1)$-separating systems beyond the probabilistic bound”, Israel J. Math., 195:1 (2013), 171–186 | DOI | MR | Zbl

[76] H. Randriambololona, “On products and powers of linear codes under componentwise multiplication”, Algorithmic arithmetic, geometry, and coding theory, AGCT 2013 (CIRM, Marseille, 2013), Contemp. Math., 637, Amer. Math. Soc., Providence, RI, 2015, 3–78 | DOI | MR | Zbl

[77] H. Randriam, “Gaps between prime numbers and tensor rank of multiplication in finite fields”, Des. Codes Cryptogr., 87:2–3 (2019), 627–645 | DOI | MR | Zbl

[78] G. Seroussi, A. Lempel, “On symmetric algorithms for bilinear forms over finite fields”, J. Algorithms, 5:3 (1984), 327–344 | DOI | MR | Zbl

[79] M. A. Shokrollahi, “Optimal algorithms for multiplication in certain finite fields using elliptic curves”, SIAM J. Comput., 21:6 (1992), 1193–1198 | DOI | MR | Zbl

[80] I. E. Shparlinski, M. A. Tsfasman, S. G. Vladut, “Curves with many points and multiplication in finite fields”, Coding theory and algebraic geometry, AGCT-3 (Luminy, 1991), Lectures Notes in Math., 1518, Springer, Berlin, 1992, 145–169 | DOI | MR | Zbl

[81] J. Sijsling, “Canonical models of arithmetic $(1;e)$-curves”, Math. Z., 273:1-2 (2013), 173–210 | DOI | MR | Zbl

[82] A. L. Toom, “The complexity of a scheme of functional elements realizing the multiplication of integers”, Soviet Math. Dokl., 4 (1963), 714–716 | MR | Zbl

[83] M. A. Tsfasman, “Goppa codes that are better than the Varshamov–Gilbert bound”, Problems Inform. Transmission, 18:3 (1982), 163–166 | MR | Zbl

[84] M. A. Tsfasman, “Some remarks on the asymptotic number of points”, Coding theory and algebraic geometry, AGCT-3 (Luminy, 1991), Lecture Notes in Math., 1518, Springer, Berlin, 1992, 178–192 | DOI | MR | Zbl

[85] M. A. Tsfasman, S. G. Vlăduţ, Algebraic-geometric codes, Math. Appl. (Soviet Ser.), 58, Kluwer Acad. Publ., Dordrecht, 1991, xxiv+667 pp. | DOI | MR | Zbl

[86] M. A. Tsfasman, S. G. Vlǎdu{t}, Th. Zink, “Modular curves, Shimura curves, and Goppa codes, better than Varshamov–Gilbert bound”, Math. Nachr., 109 (1982), 21–28 | DOI | MR | Zbl

[87] M. Tukumuli, Étude de la construction effective des algorithmes de type Chudnovsky pour la multiplication dans les corps finis, PhD thesis, Univ. d'Aix-Marseille, Inst. Math. de Luminy, 2013, 95 pp.

[88] J. Voight, Three lectures on Shimura curves, 2006, 15 pp., \par {9pt}\selectfont https://www.maths.usyd.edu.au/u/NumTheorySeminar/notes/shimura-magma-survey.pdf} \fontsize{8

[89] J. Voight, “Shimura curves of genus at most two”, Math. Comp., 78:266 (2009), 1155–1172 | DOI | MR | Zbl

[90] S. Winograd, “Some bilinear forms whose multiplicative complexity depends on the field of constants”, Math. Systems Theory, 10:2 (1976/77), 169–180 | DOI | MR | Zbl

[91] S. Winograd, “On multiplication in algebraic extension fields”, Theoret. Comput. Sci., 8:3 (1979), 359–377 | DOI | MR | Zbl

[92] Chaoping Xing, “Asymptotic bounds on frameproof codes”, IEEE Trans. Inform. Theory, 48:11 (2002), 2991–2995 | DOI | MR | Zbl