[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Optimal selection for good polynomials of degree up to five

Published: 01 June 2022 Publication History

Abstract

An (r,)-good polynomial is a polynomial of degree r+1 that is constant on subsets of Fq, each of size r+1. For any positive integer r4 we provide an (r,)-good polynomial such that =Crq+O(q), with Cr maximal. This directly provides an explicit estimate (up to an error term of O(q), with explict constant) for the maximal length and dimension of a Tamo–Barg LRC. Moreover, we explain how to construct good polynomials achieving these bounds. Finally, we provide computational examples to show how close our estimates are to the actual values of , and we explain how to obtain the best possible good polynomials in degree 5. Our results complete the study by Chen et al. (Des Codes Cryptogr 89(7):1639–1660, 2021), providing (r,)-good polynomials of degree up to 5, with maximal (up to an error term of q), and our methods are independent.

References

[1]
Bartoli D and Calderini M On construction and (non) existence of c-(almost) perfect nonlinear functions Finite Fields Appl. 2021 72 101835
[2]
Bartoli D., Micheli G.: Algebraic constructions of complete m-arcs. arXiv:2007.00911 (2020).
[3]
Bartoli D., Micheli G., Zini G., Zullo F.: r-Fat linearized polynomials over finite fields. arXiv:2012.15357 (2020).
[4]
Bartoli D, Montanucci M, and Quoos L Locally recoverable codes from automorphism group of function fields of genus g1 IEEE Trans. Inf. Theory 2020 66 11 6799-6808
[5]
Bartoli D., Zini G., Zullo F.: Investigating the exceptionality of scattered polynomials. arXiv:2103.04591 (2021).
[6]
Berlekamp ER An analog to the discriminant over fields of characteristic two J. Algebra 1976 38 2 315-317
[7]
Chen R, Mesnager S, and Zhao CA Good polynomials for optimal LRC of low locality Des. Codes Cryptogr. 2021 89 7 1639-1660
[8]
Cohen S.D., Matthews R.W.: Monodromy groups of classical families over finite fields. In: Finite Fields and Applications (Glasgow, 1995), volume 233 of London Math. Soc. Lecture Note Ser., pp. 59–68. Cambridge Univ. Press, Cambridge (1996).
[9]
Ferraguti A and Micheli G Full classification of permutation rational functions and complete rational functions of degree three over finite fields Des. Codes Cryptogr. 2020 88 5 867-886
[10]
Ferraguti A and Micheli G Exceptional scatteredness in prime degree J. Algebra 2021 565 691-701
[11]
Ferraguti A., Pagano C., Casazza D.: The inverse problem for arboreal Galois representations of index two. arXiv:1907.08608 (2019).
[12]
Gallagher P.X.: The large sieve and probabilistic Galois theory. In: Analytic Number Theory (Proc. Sympos. Pure Math., vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972), pp. 91–101 (1973).
[13]
Gopalan P, Huang C, Simitci H, and Yekhanin S On the locality of codeword symbols IEEE Trans. Inf. Theory 2012 58 11 6925-6934
[14]
Liu J, Mesnager S, and Chen L New constructions of optimal locally recoverable codes via good polynomials IEEE Trans. Inf. Theory 2017 64 2 889-899
[15]
Liu J, Mesnager S, and Tang D Constructions of optimal locally recoverable codes via Dickson polynomials Des. Codes Cryptogr. 2020 88 9 1759-1780
[16]
Micheli G On the selection of polynomials for the DLP quasi-polynomial time algorithm for finite fields of small characteristic SIAM J. Appl. Algebra Geom. 2019 3 2 256-265
[17]
Micheli G Constructions of locally recoverable codes which are optimal IEEE Trans. Inf. Theory 2020 66 1 167-175
[18]
Papailiopoulos DS and Dimakis AG Locally repairable codes IEEE Trans. Inf. Theory 2014 60 10 5843-5855
[19]
Tamo I and Barg A A family of optimal locally recoverable codes IEEE Trans. Inf. Theory 2014 60 8 4661-4676
[20]
Turnwald G.: Some notes on monodromy groups of polynomials. In: Number Theory in Progress, vol. 1 (Zakopane-Kościelisko, 1997), pp. 539–552. de Gruyter, Berlin (1999).

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Designs, Codes and Cryptography
Designs, Codes and Cryptography  Volume 90, Issue 6
Jun 2022
210 pages

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 June 2022
Accepted: 12 April 2022
Revision received: 19 January 2022
Received: 27 July 2021

Author Tags

  1. Good polynomials
  2. Monodromy groups
  3. Global function fields

Author Tag

  1. 11T06

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Dec 2024

Other Metrics

Citations

Cited By

View all

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media