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.

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