Factorization of Multivariate Polynomials with Coefficients in Fp

✍ Scribed by Guy Viry

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 548 KB
• Volume: 15
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1993.1027

✦ Synopsis

The ring of polynomials in (X, X_{1}, \ldots, X_{m}) are denoted by (\mathbf{F}{p}\left[X, X{1}, \ldots, X_{m}\right]) in (F_{p}), that is the field of integers defined modulo (p). In the usual factorization algorithm defined by Wang, the given polynomial (P) is first factorized modulo (\Delta^{n}), where (\Delta^{n}) is an ideal. This algorithm uses a generalization of Hensel's Lemma. If there are no extraneous factors, then the factors defined modulo (\Delta^{n}) correspond to the factors of (P) in (\mathbf{F}{p}\left[X, X{1}, \ldots, X_{m}\right]), or else the defined factors must be regrouped to find the factors of (P) in (\mathbf{F}{p}\left[X, X{1}, \ldots, X_{m}\right]). In this paper, a mapping that transforms the product of the factors into a sum is defined. A theorem that determines whether a subproduct of the factors of (P) corresponds to a factor of (P) in (F_{p}\left[X, X_{1}, \ldots, X_{m}\right}) is given. Therefore the regrouping of the factors of (P) reduces to solving a system of linear equations, as in the univariate case, with Berlekamp's algorithm.