Computing with polynomials given byblack boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators

摘要: Algorithms are developed that adopt a novel implicit representation for multivariate polynomials and rational functions with coefficients, of black boxes their evaluation. We show within this the polynomial greatest common divisor factorization problems, as well problem extracting numerator denominator function, can all be solved in random polynomial-time. Since we convert efficiently to sparse format, problems solutions, e.g., function interpolation, also time. Moreover, box is one most space efficient representations know. Therefore, output programs easily distributed over network processors further manipulation, such interpolation.