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.
|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|
* 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.