When I implemented polynomial factoring in 2016, the following were the times:
| Poly |
NTL |
Magma |
Flint-1.6 |
New |
| P1 |
0.07 |
0.03 |
0.10 |
0.30 |
| P2 |
0.2 |
0.08 |
0.10 |
0.50 |
| P3 |
0.3 |
0.16 |
0.16 |
0.93 |
| P4 |
2.0 |
1.9 |
0.94 |
4.6 |
| P5 |
0.09 |
0.11 |
0.04 |
0.03 |
| P6 |
0.12 |
0.11 |
0.11 |
0.26 |
| P7 |
1.1 |
1.1 |
0.52 |
1.8 |
| P8 |
3.4 |
2.2 |
1.5 |
0.79 |
| M12_5 |
12.4 |
9.5 |
2.9 |
2.2 |
| M12_6 |
21.7 |
21.5 |
5.2 |
73 |
| S7 |
0.34 |
0.42 |
0.20 |
0.56 |
| S8 |
3.8 |
4.6 |
2.1 |
7.9 |
| S9 |
71 |
165 |
21 |
---- |
| S10 |
?? |
?? |
?? |
---- |
| T1 |
3.8 |
2.5 |
1.2 |
0.6 |
| T2 |
3.2 |
2.1 |
1.2 |
0.6 |
| T3 |
24 |
20 |
7.4 |
59 |
| H1 |
?? |
?? |
?? |
9.3 |
| H2 |
?? |
?? |
?? |
---- |
I also gave a list of things that we don't do yet, some of which have been done since:
- tuning of parameters p^a, rho, delta, eta, l, E_bound, number of CLDs, etc a la van Hoeij-Novocin
- switch to Zassenhaus once number of local factors is low enough
- inflation/deflation (aka power hack)
- U_LLL floating point LLL trick
- spend more time searching for optimal prime p
- mix CLD data using random matrices
- only run LLL if justified as outlined in van Hoeij-Novocin
- only add row if justified as outlined in van Hoeij-Novocin
- speed up basic arithmetic in LLL
- fast divisibility testing, e.g. mod a small prime
- asymptotically fast truncated division smod p^a
When I implemented polynomial factoring in 2016, the following were the times:
I also gave a list of things that we don't do yet, some of which have been done since: