A note on Gröbner bases and Berlekamp's algorithm (Q2474859)

The factorization of polynomials over finite fields plays an important role in many topics of mathematics: cryptography, number theory and coding theory. The paper under review deals with the factorization of square-free polynomials in one variable over finite fields by using Gröbner bases. In general, factorization methods existing in present time can be classified in two parts perfectly distinguished: deterministic techniques [for instance see \textit{E. Berlekamp}, Bell Syst. Tech. J. 46, 1853--1859 (1967; Zbl 0166.04901) and \textit{H. Niederreiter}, Math. Comput. 62, 819--830 (1994; Zbl 0797.11092)] and probabilistic techniques [see for example \textit{E. Kaltofen} and \textit{V. Shoup}, Math. Compt. 67, No. 223, 1179--1197 (1998; Zbl 0902.11053)]. The interest of this article is centered on Berlekamp's algorithm. This algorithm provides the factorization of a square-free polynomial. The use of Gröbner bases to factorize polynomials is not the first. Indeed, for bivariate polynomials, see \textit{M. Noro} and \textit{K. Yokoyama} [in: ISSAC 2002. Proc. 2002 inter. symp. on symbolic and algebraic computation, Lille, France, 2002, 200--206 (2002; Zbl 1072.68690)]. Here the aim is to use Gröbner bases to obtain the greatest common divisors needed to apply Berlekamp's algorithm. A \texttt{Maple} package which calculates the factorization of a square-free polynomial in one variable over a finite field using this kind of techniques is shown. Moreover, some interest examples are given.