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

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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.

About the authors

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

References

  1. N. Arnaud, Evaluation derivee, multiplication dans les corps finis et codes correcteurs, PhD thesis, Univ. de la Mediterranee, 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
  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
  4. R. C. Baker, G. Harman, J. Pintz, “The difference between consecutive primes. II”, Proc. London Math. Soc. (3), 83:3 (2001), 532–562
  5. 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
  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
  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
  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
  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
  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
  11. S. Ballet, “On the tensor rank of the multiplication in the finite fields”, J. Number Theory, 128:6 (2008), 1795–1806
  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.
  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
  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
  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.
  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
  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
  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
  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), Semin. Congr., 21, Soc. Math. France, Paris, 2010, 187–203
  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
  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
  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
  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
  24. S. Ballet, R. Rolland, “Multiplication algorithm in a finite field and tensor rank of the multiplication”, J. Algebra, 272:1 (2004), 173–185
  25. 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
  26. 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
  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
  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
  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
  30. R. W. Brockett, D. Dobkin, “On the optimal evaluation of a set of bilinear forms”, Linear Algebra Appl., 19:3 (1978), 207–235
  31. M. R. Brown, D. P. Dobkin, “An improved lower bound on polynomial multiplication”, IEEE Trans. Comput., C-29:5 (1980), 337–340
  32. N. Bshouty, “Testers and their applications”, Electronic Colloquium on Computational Complexity (ECCC), 2012, TR12-011, 108 pp., par
  33. N. Bshouty, “Multilinear complexity is equivalent to optimal tester size”, Electronic Colloquium on Computational Complexity (ECCC), 2013, TR13-011, 39 pp.
  34. N. H. Bshouty, M. Kaminski, “Multiplication of polynomials over finite fields”, SIAM J. Comput., 19:3 (1990), 452–456
  35. P. Bürgisser, M. Clausen, M. A. Shokrollahi, Algebraic complexity theory, Grundlehren Math. Wiss., 315, Springer-Verlag, Berlin, 1997, xxiv+618 pp.
  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
  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
  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
  39. M. Cenk, F. Özbudak, “On multiplication in finite fields”, J. Complexity, 26:2 (2010), 172–186
  40. M. Cenk, F. Özbudak, “Multiplication of polynomials modulo $x^n$”, Theoret. Comput. Sci., 412:29 (2011), 3451–3462
  41. 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.
  42. J. Chaumine, “Complexite bilineaire de la multiplication dans des petits corps finis”, C. R. Math. Acad. Sci. Paris, 343:4 (2006), 265–266
  43. D. V. Chudnovsky, G. V. Chudnovsky, “Algebraic complexities and algebraic curves over finite fields”, J. Complexity, 4:4 (1988), 285–316
  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
  45. J.-M. Couveignes, R. Lercier, “Elliptic periods for finite fields”, Finite Fields Appl., 15:1 (2009), 1–22
  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
  47. F. Diamond, J. Shurman, A first course in modular forms, Grad. Texts in Math., 288, Springer-Verlag, New York, 2005, xvi+436 pp.
  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.
  49. A. W. Dudek, “An explicit result for primes between cubes”, Funct. Approx. Comment. Math., 55:2 (2016), 177–197
  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
  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
  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
  54. N. Estibals, Algorithmes et arithmetique pour l'implementation de couplages cryptographiques, PhD thesis, Univ. de Lorraine, Nancy, 2013, 219 pp.
  55. C. M. Fiduccia, Y. Zalcstein, “Algebras having linear multiplicative complexities”, J. Assoc. Comput. Mach., 24:2 (1977), 311–331
  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
  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
  58. A. Garcia, H. Stichtenoth, H.-G. Rück, “On tame towers over finite fields”, J. Reine Angew. Math., 2003:557 (2003), 53–80
  59. В. Д. Гоппа, “Коды на алгебраических кривых”, Докл. АН СССР, 259:6 (1981), 1289–1290
  60. В. Д. Гоппа, “Алгебраико-геометрические коды”, Изв. АН СССР. Сер. матем., 46:4 (1982), 762–781
  61. E. Hallouin, “Computation of a cover of Shimura curves using a Hurwitz space”, J. Algebra, 321:2 (2009), 558–566
  62. T. Hasegawa, An explicit Shimura tower of function fields over a number field: an application of Takeuchi's list, 2017, 8 pp.
  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
  64. A. Lempel, G. Seroussi, S. Winograd, “On the complexity of multiplication in finite fields”, Theoret. Comput. Sci., 22:3 (1983), 285–296
  65. C. Levrat, Tours de courbes de Shimura, Master's thesis, Univ. Paris-Saclay, Univ. de Versailles Saint-Quentin, Paris, 2018, 37 pp., par
  66. Д. Мамфорд, Абелевы многообразия, Мир, М., 1971, 299 с.
  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
  68. 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.
  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
  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
  71. M. Rambaud, Shimura curves and bilinear multiplication algorithms in finite fields, PhD thesis, Telecom 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
  73. H. Randriam, Diviseurs de la forme 2D-G sans sections et rang de la multiplication dans les corps finis, 2011, 35 pp.
  74. H. Randriambololona, “Bilinear complexity of algebras and the Chudnovsky–Chudnovsky interpolation method”, J. Complexity, 28:4 (2012), 489–517
  75. H. Randriambololona, “$(2,1)$-separating systems beyond the probabilistic bound”, Israel J. Math., 195:1 (2013), 171–186
  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
  77. H. Randriam, “Gaps between prime numbers and tensor rank of multiplication in finite fields”, Des. Codes Cryptogr., 87:2–3 (2019), 627–645
  78. G. Seroussi, A. Lempel, “On symmetric algorithms for bilinear forms over finite fields”, J. Algorithms, 5:3 (1984), 327–344
  79. M. A. Shokrollahi, “Optimal algorithms for multiplication in certain finite fields using elliptic curves”, SIAM J. Comput., 21:6 (1992), 1193–1198
  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
  81. J. Sijsling, “Canonical models of arithmetic $(1;e)$-curves”, Math. Z., 273:1-2 (2013), 173–210
  82. А. Л. Тоом, “О сложности схемы из функциональных элементов, реализующей умножение целых чисел”, Докл. АН СССР, 150:3 (1963), 496–498
  83. М. А. Цфасман, “Коды Гоппы, лежащие выше границы Варшамова–Гилберта”, Пробл. передачи информ., 18:3 (1982), 3–6
  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
  85. M. A. Tsfasman, S. G. Vlăduţ, Algebraic-geometric codes, Math. Appl. (Soviet Ser.), 58, Kluwer Acad. Publ., Dordrecht, 1991, xxiv+667 pp.
  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
  87. 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.
  88. J. Voight, Three lectures on Shimura curves, 2006, 15 pp., par
  89. J. Voight, “Shimura curves of genus at most two”, Math. Comp., 78:266 (2009), 1155–1172
  90. S. Winograd, “Some bilinear forms whose multiplicative complexity depends on the field of constants”, Math. Systems Theory, 10:2 (1976/77), 169–180
  91. S. Winograd, “On multiplication in algebraic extension fields”, Theoret. Comput. Sci., 8:3 (1979), 359–377
  92. Chaoping Xing, “Asymptotic bounds on frameproof codes”, IEEE Trans. Inform. Theory, 48:11 (2002), 2991–2995

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2021 Ballet S., Pieltant J., Rambaud M., Randriambololona H., Rolland R., Chaumine J.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».