We present here some timings of the new F_mpz_poly_factor procedure in FLINT. The implementation still lacks many standard tricks, however it is the first competitive algorithm to use CLDs over traces. This allows, in the typical case, earlier termination of the algorithm than other versions. We illustrate this by showing the amount of Hensel lifting used by MAGMA, NTL, and FLINT to solve each problem under the H-=Bnd columns.

When a MAGMA time has a * that indicates that MAGMA succesfully used a power hack trick which FLINT does not have at the moment (and we deactivated NTL's power hack), these times then had many instances of Hensel lifting on multiple polynomials and are typically much faster (and not quite comparable to the others). In the FLINT H-Bnd column there are some polynomials with a (number/number) in their exponent. These polynomial solved the combinatorial problem using only the first level of p-adic precision but needed one more round of Hensel lifting to recontruct one of the factors.

All of the polynomials but T1 and T2 were taken as benchmarks from NTL's website here. There you can find a brief description of each polynomial and its application. T1 and T2 were created as examples of polynomials which come from typical uses of Trager's algorithm for factoring in a number field. These polynomials represent the rather common case of polynomials whose CPU bottleneck is Hensel lifting. Where as S7 and S8 are Swinnerton-Dyer polynomials where the running times are dominated by calls to LLL.