Portal de Periódicos da CAPES

Factoring sparse multivariate polynomials

1985; Elsevier BV; Volume: 31; Issue: 2 Linguagem: Inglês

10.1016/0022-0000(85)90044-3

1090-2724

Joachim von zur Gathen, Erich Kaltofen,

Cryptography and Residue Arithmetic

This paper presents a probabilistic reduction for factoring polynomials from multivariate to the bivariate case, over an arbitrary (effectively computable) field. It uses an expected number of field operations (and certain random choices) that is polynomial in the size of sparse representations of input plus output, provided the number of irreducible factors is bounded. We thus obtain probabilistic polynomial-time factoring procedures over algebraic number fields and over finite fields. The reduction is based on an effective version of Hilbert's irreducibility theorem.