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:


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.

More recent news:

In the implementation there is some fine tuning to be done (how many traces to use at a time, and with how many p-adic digits at a time, etc.). My implementation is not tuned in the best possible way. A much better way (more efficient, more robust and simpler) to tune the algorithm is given by Karim Belabas in section 2 of his paper "A relative van Hoeij algorithm over number fields", to appear in J. Symbolic Computation. So if you want to implement the algorithm, the best way to get a well tuned implementation is to read Karim's paper.