Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Start single access now
Access for companies
12th International Engine Congress 2025 | 25. + 26. February 2025

Meeting Place for the Powertrain and Sustainable Fuels Community

The congress will examine the future role of the internal combustion engine and its non-fossil fuels from a global perspective with leading experts. Be part of it! More information and booking options are available on our website.
EXTENDED SEARCH
Log in
Top
Published in:
Read chapter Read first chapter

2024 | OriginalPaper | Chapter

A New Absolute Irreducibility Criterion for Multivariate Polynomials over Finite Fields

Authors : Carlos Agrinsoni, Heeralal Janwa, Moises Delgado

Published in: Combinatorics, Graph Theory and Computing

Publisher: Springer Nature Switzerland

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

One of the key problems in algebraic geometry and its applications in coding theory, cryptography, and other disciplines is to determine whether a variety defined by a set of polynomials is absolutely irreducible; i.e., it remains irreducible in the algebraic closure of the defining field. The famous Eisenstein criterion for irreducibility works only over the defining fields. One important place where this is needed is when one applies the Riemann-Roch theorem. Another important application is in bounding the number of rational points or exponential sums through the Weil conjectures. In this chapter, we consider the hypersurfaces defined by generalized trinomials. We present a new absolute irreducibility criterion for generalized trinomials over finite fields. Our criterion does not require testing for irreducibility in the ground field or in any extension field. We just require multivariate GCD computations and the square-free property. Since almost all polynomials are known to be square-free, our absolute irreducibility criterion proves the absolute irreducibility of almost all generalized trinomials.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Group Divisible Designs with Three Groups and Block Size 4
next chapter On Combinatorial Interpretations of Some Elements of the Riordan Group
Literature
1.
L. M. Adleman. The function field sieve. In Algorithmic number theory (Ithaca, NY, 1994), volume 877 of Lecture Notes in Comput. Sci., pages 108–121. Springer, Berlin, 1994.
2.
C. Agrinsoni, H. Janwa, and M. Delgado. New absolute irreducibility testing criteria and factorization of multivariate polynomials. In F. Hoffman, S. Holliday, Z. Rosen, F. Shahrokhi, and J. Wierman (eds.) Combinatorics, graph theory and computing, pages 403–412. Springer International Publishing, Cham, 2024.
3.
Y. Aubry, G. McGuire, and F. Rodier. A few more functions that are not APN infinitely often. In Finite fields: theory and applications, volume 518 of Contemp. Math., pages 23–31. Amer. Math. Soc., Providence, RI, 2010.
4.
Y. Aubry and M. Perret. A Weil theorem for singular curves. In Arithmetic, geometry and coding theory (Luminy, 1993), pages 1–7. de Gruyter, Berlin, 1996.
5.
D. Bartoli and M. Montanucci. Towards the full classification of exceptional scattered polynomials. arXiv preprint arXiv:1905.11390, 2019.
6.
D. Bartoli and K.-U. Schmidt. Low-degree planar polynomials over finite fields of characteristic two. Journal of Algebra, 535:541–555, 2019.MathSciNetCrossRef
7.
P. Beelen and R. Pellikaan. The newton polygon of plane curves with many rational points. Designs, Codes and Cryptography, 21(1/3):41–67, 2000.MathSciNetCrossRef
8.
9.
10.
J. W. S. Cassels. Local fields, volume 3 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1986.CrossRef
11.
P. Deligne. La conjecture de Weil. i. Publications Mathématiques de l’Institut des Hautes Études Scientifiques, 43(1):273–307, 1974.
12.
G. Dumas. Sur quelques cas d’irréductibilité des polynômes à coefficients rationnels. Journal de Mathématiques Pures et Appliquées, 2:191–258, 1906.
13.
G. Eisenstein. Über die Irreductibilität und einige andere Eigenschaften der Gleichung, von welcher die Theilung der ganzen Lemniscate abhängt. J. Reine Angew. Math., 39:160–179, 1850.MathSciNet
14.
15.
S. Gao. Factoring multivariate polynomials via partial differential equations. Math. Comp., 72(242):801–822, 2003.MathSciNetCrossRef
16.
S. Gao and A. Lauder. Hensel lifting and bivariate polynomial factorisation over finite fields. Mathematics of Computation, 71(240):1663–1676, 2002.MathSciNetCrossRef
17.
J. Heintz and M. Sieveking. Absolute primality of polynomials is decidable in random polynomial time in the number of variables. In Automata, languages and programming (Akko, 1981), volume 115 of Lecture Notes in Comput. Sci., pages 16–28. Springer, Berlin-New York, 1981.
18.
F. Hernando and G. McGuire. Proof of a conjecture on the sequence of exceptional numbers, classifying cyclic codes and APN functions. J. Algebra, 343:78–92, 2011.MathSciNetCrossRef
19.
F. Hernando and G. McGuire. Proof of a conjecture of Segre and Bartocci on monomial hyperovals in projective planes. Des. Codes Cryptogr., 65(3):275–289, 2012.MathSciNetCrossRef
20.
J. W. P. Hirschfeld. Projective geometries over finite fields. The Clarendon Press, Oxford University Press, New York, 1979. Oxford Mathematical Monographs.
21.
T. Høholdt, J. H. Van Lint, and R. Pellikaan. Algebraic geometry codes. Handbook of coding theory, 1(Part 1):871–961, 1998.
22.
J. Hu and M. Monagan. A fast parallel sparse polynomial gcd algorithm. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, pages 271–278, 2016.
23.
H. Janwa, G. M. McGuire, and R. M. Wilson. Double-error-correcting cyclic codes and absolutely irreducible polynomials over \(\mathrm {GF}(2)\). J. Algebra, 178(2):665–676, 1995.
24.
H. Janwa and R. M. Wilson. Hyperplane sections of Fermat varieties in \({\mathbf {P}}^3\) in \(\mathrm {char}.\,2\) and some applications to cyclic codes. In Applied algebra, algebraic algorithms and error-correcting codes (San Juan, PR, 1993), volume 673 of Lecture Notes in Comput. Sci., pages 180–194. Springer, Berlin, 1993.
25.
D. Jedlicka. APN monomials over \(\mathrm {GF}(2^n)\) for infinitely many n. Finite Fields Appl., 13(4):1006–1028, 2007.
26.
E. Kaltofen. A polynomial reduction from multivariate to bivariate integral polynomial factorization. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 261–266, 1982.
27.
E. Kaltofen. A polynomial-time reduction from bivariate to univariate integral polynomial factorization. In 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982), pages 57–64. IEEE, New York, 1982.
28.
29.
E. Kaltofen. Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. SIAM J. Comput., 14(2):469–489, 1985.MathSciNetCrossRef
30.
S. K. Khanduja and J. Saha. On a generalization of Eisenstein’s irreducibility criterion. Mathematika, 44(1):37–41, 1997.MathSciNetCrossRef
31.
S. Kopparty and S. Yekhanin. Detecting rational points on hypersurfaces over finite fields. In Twenty-Third Annual IEEE Conference on Computational Complexity, pages 311–320. IEEE Computer Soc., Los Alamitos, CA, 2008.
32.
A. K. Lenstra. Factoring multivariate polynomials over finite fields. J. Comput. System Sci., 30(2):235–248, 1985.MathSciNetCrossRef
33.
A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261(4):515–534, 1982.MathSciNetCrossRef
34.
R. Lidl and H. Niederreiter. Finite fields, volume 20 of Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn.
35.
S. MacLane. The Schönemann-Eisenstein irreducibility criteria in terms of prime ideals. Trans. Amer. Math. Soc., 43(2):226–239, 1938.MathSciNet
36.
T. Sasaki and M. Suzuki. Three new algorithms for multivariate polynomial gcd. Journal of symbolic computation, 13(4):395–411, 1992.MathSciNetCrossRef
37.
W. Schmidt. Equations over finite fields: an elementary approach. Kendrick Press, Heber City, UT, second edition, 2004.
38.
S. A. Stepanov. Congruences with two unknowns. Izv. Akad. Nauk SSSR Ser. Mat., 36:683–711, 1972.MathSciNet
39.
S. A. Stepanov. Rational points of algebraic curves over finite fields. In Current problems of analytic number theory (Proc. Summer School, Minsk, 1972) (Russian), pages 223–243, 272, 1974.
40.
H. Stichtenoth. Algebraic function fields and codes. Universitext. Springer-Verlag, Berlin, 1993.
41.
T. Szőnyi. Some applications of algebraic curves in finite geometry and combinatorics. In Surveys in combinatorics, 1997 (London), volume 241 of London Math. Soc. Lecture Note Ser., pages 197–236. Cambridge Univ. Press, Cambridge, 1997.
42.
J. von zur Gathen. Irreducibility of multivariate polynomials. J. Comput. System Sci., 31(2):225–264, 1985. Special issue: Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983).
43.
J. Von Zur Gathen and J. Gerhard. Modern computer algebra. Cambridge university press, 2013.CrossRef
44.
D. Q. Wan. Minimal polynomials and distinctness of Kloosterman sums. Finite Fields Appl., 1(2):189–203, 1995. Special issue dedicated to Leonard Carlitz.
45.
Metadata
Title
A New Absolute Irreducibility Criterion for Multivariate Polynomials over Finite Fields
Authors
Carlos Agrinsoni
Heeralal Janwa
Moises Delgado
Copyright Year
2024
Book
Combinatorics, Graph Theory and Computing

Print ISBN: 978-3-031-62165-9

Electronic ISBN: 978-3-031-62166-6

Copyright Year: 2024

DOI
https://doi.org/10.1007/978-3-031-62166-6_5

Premium Partner

    Image Credits