Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators (Q923629)

This paper gives algorithms to factorize multivariate polynomials and compute GCD's of them, where each polynomial is given as a black box, i.e. a procedure that computes a value when input is presented. The results of the computations are similar black boxes that rely on the black boxes of the original polynomials. The algorithms are all in random polynomial time.