On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry
- Autores: Ballet S.1, Pieltant J.2, Rambaud M.3, Randriambololona H.4, Rolland R.1, Chaumine J.5
-
Afiliações:
- Institut de Mathématiques de Marseille
- Conservatoire National des Arts et Métiers
- Telecom ParisTech
- Agence Nationale de Sécurité des Systèmes d'Information
- Université de la Polynésie Française
- Edição: Volume 76, Nº 1 (2021)
- Páginas: 31-94
- Seção: Articles
- URL: https://journals.rcsi.science/0042-1316/article/view/133641
- DOI: https://doi.org/10.4213/rm9928
- ID: 133641
Citar
Resumo
Palavras-chave
Sobre autores
Stéphane Ballet
Institut de Mathématiques de Marseille
Email: stephane.ballet@univ-amu.fr
Julia Pieltant
Conservatoire National des Arts et Métiers
Matthieu Rambaud
Telecom ParisTech
Hugues Randriambololona
Agence Nationale de Sécurité des Systèmes d'Information
Robert Rolland
Institut de Mathématiques de Marseille
Email: robert.rolland@acrypta.fr
PhD, Professor
Jean Chaumine
Université de la Polynésie Française
Bibliografia
- N. Arnaud, Evaluation derivee, multiplication dans les corps finis et codes correcteurs, PhD thesis, Univ. de la Mediterranee, Inst. Math. de Luminy, 2006
- 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
- 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
- R. C. Baker, G. Harman, J. Pintz, “The difference between consecutive primes. II”, Proc. London Math. Soc. (3), 83:3 (2001), 532–562
- S. Ballet, Complexite bilineaire de la multiplication dans les corps finis par interpolation sur des courbes algebriques, PhD thesis, Univ. de la Mediterranee, Inst. Math. de Luminy, 1998
- S. Ballet, “Curves with many points and multiplication complexity in any extension of $mathbb{F}_q$”, Finite Fields Appl., 5:4 (1999), 364–377
- 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
- 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
- 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
- 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
- S. Ballet, “On the tensor rank of the multiplication in the finite fields”, J. Number Theory, 128:6 (2008), 1795–1806
- 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.
- 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
- 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
- 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.
- 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
- 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
- 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
- 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), Semin. Congr., 21, Soc. Math. France, Paris, 2010, 187–203
- S. Ballet, J. Pieltant, “On the tensor rank of multiplication in any extension of $mathbb{F}_2$”, J. Complexity, 27:2 (2011), 230–245
- 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
- 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
- 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
- S. Ballet, R. Rolland, “Multiplication algorithm in a finite field and tensor rank of the multiplication”, J. Algebra, 272:1 (2004), 173–185
- S. Ballet, R. Rolland, “On the bilinear complexity of the multiplication in finite fields”, Arithmetic, geometry and coding theory, AGCT 2003 (Luminy, 2003), Semin. Congr., 11, Soc. Math. France, Paris, 2005, 179–188
- S. Ballet, R. Rolland, “Families of curves over any finite field attaining the generalized Drinfeld–Vladut bound”, Publ. Math. Besançon Algèbre Theorie Nr., 2011 (2011), 5–18
- 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
- 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
- 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
- R. W. Brockett, D. Dobkin, “On the optimal evaluation of a set of bilinear forms”, Linear Algebra Appl., 19:3 (1978), 207–235
- M. R. Brown, D. P. Dobkin, “An improved lower bound on polynomial multiplication”, IEEE Trans. Comput., C-29:5 (1980), 337–340
- N. Bshouty, “Testers and their applications”, Electronic Colloquium on Computational Complexity (ECCC), 2012, TR12-011, 108 pp., par
- N. Bshouty, “Multilinear complexity is equivalent to optimal tester size”, Electronic Colloquium on Computational Complexity (ECCC), 2013, TR13-011, 39 pp.
- N. H. Bshouty, M. Kaminski, “Multiplication of polynomials over finite fields”, SIAM J. Comput., 19:3 (1990), 452–456
- P. Bürgisser, M. Clausen, M. A. Shokrollahi, Algebraic complexity theory, Grundlehren Math. Wiss., 315, Springer-Verlag, Berlin, 1997, xxiv+618 pp.
- 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
- 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
- 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
- M. Cenk, F. Özbudak, “On multiplication in finite fields”, J. Complexity, 26:2 (2010), 172–186
- M. Cenk, F. Özbudak, “Multiplication of polynomials modulo $x^n$”, Theoret. Comput. Sci., 412:29 (2011), 3451–3462
- J. Chaumine, Corps de fonctions algebriques et algorithme de D. V. et G. V. Chudnovsky pour la multiplication dans les corps finis, PhD thesis, Univ. de la Polynesie Française, 2005, 93 pp.
- J. Chaumine, “Complexite bilineaire de la multiplication dans des petits corps finis”, C. R. Math. Acad. Sci. Paris, 343:4 (2006), 265–266
- D. V. Chudnovsky, G. V. Chudnovsky, “Algebraic complexities and algebraic curves over finite fields”, J. Complexity, 4:4 (1988), 285–316
- 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
- J.-M. Couveignes, R. Lercier, “Elliptic periods for finite fields”, Finite Fields Appl., 15:1 (2009), 1–22
- 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
- F. Diamond, J. Shurman, A first course in modular forms, Grad. Texts in Math., 288, Springer-Verlag, New York, 2005, xvi+436 pp.
- 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.
- A. W. Dudek, “An explicit result for primes between cubes”, Funct. Approx. Comment. Math., 55:2 (2016), 177–197
- 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
- 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
- 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
- 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
- N. Estibals, Algorithmes et arithmetique pour l'implementation de couplages cryptographiques, PhD thesis, Univ. de Lorraine, Nancy, 2013, 219 pp.
- C. M. Fiduccia, Y. Zalcstein, “Algebras having linear multiplicative complexities”, J. Assoc. Comput. Mach., 24:2 (1977), 311–331
- S. Gao, J. von zur Gathen, D. Panario, V. Shoup, “Algorithms for exponentiation in finite fields”, J. Symb. Comput., 29:6 (2000), 879–889
- 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
- A. Garcia, H. Stichtenoth, H.-G. Rück, “On tame towers over finite fields”, J. Reine Angew. Math., 2003:557 (2003), 53–80
- В. Д. Гоппа, “Коды на алгебраических кривых”, Докл. АН СССР, 259:6 (1981), 1289–1290
- В. Д. Гоппа, “Алгебраико-геометрические коды”, Изв. АН СССР. Сер. матем., 46:4 (1982), 762–781
- E. Hallouin, “Computation of a cover of Shimura curves using a Hurwitz space”, J. Algebra, 321:2 (2009), 558–566
- T. Hasegawa, An explicit Shimura tower of function fields over a number field: an application of Takeuchi's list, 2017, 8 pp.
- 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
- A. Lempel, G. Seroussi, S. Winograd, “On the complexity of multiplication in finite fields”, Theoret. Comput. Sci., 22:3 (1983), 285–296
- C. Levrat, Tours de courbes de Shimura, Master's thesis, Univ. Paris-Saclay, Univ. de Versailles Saint-Quentin, Paris, 2018, 37 pp., par
- Д. Мамфорд, Абелевы многообразия, Мир, М., 1971, 299 с.
- 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
- J. Pieltant, Tours de corps de fonctions algebriques et rang de tenseur de la multiplication dans les corps finis, PhD thesis, Univ. d'Aix-Marseille, Inst. Math. de Luminy, 2012, 96 pp.
- 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
- 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
- M. Rambaud, Shimura curves and bilinear multiplication algorithms in finite fields, PhD thesis, Telecom ParisTech, 2017
- 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
- H. Randriam, Diviseurs de la forme 2D-G sans sections et rang de la multiplication dans les corps finis, 2011, 35 pp.
- H. Randriambololona, “Bilinear complexity of algebras and the Chudnovsky–Chudnovsky interpolation method”, J. Complexity, 28:4 (2012), 489–517
- H. Randriambololona, “$(2,1)$-separating systems beyond the probabilistic bound”, Israel J. Math., 195:1 (2013), 171–186
- 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
- H. Randriam, “Gaps between prime numbers and tensor rank of multiplication in finite fields”, Des. Codes Cryptogr., 87:2–3 (2019), 627–645
- G. Seroussi, A. Lempel, “On symmetric algorithms for bilinear forms over finite fields”, J. Algorithms, 5:3 (1984), 327–344
- M. A. Shokrollahi, “Optimal algorithms for multiplication in certain finite fields using elliptic curves”, SIAM J. Comput., 21:6 (1992), 1193–1198
- 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
- J. Sijsling, “Canonical models of arithmetic $(1;e)$-curves”, Math. Z., 273:1-2 (2013), 173–210
- А. Л. Тоом, “О сложности схемы из функциональных элементов, реализующей умножение целых чисел”, Докл. АН СССР, 150:3 (1963), 496–498
- М. А. Цфасман, “Коды Гоппы, лежащие выше границы Варшамова–Гилберта”, Пробл. передачи информ., 18:3 (1982), 3–6
- 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
- M. A. Tsfasman, S. G. Vlăduţ, Algebraic-geometric codes, Math. Appl. (Soviet Ser.), 58, Kluwer Acad. Publ., Dordrecht, 1991, xxiv+667 pp.
- 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
- M. Tukumuli, Etude 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.
- J. Voight, Three lectures on Shimura curves, 2006, 15 pp., par
- J. Voight, “Shimura curves of genus at most two”, Math. Comp., 78:266 (2009), 1155–1172
- S. Winograd, “Some bilinear forms whose multiplicative complexity depends on the field of constants”, Math. Systems Theory, 10:2 (1976/77), 169–180
- S. Winograd, “On multiplication in algebraic extension fields”, Theoret. Comput. Sci., 8:3 (1979), 359–377
- Chaoping Xing, “Asymptotic bounds on frameproof codes”, IEEE Trans. Inform. Theory, 48:11 (2002), 2991–2995
Arquivos suplementares
