The average number of modular factors in Trager’s polynomial factorization algorithm

Trager’s algorithm for factoring a univariate polynomial over an algebraic number field computes the norm of the polynomial and then factors the norm over the integers. It has been observed by the author as well as others that the norm tends to factor modulo a prime into more irreducible factors than one would expect from a typical random polynomial, but no explanation has previously been given. In this paper, an exact formula is derived for the average number of irreducible
factors of the norm modulo a prime. For large primes, the asymptotic average is larger than the corresponding average for random polynomials with integer coefficients.