A Maple Program to Factor Multivariate Polynomials Given by Black Boxes

Let a be a polynomial in Z[ x 1 , x 2 , …,x n ]. Let α ∈ Z n and p be a large prime. Let B be a modular black box representation for a , that is, B : Z n × { p } → Z p such that B( α,p ) outputs a ( α ) mod p. In our implementation B is a Maple procedure. We present a Maple program CMBBSHL which on input of B outputs the irreducible factorization Π r i =1 f e i i of a ( x 1 ,…, x n ) with high probability. Our program is a combination of Maple codes and C codes where the main programs are implemented in Maple and several subroutines are implemented in C for increased efficiency. We present (1) a description of the algorithm, (2) a demonstration of the software, (3) a timing benchmark, and (4) some implementation details.