FAST16

FAST16: A software program for factorizing polynomials over large GF(p) [For the entire collection see Zbl 0642.00029.] par The authors consider the problem of factorizing square-free polynomials over large, finite, prime fields. They give a categorization of the methods used until now for this problem. These ideas are used and the authors present a new algorithm. They compare the performance of this algorithm with that of Macsyma. The result is that their algorithm is faster. par Let $fin {bfF}sb p[X]$ be a square-free polynomial. The algorithm first searches for a factorization of the f into a product $fsb{(r)}g$, such that $fsb{(r)}$ consists of all irreducible factors of f whose degrees divide a certain integer r. This is done by taking the greatest common divisor of f and $xsp{pquad j}-x$ for certain j. In the second step the authors try to find a factorization of $fsb{(r)}$ into products of polynomials, such that each of them is a product of irreducible polynomials of the same degree. Finally these parts are factorized, using some norm function. par The presented algorithm is probabilistic in the sense that several tries have to be made in each step. The authors provide average numbers of how often such tries have to be made.