BLACK-BOX POLYNOMIAL RESULTANTS

A black-box polynomial is a multivariate polynomial that is represente d by a program that evaluates the polynomial at an arbitrary point sup plied as input. The paper describes an algorithm for constructing a bl ack box for the resultant of two black-box polynomials. The only compu tationally nontrivial step in the construction is that which determine s the degrees of the input black boxes in the variable being eliminate d; if those degrees are known, then the black-box resultant can be con structed in a bounded amount of time. Let N be an upper bound for the degrees of the input polynomials. The black-box resultant can be evalu ated at an arbitrary point with O(N) calls to the input black boxes an d O(N-2) arithmetic operations. (C) 1997 Elsevier Science B.V.