Multi-Modular Approach to Polynomial-Time Factorization of Bivariate Integral Polynomials

Efficient algorithms to factorize bivariate integral polynomials are discussed. As a key technique to provide the most efficient algorithms in theory, an approach, named multimodular approach, is proposed and its implication is discussed intensively. The approach uses combined information from several modular factorizations of different types. Although essentially the same idea was already proposed by Chistov&Grigoryev in 1982, the concept is presented independently in detail but in a more intelligible form. Effectiveness of the multi-modular approach is proved by affording two new algorithms superior to any other existing algorithms.