// Magma code for generating the timings in Table 2

Z := IntegerRing();
P<x1,x2,x3,x4,x5,x6> := PolynomialRing(Z,6);

getmon := function(d)
   m := x1^Random(0,d)*x2^Random(0,d)*x3^Random(0,d)*
        x4^Random(0,d)*x5^Random(0,d)*x6^Random(0,d);
   return m;
end function;

randpoly := function(d,t,m)
   M := { getmon(d) : i in [1..t] };
   while #M lt t do M := M join { getmon(d) : i in [1..t-#M] }; end while;
   M := [ x : x in M ];
   C := [ Random(1,m) : i in [1..t] ];
   return Polynomial(C,M);
end function;

d := 7;
t := 500;
for d in [5,10,15,20,40,60,80] do
  f := x1^d + randpoly(d,t-1,1000);
  g := x1^d + randpoly(d,t-1,1000);
  time a := f*g;
  d; Length(a);
  time h := Factorization(a);
end for;