// Magma code for generating the timings in Table 1

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] ];
   g := Polynomial(C,M);
   return g;
end function;

d := 7;
for t in [100,500,1000,2000,4000,8000] do
  f := x1^d + randpoly(d,t-1,1000);
  g := x1^d + randpoly(d,t-1,1000);
  time a := f*g;
  t; Length(a);
  time h := Factorization(a);
end for;