I've written a newer version of the implementation (for Maple 6) which is more complete and also faster than the previous version, at least on most, but not all, large examples. See timings and more test examples). The source code is now available as well. There is now also a version for Maple 5. To install, place the two files maple.ind and maple.lib in the directory maple/lib under your home directory, and add the following line (edit the pathname):libname := `/home/m17/hoeij/maple/lib` , libname: to your Maple startup file which is called .mapleinit under Unix. This startup file should be placed in your homedirectory. It would be very helpful for the development of this software if you could e-mail me any bugs, examples where the code performs poorly, or other problems you may find. To use the code just type factor(f) in Maple. To see if the code is there type the following two commands in Maple interface(verboseproc=2): op(`factor/knapsack`); If you succesfully installed the code you should be able to see the algorithm this way. Type the command: infolevel[factor]:=10; to see when `factor/knapsack` gets called and how much time the lattice reductions take. As a quick test to see if it works issue the following Maple commands: a:=sqrt(2)+sqrt(3)+sqrt(5)+sqrt(7)+sqrt(11); b:=sqrt(2)+sqrt(3)+sqrt(5)+sqrt(7)+sqrt(13); f1:=evala(Norm(convert(x-a,RootOf))); f2:=evala(Norm(convert(x-b,RootOf))); f:=expand(f1*f2); factor(f); Factoring this one should now be a piece of cake (30 to 40 seconds on a P266). Download this paper. A previous version of this paper is also still available: preprint FSU00-13.