The complexity of the Berlekamp-Hensel algorithm for factoring polynomials in one or more variables with integer coefficients can become exponential in the individual variable degrees of the input polynomial due 10 the fact that, after factoring the projected polynomial and lifting its factors to sufficiently large coefficients, one may need 10 combine exponentially many lifted factors to obtain the true integer factors. In the univariate case, where the projection is taking the coefficients modulo a prime number, we can find worst case polynomials by prescribing that their Galois groups consist only of permutations with short cycles. Using the Chebotarev density theorem we then are able 10 construct succinct certificates for our hard-to-factor polynomials. In the multivariate case the projection is evaluation of selected variables at integral points. By computing the minimal polynomial of the approximation for a root we are able 10 replace the factor combination process by solving a system of linear equations. The growth analysis for the size of the rational numbers involved shows that, provided the number of variables is fixed, our algorithm reduces the problem in polynomial time in the total degree and coefficient length to the problem of factoring univariate polynomials, which has recently been solved in polynomial lime as well. Therefore our algorithm can factor multivariate polynomials with a fixed number of variables in polynomial time in the total degrees and coefficient lengths, except for splitting a possible constant factor into its prime divisors. The evaluation process also leads us to the study of the Hilbert irreducibilily theorem, an effective version of which provides us with an alternate polynomial time reduction from multivariate to bivariate polynomial factorization and irreducibilily testing.