An LLL-based minimal polynomial algorithm is found in most computer algebra systems. We have received quite comparable results for the following three systems. For all three systems the tests were performed on an R4600 SGI workstation running at 132 MHz. Maple and Mathematica are leading commercial computer algebra products. PARI-GP can be obtained by anonymous ftp to megrez.math.u-bordeaux.fr.
software | precision | time | function |
system | needed | needed | used |
Maple 5.5 | 235(310)* | 27 min* | minpoly |
Mathematica 3.0 | 170 | 33.5 min | NumberTheory`Recognize` |
PARI-GP 1.39 | 175(265)* | 27.5 min* | lindep2 |
Comments:
*
The notation d1(d2) means that
the first correct result is received at the precision
of d1 decimal digits but a steady stream
of correct results (when incrementing the precision by 5 digits in one step)
only starts at d2 digits. In this case, the timing in the third
column is for the run at the precision of d1 digits.