Factoring modular polynomials
type: Item
instance of: scholarly article
title: Factoring modular polynomials
zbMATH Open document ID: 0913.11050
author: Joachim von zur Gathen
author: Silke Hartlieb
published in: Journal of Symbolic Computation
publication date: 1999-03-11T00:00:00Z
review text: Let \(R\) be either \(Z\) or \(F_q [y]\), \(F_q\) the finite field containing \(q\) elements, and let \(r \in R\) be a non-zero non-unit. The aim of the work is to describe all possible factorizations into irreducibles of polynomials in \(R[x]\) over the ring \(R/(r)\) where \((r)\) is the ideal generated by \(r\). Factorization of polynomials into irreducible factors over such rings is not unique. For example: \[ x^2 \equiv (x- \alpha p)(x+ \alpha p)\bmod{p^2} \] for all \(\alpha \in \{ 0,1,\dots , p-1 \}\). An example due to Shamir shows that for certain rings, non-trivial factors of \(f\) can have the same degree as \(f\): e.g for \(r=pq\) for different (non-associate) primes, then \(p^2 +q^2\) is a unit in \(Z/(r)\) and \[ x \equiv (p^2 + q^2)^{-1} (px+q)(qx+p)\bmod{r}. \] It is first shown that the problem can be reduced, by use of the Chinese remainder theorem and a generalization of Hensel's lemma, to the case where \(r \in R\) is a prime power, or the power of an irreducible polynomial modulo the prime. The main result of the paper is then an algorithm for finding all irreducible factorizations if \(r = p^k\). The algorithm only works when the discriminant of the polynomial is not divisible by \(p^k\). In particular, the polynomial to be factored must be square-free. In this case the algorithm produces a description of all factorizations and is polynomial in time, even when there exist exponentially many irreducible factors. In the case when \(r\) divides the discriminant, the only known algorithm for factorization is by exhaustive search, in exponential time.
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 1236261
zbMATH Keywords: factorization of polynomials
zbMATH Keywords: finite fields
zbMATH Keywords: finite commutative rings
zbMATH Keywords: polynomial time algorithm
reviewed by: Ian Blake
MaRDI profile type: Publication
OpenAlex ID: W2024250625
DOI: 10.1006/JSCO.1998.0228
Recommended article: Factoring polynomials modulo special primes
Recommended article: Q4227317
Recommended article: Q3597328
Recommended article: 3256. Polynomials factorable (mod n)
Recommended article: Computing Modular Polynomials
Recommended article: Q3417148
Recommended article: Factoring polynomials over finite fields
Recommended article: Q4892927
Recommended article: Q3345783
description: scientific article; zbMATH DE number 1236261