Portal de Periódicos da CAPES

Factorization of multivariate polynomials over finite fields

1985; American Mathematical Society; Volume: 45; Issue: 171 Linguagem: Inglês

10.1090/s0025-5718-1985-0790658-x

1088-6842

Joachim von zur Gathen, Erich Kaltofen,

Cryptography and Residue Arithmetic

We present a probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in time polynomial in the input size, i.e., in the degree of the polynomial and log (cardinality of field). The algorithm generalizes to multivariate polynomials and has polynomial running time for densely encoded inputs. A deterministic version of the algorithm is also discussed, whose running time is polynomial in the degree of the input polynomial and the size of the field.