I've written a <a href=knapsack/version2.tar.gz> newer version
of the implementation</a>
(for Maple 6) which is more complete and also faster than
the <a href=knapsack/impl.tar.gz> previous version</a>, at least on most,  
but not all, large examples. See
<a href=knapsack/timings> timings</a> and
more <a href=knapsack/polys>test examples</a>).
The <a href=knapsack/knapsack>source code</a>
is now available as well.
There is now also a <a href=knapsack/version2_V5.tar.gz>version for Maple
5</a>.
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): </p>

libname := `/home/m17/hoeij/maple/lib` , libname: </p>

to your Maple startup file which is
called .mapleinit under Unix. This startup file should be
placed in your homedirectory. </p>

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. </p>

To use the code just type factor(f) in Maple. To see if the
code is there type the following two commands in Maple </p>
 
interface(verboseproc=2): 
op(`factor/knapsack`); </p>

If you succesfully installed the code you should be able to
see the algorithm this way. Type the command: </p>
infolevel[factor]:=10; </p>
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: </p>


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);

</p>
Factoring this one should now be a piece of cake (30 to 40 seconds on a
P266).
</p>
<a href=knapsack/paper/knapsack.ps> Download this
paper</a>. A previous version of this paper is also still
available: <a href=knapsack/old/1.ps>preprint FSU00-13</a>.
</p>
<hr>
<b>More recent news:</b></p>
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 <a href=knapsack/knapsack>implementation</a> 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
<a href=http://mahery.math.u-psud.fr/~belabas/>Karim Belabas</a> 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.