Parallel univariate polynomial factorization on shared-memory multiprocessors

Abstract

Using parallelism afforded by shared-memory multiprocessors to speed up systems for polynomial factorization is discussed. The approach is to take the fastest known factoring algorithm for practical purposes and parallelize key parts of it. The univariate factoring algorithm consists of two major tasks (a) factoring modulo small integer primes and (b) EEZ lifting and recovery of true factors. A C coded system PFACTOR that implements (a) in parallel is described in detail. PFACTOR is a stand-alone parallel factorizer that can take input from a file, a pipe or a socket connection over a network. It can also be used interactively as a UNIX command. PFACTOR consists of parallel selection of primes, automatic balancing of work, parallel Berlekamp algorithm, and parallel reconciliation of degrees of factors modulo different primes. Actual timings on the Encore Multimax show the effectiveness of the approach. Work on part (b) is still on going.