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.

Polynomial MAGMA time MAGMA H-Bnd NTL time NTL H-Bnd FLINT time FLINT H-Bnd
P1 0.03* 29^307 0.248 29^311 0.136 89^33
P2 0.08* 11^426 .376 11^437 .144 11^(22/44)
P3 .210* 11^597 1.036 11^629 .320 11^31
P4 2.040 7^984 1.956 13^745 1.452 7^(80/160)
P5 .01* 7^77 .088 19^51 .036 23^26
P6 .150* 19^107 .276 19^152 .160 23^(38/76)
P7 1.1* 23^68 1.136 37^78 .900 19^74
P8 2.230* 11^350 3.428 13^324 1.700 11^84
M12_5 10.439 11^1264 12.429 13^1171 4.156 11^180
M12_6 23.329 13^1555 21.697 13^1555 7.780 13^(190/380)
S7 .420* 29^78 .340 29^78 .336 47^41
S8 4.629* 47^140 3.752 47^140 8.437 53^79
T1 5.509 7^484 3.848 7^495 1.180 7^40
T2 4.399 7^312 3.18 7^200 1.216 7^43