nmod_mpoly_gcd performanc

[thofma]

This came up in Nemocas/Nemo.jl#2256.

Here is a gcd call for nmod_mpoly, which takes long (have not seen it finish), but it is instant in Magma and other systems:

julia> R, (l1, l2, l3, a1, a2, a3, b1, b2, b3, g1, g2, g3) = polynomial_ring(Nemo.Native.GF(2^31 - 1), ["l1", "l2", "l3", "a1", "a2", "a3", "b1", "b2", "b3", "g1", "g2", "g3"]);

julia> g = l1^2*a2^2*b1^2*g2^2*g3^2 + 2*l1^2*a2^2*b1*b2*g1*g2*g3^2 + 2*l1^2*a2^2*b1*b3*g1*g2^2*g3 + l1^2*a2^2*b2^2*g1^2*g3^2 + 2*l1^2*a2^2*b2*b3*g1^2*g2*g3 + l1^2*a2^2*b3^2*g1^2*g2^2 + 2147483645*l1^2*a2*a3*b1^2*g2^2*g3^2 + 2147483643*l1^2*a2*a3*b1*b2*g1*g2*g3^2 + 2147483643*l1^2*a2*a3*b1*b3*g1*g2^2*g3 + 2147483645*l1^2*a2*a3*b2^2*g1^2*g3^2 + 2147483643*l1^2*a2*a3*b2*b3*g1^2*g2*g3 + 2147483645*l1^2*a2*a3*b3^2*g1^2*g2^2 + l1^2*a3^2*b1^2*g2^2*g3^2 + 2*l1^2*a3^2*b1*b2*g1*g2*g3^2 + 2*l1^2*a3^2*b1*b3*g1*g2^2*g3 + l1^2*a3^2*b2^2*g1^2*g3^2 + 2*l1^2*a3^2*b2*b3*g1^2*g2*g3 + l1^2*a3^2*b3^2*g1^2*g2^2 + 2147483645*l1*l2*a1*a2*b1^2*g2^2*g3^2 + 2147483643*l1*l2*a1*a2*b1*b2*g1*g2*g3^2 + 2147483643*l1*l2*a1*a2*b1*b3*g1*g2^2*g3 + 2147483645*l1*l2*a1*a2*b2^2*g1^2*g3^2 + 2147483643*l1*l2*a1*a2*b2*b3*g1^2*g2*g3 + 2147483645*l1*l2*a1*a2*b3^2*g1^2*g2^2 + 2*l1*l2*a1*a3*b1^2*g2^2*g3^2 + 4*l1*l2*a1*a3*b1*b2*g1*g2*g3^2 + 4*l1*l2*a1*a3*b1*b3*g1*g2^2*g3 + 2*l1*l2*a1*a3*b2^2*g1^2*g3^2 + 4*l1*l2*a1*a3*b2*b3*g1^2*g2*g3 + 2*l1*l2*a1*a3*b3^2*g1^2*g2^2 + 2*l1*l2*a2*a3*b1^2*g2^2*g3^2 + 4*l1*l2*a2*a3*b1*b2*g1*g2*g3^2 + 4*l1*l2*a2*a3*b1*b3*g1*g2^2*g3 + 2*l1*l2*a2*a3*b2^2*g1^2*g3^2 + 4*l1*l2*a2*a3*b2*b3*g1^2*g2*g3 + 2*l1*l2*a2*a3*b3^2*g1^2*g2^2 + 2147483645*l1*l2*a3^2*b1^2*g2^2*g3^2 + 2147483643*l1*l2*a3^2*b1*b2*g1*g2*g3^2 + 2147483643*l1*l2*a3^2*b1*b3*g1*g2^2*g3 + 2147483645*l1*l2*a3^2*b2^2*g1^2*g3^2 + 2147483643*l1*l2*a3^2*b2*b3*g1^2*g2*g3 + 2147483645*l1*l2*a3^2*b3^2*g1^2*g2^2 + 2*l1*l3*a1*a2*b1^2*g2^2*g3^2 + 4*l1*l3*a1*a2*b1*b2*g1*g2*g3^2 + 4*l1*l3*a1*a2*b1*b3*g1*g2^2*g3 + 2*l1*l3*a1*a2*b2^2*g1^2*g3^2 + 4*l1*l3*a1*a2*b2*b3*g1^2*g2*g3 + 2*l1*l3*a1*a2*b3^2*g1^2*g2^2 + 2147483645*l1*l3*a1*a3*b1^2*g2^2*g3^2 + 2147483643*l1*l3*a1*a3*b1*b2*g1*g2*g3^2 + 2147483643*l1*l3*a1*a3*b1*b3*g1*g2^2*g3 + 2147483645*l1*l3*a1*a3*b2^2*g1^2*g3^2 + 2147483643*l1*l3*a1*a3*b2*b3*g1^2*g2*g3 + 2147483645*l1*l3*a1*a3*b3^2*g1^2*g2^2 + 2147483645*l1*l3*a2^2*b1^2*g2^2*g3^2 + 2147483643*l1*l3*a2^2*b1*b2*g1*g2*g3^2 + 2147483643*l1*l3*a2^2*b1*b3*g1*g2^2*g3 + 2147483645*l1*l3*a2^2*b2^2*g1^2*g3^2 + 2147483643*l1*l3*a2^2*b2*b3*g1^2*g2*g3 + 2147483645*l1*l3*a2^2*b3^2*g1^2*g2^2 + 2*l1*l3*a2*a3*b1^2*g2^2*g3^2 + 4*l1*l3*a2*a3*b1*b2*g1*g2*g3^2 + 4*l1*l3*a2*a3*b1*b3*g1*g2^2*g3 + 2*l1*l3*a2*a3*b2^2*g1^2*g3^2 + 4*l1*l3*a2*a3*b2*b3*g1^2*g2*g3 + 2*l1*l3*a2*a3*b3^2*g1^2*g2^2 + l2^2*a1^2*b1^2*g2^2*g3^2 + 2*l2^2*a1^2*b1*b2*g1*g2*g3^2 + 2*l2^2*a1^2*b1*b3*g1*g2^2*g3 + l2^2*a1^2*b2^2*g1^2*g3^2 + 2*l2^2*a1^2*b2*b3*g1^2*g2*g3 + l2^2*a1^2*b3^2*g1^2*g2^2 + 2147483645*l2^2*a1*a3*b1^2*g2^2*g3^2 + 2147483643*l2^2*a1*a3*b1*b2*g1*g2*g3^2 + 2147483643*l2^2*a1*a3*b1*b3*g1*g2^2*g3 + 2147483645*l2^2*a1*a3*b2^2*g1^2*g3^2 + 2147483643*l2^2*a1*a3*b2*b3*g1^2*g2*g3 + 2147483645*l2^2*a1*a3*b3^2*g1^2*g2^2 + l2^2*a3^2*b1^2*g2^2*g3^2 + 2*l2^2*a3^2*b1*b2*g1*g2*g3^2 + 2*l2^2*a3^2*b1*b3*g1*g2^2*g3 + l2^2*a3^2*b2^2*g1^2*g3^2 + 2*l2^2*a3^2*b2*b3*g1^2*g2*g3 + l2^2*a3^2*b3^2*g1^2*g2^2 + 2147483645*l2*l3*a1^2*b1^2*g2^2*g3^2 + 2147483643*l2*l3*a1^2*b1*b2*g1*g2*g3^2 + 2147483643*l2*l3*a1^2*b1*b3*g1*g2^2*g3 + 2147483645*l2*l3*a1^2*b2^2*g1^2*g3^2 + 2147483643*l2*l3*a1^2*b2*b3*g1^2*g2*g3 + 2147483645*l2*l3*a1^2*b3^2*g1^2*g2^2 + 2*l2*l3*a1*a2*b1^2*g2^2*g3^2 + 4*l2*l3*a1*a2*b1*b2*g1*g2*g3^2 + 4*l2*l3*a1*a2*b1*b3*g1*g2^2*g3 + 2*l2*l3*a1*a2*b2^2*g1^2*g3^2 + 4*l2*l3*a1*a2*b2*b3*g1^2*g2*g3 + 2*l2*l3*a1*a2*b3^2*g1^2*g2^2 + 2*l2*l3*a1*a3*b1^2*g2^2*g3^2 + 4*l2*l3*a1*a3*b1*b2*g1*g2*g3^2 + 4*l2*l3*a1*a3*b1*b3*g1*g2^2*g3 + 2*l2*l3*a1*a3*b2^2*g1^2*g3^2 + 4*l2*l3*a1*a3*b2*b3*g1^2*g2*g3 + 2*l2*l3*a1*a3*b3^2*g1^2*g2^2 + 2147483645*l2*l3*a2*a3*b1^2*g2^2*g3^2 + 2147483643*l2*l3*a2*a3*b1*b2*g1*g2*g3^2 + 2147483643*l2*l3*a2*a3*b1*b3*g1*g2^2*g3 + 2147483645*l2*l3*a2*a3*b2^2*g1^2*g3^2 + 2147483643*l2*l3*a2*a3*b2*b3*g1^2*g2*g3 + 2147483645*l2*l3*a2*a3*b3^2*g1^2*g2^2 + l3^2*a1^2*b1^2*g2^2*g3^2 + 2*l3^2*a1^2*b1*b2*g1*g2*g3^2 + 2*l3^2*a1^2*b1*b3*g1*g2^2*g3 + l3^2*a1^2*b2^2*g1^2*g3^2 + 2*l3^2*a1^2*b2*b3*g1^2*g2*g3 + l3^2*a1^2*b3^2*g1^2*g2^2 + 2147483645*l3^2*a1*a2*b1^2*g2^2*g3^2 + 2147483643*l3^2*a1*a2*b1*b2*g1*g2*g3^2 + 2147483643*l3^2*a1*a2*b1*b3*g1*g2^2*g3 + 2147483645*l3^2*a1*a2*b2^2*g1^2*g3^2 + 2147483643*l3^2*a1*a2*b2*b3*g1^2*g2*g3 + 2147483645*l3^2*a1*a2*b3^2*g1^2*g2^2 + l3^2*a2^2*b1^2*g2^2*g3^2 + 2*l3^2*a2^2*b1*b2*g1*g2*g3^2 + 2*l3^2*a2^2*b1*b3*g1*g2^2*g3 + l3^2*a2^2*b2^2*g1^2*g3^2 + 2*l3^2*a2^2*b2*b3*g1^2*g2*g3 + l3^2*a2^2*b3^2*g1^2*g2^2;

julia> h = 2147483646*l1*a1*a2*b1^2*g2^3*g3 + 2147483646*l1*a1*a2*b1^2*g2*g3^3 + 2147483645*l1*a1*a2*b1*b2*g1*g2^2*g3 + 2147483645*l1*a1*a2*b1*b2*g1*g3^3 + 2147483645*l1*a1*a2*b1*b3*g1*g2^3 + 2147483645*l1*a1*a2*b1*b3*g1*g2*g3^2 + 2147483646*l1*a1*a2*b2^2*g1^2*g2*g3 + 2147483646*l1*a1*a2*b2^2*g2*g3^3 + 2147483646*l1*a1*a2*b2*b3*g1^2*g2^2 + 2147483646*l1*a1*a2*b2*b3*g1^2*g3^2 + 2147483645*l1*a1*a2*b2*b3*g2^2*g3^2 + 2147483646*l1*a1*a2*b3^2*g1^2*g2*g3 + 2147483646*l1*a1*a2*b3^2*g2^3*g3 + l1*a1*a3*b1^2*g2^3*g3 + l1*a1*a3*b1^2*g2*g3^3 + 2*l1*a1*a3*b1*b2*g1*g2^2*g3 + 2*l1*a1*a3*b1*b2*g1*g3^3 + 2*l1*a1*a3*b1*b3*g1*g2^3 + 2*l1*a1*a3*b1*b3*g1*g2*g3^2 + l1*a1*a3*b2^2*g1^2*g2*g3 + l1*a1*a3*b2^2*g2*g3^3 + l1*a1*a3*b2*b3*g1^2*g2^2 + l1*a1*a3*b2*b3*g1^2*g3^2 + 2*l1*a1*a3*b2*b3*g2^2*g3^2 + l1*a1*a3*b3^2*g1^2*g2*g3 + l1*a1*a3*b3^2*g2^3*g3 + l1*a2^2*b1^2*g2*g3^3 + 2*l1*a2^2*b1*b2*g1*g3^3 + 2*l1*a2^2*b1*b3*g1*g2*g3^2 + l1*a2^2*b2^2*g2*g3^3 + 2147483646*l1*a2^2*b2*b3*g1^2*g2^2 + 2*l1*a2^2*b2*b3*g1^2*g3^2 + l1*a2^2*b2*b3*g2^2*g3^2 + l1*a2^2*b3^2*g1^2*g2*g3 + l1*a2*a3*b1^2*g2^3*g3 + 2147483646*l1*a2*a3*b1^2*g2*g3^3 + 2*l1*a2*a3*b1*b2*g1*g2^2*g3 + 2147483645*l1*a2*a3*b1*b2*g1*g3^3 + 2*l1*a2*a3*b1*b3*g1*g2^3 + 2147483645*l1*a2*a3*b1*b3*g1*g2*g3^2 + l1*a2*a3*b2^2*g1^2*g2*g3 + 2147483646*l1*a2*a3*b2^2*g2*g3^3 + 3*l1*a2*a3*b2*b3*g1^2*g2^2 + 2147483644*l1*a2*a3*b2*b3*g1^2*g3^2 + 2147483646*l1*a2*a3*b3^2*g1^2*g2*g3 + l1*a2*a3*b3^2*g2^3*g3 + 2147483646*l1*a3^2*b1^2*g2^3*g3 + 2147483645*l1*a3^2*b1*b2*g1*g2^2*g3 + 2147483645*l1*a3^2*b1*b3*g1*g2^3 + 2147483646*l1*a3^2*b2^2*g1^2*g2*g3 + 2147483645*l1*a3^2*b2*b3*g1^2*g2^2 + l1*a3^2*b2*b3*g1^2*g3^2 + 2147483646*l1*a3^2*b2*b3*g2^2*g3^2 + 2147483646*l1*a3^2*b3^2*g2^3*g3 + l2*a1^2*b1^2*g2^3*g3 + l2*a1^2*b1^2*g2*g3^3 + 2*l2*a1^2*b1*b2*g1*g2^2*g3 + 2*l2*a1^2*b1*b2*g1*g3^3 + 2*l2*a1^2*b1*b3*g1*g2^3 + 2*l2*a1^2*b1*b3*g1*g2*g3^2 + l2*a1^2*b2^2*g1^2*g2*g3 + l2*a1^2*b2^2*g2*g3^3 + l2*a1^2*b2*b3*g1^2*g2^2 + l2*a1^2*b2*b3*g1^2*g3^2 + 2*l2*a1^2*b2*b3*g2^2*g3^2 + l2*a1^2*b3^2*g1^2*g2*g3 + l2*a1^2*b3^2*g2^3*g3 + 2147483646*l2*a1*a2*b1^2*g2*g3^3 + 2147483645*l2*a1*a2*b1*b2*g1*g3^3 + 2147483645*l2*a1*a2*b1*b3*g1*g2*g3^2 + 2147483646*l2*a1*a2*b2^2*g2*g3^3 + l2*a1*a2*b2*b3*g1^2*g2^2 + 2147483645*l2*a1*a2*b2*b3*g1^2*g3^2 + 2147483646*l2*a1*a2*b2*b3*g2^2*g3^2 + 2147483646*l2*a1*a2*b3^2*g1^2*g2*g3 + 2147483645*l2*a1*a3*b1^2*g2^3*g3 + 2147483646*l2*a1*a3*b1^2*g2*g3^3 + 2147483643*l2*a1*a3*b1*b2*g1*g2^2*g3 + 2147483645*l2*a1*a3*b1*b2*g1*g3^3 + 2147483643*l2*a1*a3*b1*b3*g1*g2^3 + 2147483645*l2*a1*a3*b1*b3*g1*g2*g3^2 + 2147483645*l2*a1*a3*b2^2*g1^2*g2*g3 + 2147483646*l2*a1*a3*b2^2*g2*g3^3 + 2147483644*l2*a1*a3*b2*b3*g1^2*g2^2 + 2147483644*l2*a1*a3*b2*b3*g2^2*g3^2 + 2147483646*l2*a1*a3*b3^2*g1^2*g2*g3 + 2147483645*l2*a1*a3*b3^2*g2^3*g3 + l2*a2*a3*b1^2*g2*g3^3 + 2*l2*a2*a3*b1*b2*g1*g3^3 + 2*l2*a2*a3*b1*b3*g1*g2*g3^2 + l2*a2*a3*b2^2*g2*g3^3 + 2147483646*l2*a2*a3*b2*b3*g1^2*g2^2 + 2*l2*a2*a3*b2*b3*g1^2*g3^2 + l2*a2*a3*b2*b3*g2^2*g3^2 + l2*a2*a3*b3^2*g1^2*g2*g3 + l2*a3^2*b1^2*g2^3*g3 + 2*l2*a3^2*b1*b2*g1*g2^2*g3 + 2*l2*a3^2*b1*b3*g1*g2^3 + l2*a3^2*b2^2*g1^2*g2*g3 + 2*l2*a3^2*b2*b3*g1^2*g2^2 + 2147483646*l2*a3^2*b2*b3*g1^2*g3^2 + l2*a3^2*b2*b3*g2^2*g3^2 + l2*a3^2*b3^2*g2^3*g3 + 2147483646*l3*a1^2*b1^2*g2^3*g3 + 2147483646*l3*a1^2*b1^2*g2*g3^3 + 2147483645*l3*a1^2*b1*b2*g1*g2^2*g3 + 2147483645*l3*a1^2*b1*b2*g1*g3^3 + 2147483645*l3*a1^2*b1*b3*g1*g2^3 + 2147483645*l3*a1^2*b1*b3*g1*g2*g3^2 + 2147483646*l3*a1^2*b2^2*g1^2*g2*g3 + 2147483646*l3*a1^2*b2^2*g2*g3^3 + 2147483646*l3*a1^2*b2*b3*g1^2*g2^2 + 2147483646*l3*a1^2*b2*b3*g1^2*g3^2 + 2147483645*l3*a1^2*b2*b3*g2^2*g3^2 + 2147483646*l3*a1^2*b3^2*g1^2*g2*g3 + 2147483646*l3*a1^2*b3^2*g2^3*g3 + l3*a1*a2*b1^2*g2^3*g3 + 2*l3*a1*a2*b1^2*g2*g3^3 + 2*l3*a1*a2*b1*b2*g1*g2^2*g3 + 4*l3*a1*a2*b1*b2*g1*g3^3 + 2*l3*a1*a2*b1*b3*g1*g2^3 + 4*l3*a1*a2*b1*b3*g1*g2*g3^2 + l3*a1*a2*b2^2*g1^2*g2*g3 + 2*l3*a1*a2*b2^2*g2*g3^3 + 3*l3*a1*a2*b2*b3*g1^2*g3^2 + 3*l3*a1*a2*b2*b3*g2^2*g3^2 + 2*l3*a1*a2*b3^2*g1^2*g2*g3 + l3*a1*a2*b3^2*g2^3*g3 + l3*a1*a3*b1^2*g2^3*g3 + 2*l3*a1*a3*b1*b2*g1*g2^2*g3 + 2*l3*a1*a3*b1*b3*g1*g2^3 + l3*a1*a3*b2^2*g1^2*g2*g3 + 2*l3*a1*a3*b2*b3*g1^2*g2^2 + 2147483646*l3*a1*a3*b2*b3*g1^2*g3^2 + l3*a1*a3*b2*b3*g2^2*g3^2 + l3*a1*a3*b3^2*g2^3*g3 + 2147483646*l3*a2^2*b1^2*g2*g3^3 + 2147483645*l3*a2^2*b1*b2*g1*g3^3 + 2147483645*l3*a2^2*b1*b3*g1*g2*g3^2 + 2147483646*l3*a2^2*b2^2*g2*g3^3 + l3*a2^2*b2*b3*g1^2*g2^2 + 2147483645*l3*a2^2*b2*b3*g1^2*g3^2 + 2147483646*l3*a2^2*b2*b3*g2^2*g3^2 + 2147483646*l3*a2^2*b3^2*g1^2*g2*g3 + 2147483646*l3*a2*a3*b1^2*g2^3*g3 + 2147483645*l3*a2*a3*b1*b2*g1*g2^2*g3 + 2147483645*l3*a2*a3*b1*b3*g1*g2^3 + 2147483646*l3*a2*a3*b2^2*g1^2*g2*g3 + 2147483645*l3*a2*a3*b2*b3*g1^2*g2^2 + l3*a2*a3*b2*b3*g1^2*g3^2 + 2147483646*l3*a2*a3*b2*b3*g2^2*g3^2 + 2147483646*l3*a2*a3*b3^2*g2^3*g3;

julia> factor(g)
(b1*g2*g3 + b2*g1*g3 + b3*g1*g2)^2 * (l1*a2 + 2147483646*l1*a3 + 2147483646*l2*a1 + l2*a3 + l3*a1 + 2147483646*l3*a2)^2

julia> factor(h)
2147483646 * (a1*b1^2*g2^3*g3 + a1*b1^2*g2*g3^3 + 2*a1*b1*b2*g1*g2^2*g3 + 2*a1*b1*b2*g1*g3^3 + 2*a1*b1*b3*g1*g2^3 + 2*a1*b1*b3*g1*g2*g3^2 + a1*b2^2*g1^2*g2*g3 + a1*b2^2*g2*g3^3 + a1*b2*b3*g1^2*g2^2 + a1*b2*b3*g1^2*g3^2 + 2*a1*b2*b3*g2^2*g3^2 + a1*b3^2*g1^2*g2*g3 + a1*b3^2*g2^3*g3 + 2147483646*a2*b1^2*g2*g3^3 + 2147483645*a2*b1*b2*g1*g3^3 + 2147483645*a2*b1*b3*g1*g2*g3^2 + 2147483646*a2*b2^2*g2*g3^3 + a2*b2*b3*g1^2*g2^2 + 2147483645*a2*b2*b3*g1^2*g3^2 + 2147483646*a2*b2*b3*g2^2*g3^2 + 2147483646*a2*b3^2*g1^2*g2*g3 + 2147483646*a3*b1^2*g2^3*g3 + 2147483645*a3*b1*b2*g1*g2^2*g3 + 2147483645*a3*b1*b3*g1*g2^3 + 2147483646*a3*b2^2*g1^2*g2*g3 + 2147483645*a3*b2*b3*g1^2*g2^2 + a3*b2*b3*g1^2*g3^2 + 2147483646*a3*b2*b3*g2^2*g3^2 + 2147483646*a3*b3^2*g2^3*g3) * (l1*a2 + 2147483646*l1*a3 + 2147483646*l2*a1 + l2*a3 + l3*a1 + 2147483646*l3*a2)

julia> gcd(g, h)
# this is hanging

This calls directly into nmod_mpoly_gcd.

For comparison, in Magma:

> time GCD(g, h);
l1*a2 + 2147483646*l1*a3 + 2147483646*l2*a1 + l2*a3 + l3*a1 + 2147483646*l3*a2
Time: 0.000

[thofma]

One more breadcrumb. The "generic" implementation of multivariate polynomials in AbstractAlgebra (also from @tthsqe12) is also quite fast:

julia> R = Nemo.AbstractAlgebra.Generic.MPolyRing{fpFieldElem}(Nemo.Native.GF(2^31 - 1), Symbol.(["l1", "l2", "l3", "a1", "a2", "a3", "b1", "b2", "b3", "g1", "g2", "g3"]));

julia> l1, l2, l3, a1, a2, a3, b1, b2, b3, g1, g2, g3 = gens(R);

julia> g = ...; h = ...;

julia> @time gcd(g, h)
  0.017169 seconds (270.32 k allocations: 19.944 MiB, 34.73% gc time)
l1*a2 + 2147483646*l1*a3 + 2147483646*l2*a1 + l2*a3 + l3*a1 + 2147483646*l3*a2

[fredrik-johansson]

Reproducer in C:

#include "flint/nmod_mpoly.h"
#include "flint/nmod_mpoly_factor.h"
#include "flint/profiler.h"

const char * vars[] = {
    "l1", "l2", "l3", "a1", "a2", "a3", "b1", "b2", "b3", "g1", "g2", "g3"
};

const char * sg = "(b1*g2*g3 + b2*g1*g3 + b3*g1*g2)^2 * (l1*a2 + 2147483646*l1*a3 + 2147483646*l2*a1 + l2*a3 + l3*a1 + 2147483646*l3*a2)^2";

const char * sh = "2147483646 * (a1*b1^2*g2^3*g3 + a1*b1^2*g2*g3^3 + 2*a1*b1*b2*g1*g2^2*g3 + 2*a1*b1*b2*g1*g3^3 + 2*a1*b1*b3*g1*g2^3 + 2*a1*b1*b3*g1*g2*g3^2 + a1*b2^2*g1^2*g2*g3 + a1*b2^2*g2*g3^3 + a1*b2*b3*g1^2*g2^2 + a1*b2*b3*g1^2*g3^2 + 2*a1*b2*b3*g2^2*g3^2 + a1*b3^2*g1^2*g2*g3 + a1*b3^2*g2^3*g3 + 2147483646*a2*b1^2*g2*g3^3 + 2147483645*a2*b1*b2*g1*g3^3 + 2147483645*a2*b1*b3*g1*g2*g3^2 + 2147483646*a2*b2^2*g2*g3^3 + a2*b2*b3*g1^2*g2^2 + 2147483645*a2*b2*b3*g1^2*g3^2 + 2147483646*a2*b2*b3*g2^2*g3^2 + 2147483646*a2*b3^2*g1^2*g2*g3 + 2147483646*a3*b1^2*g2^3*g3 + 2147483645*a3*b1*b2*g1*g2^2*g3 + 2147483645*a3*b1*b3*g1*g2^3 + 2147483646*a3*b2^2*g1^2*g2*g3 + 2147483645*a3*b2*b3*g1^2*g2^2 + a3*b2*b3*g1^2*g3^2 + 2147483646*a3*b2*b3*g2^2*g3^2 + 2147483646*a3*b3^2*g2^3*g3) * (l1*a2 + 2147483646*l1*a3 + 2147483646*l2*a1 + l2*a3 + l3*a1 + 2147483646*l3*a2)";

int main()
{
    nmod_mpoly_ctx_t ctx;
    nmod_mpoly_ctx_init(ctx, 12, ORD_LEX, (UWORD(1)<<31) - 1);

    nmod_mpoly_t g, h, y;
    nmod_mpoly_init(g, ctx);
    nmod_mpoly_init(h, ctx);
    nmod_mpoly_init(y, ctx);

    nmod_mpoly_set_str_pretty(g, sg, vars, ctx);
    nmod_mpoly_set_str_pretty(h, sh, vars, ctx);
    TIMEIT_START;
    //nmod_mpoly_gcd_zippel(y, g, h, ctx);
    nmod_mpoly_gcd(y, g, h, ctx);
    TIMEIT_STOP;

    nmod_mpoly_print_pretty(y, vars, ctx); flint_printf("\n");
}

Finishes in 0.0005 seconds if one calls nmod_mpoly_gcd_zippel instead of nmod_mpoly_gcd. Though the place where nmod_mpoly_gcd gets stuck is actually inside Zippel. For someone reason Zippel works with the original polynomials but not with the deflated polynomials preprocessed by nmod_mpoly_gcd. Program to reproduce:

#include "nmod_mpoly.h"
#include "nmod_mpoly_factor.h"
#include "profiler.h"

const char * sg2 = "2147483646*x3*x4^2*x7^2*x11^3*x12+2147483646*x3*x4^2*x7^2*x11*x12^3+2147483645*x3*x4^2*x7*x8*x10*x11^2*x12+2147483645*x3*x4^2*x7*x8*x10*x12^3+2147483645*x3*x4^2*x7*x9*x10*x11^3+2147483645*x3*x4^2*x7*x9*x10*x11*x12^2+2147483646*x3*x4^2*x8^2*x10^2*x11*x12+2147483646*x3*x4^2*x8^2*x11*x12^3+2147483646*x3*x4^2*x8*x9*x10^2*x11^2+2147483646*x3*x4^2*x8*x9*x10^2*x12^2+2147483645*x3*x4^2*x8*x9*x11^2*x12^2+2147483646*x3*x4^2*x9^2*x10^2*x11*x12+2147483646*x3*x4^2*x9^2*x11^3*x12+x3*x4*x5*x7^2*x11^3*x12+2*x3*x4*x5*x7^2*x11*x12^3+2*x3*x4*x5*x7*x8*x10*x11^2*x12+4*x3*x4*x5*x7*x8*x10*x12^3+2*x3*x4*x5*x7*x9*x10*x11^3+4*x3*x4*x5*x7*x9*x10*x11*x12^2+x3*x4*x5*x8^2*x10^2*x11*x12+2*x3*x4*x5*x8^2*x11*x12^3+3*x3*x4*x5*x8*x9*x10^2*x12^2+3*x3*x4*x5*x8*x9*x11^2*x12^2+2*x3*x4*x5*x9^2*x10^2*x11*x12+x3*x4*x5*x9^2*x11^3*x12+x3*x4*x6*x7^2*x11^3*x12+2*x3*x4*x6*x7*x8*x10*x11^2*x12+2*x3*x4*x6*x7*x9*x10*x11^3+x3*x4*x6*x8^2*x10^2*x11*x12+2*x3*x4*x6*x8*x9*x10^2*x11^2+2147483646*x3*x4*x6*x8*x9*x10^2*x12^2+x3*x4*x6*x8*x9*x11^2*x12^2+x3*x4*x6*x9^2*x11^3*x12+2147483646*x3*x5^2*x7^2*x11*x12^3+2147483645*x3*x5^2*x7*x8*x10*x12^3+2147483645*x3*x5^2*x7*x9*x10*x11*x12^2+2147483646*x3*x5^2*x8^2*x11*x12^3+x3*x5^2*x8*x9*x10^2*x11^2+2147483645*x3*x5^2*x8*x9*x10^2*x12^2+2147483646*x3*x5^2*x8*x9*x11^2*x12^2+2147483646*x3*x5^2*x9^2*x10^2*x11*x12+2147483646*x3*x5*x6*x7^2*x11^3*x12+2147483645*x3*x5*x6*x7*x8*x10*x11^2*x12+2147483645*x3*x5*x6*x7*x9*x10*x11^3+2147483646*x3*x5*x6*x8^2*x10^2*x11*x12+2147483645*x3*x5*x6*x8*x9*x10^2*x11^2+x3*x5*x6*x8*x9*x10^2*x12^2+2147483646*x3*x5*x6*x8*x9*x11^2*x12^2+2147483646*x3*x5*x6*x9^2*x11^3*x12";

const char * sh2 = "x2*x4^2*x7^2*x11^3*x12+x2*x4^2*x7^2*x11*x12^3+2*x2*x4^2*x7*x8*x10*x11^2*x12+2*x2*x4^2*x7*x8*x10*x12^3+2*x2*x4^2*x7*x9*x10*x11^3+2*x2*x4^2*x7*x9*x10*x11*x12^2+x2*x4^2*x8^2*x10^2*x11*x12+x2*x4^2*x8^2*x11*x12^3+x2*x4^2*x8*x9*x10^2*x11^2+x2*x4^2*x8*x9*x10^2*x12^2+2*x2*x4^2*x8*x9*x11^2*x12^2+x2*x4^2*x9^2*x10^2*x11*x12+x2*x4^2*x9^2*x11^3*x12+2147483646*x2*x4*x5*x7^2*x11*x12^3+2147483645*x2*x4*x5*x7*x8*x10*x12^3+2147483645*x2*x4*x5*x7*x9*x10*x11*x12^2+2147483646*x2*x4*x5*x8^2*x11*x12^3+x2*x4*x5*x8*x9*x10^2*x11^2+2147483645*x2*x4*x5*x8*x9*x10^2*x12^2+2147483646*x2*x4*x5*x8*x9*x11^2*x12^2+2147483646*x2*x4*x5*x9^2*x10^2*x11*x12+2147483645*x2*x4*x6*x7^2*x11^3*x12+2147483646*x2*x4*x6*x7^2*x11*x12^3+2147483643*x2*x4*x6*x7*x8*x10*x11^2*x12+2147483645*x2*x4*x6*x7*x8*x10*x12^3+2147483643*x2*x4*x6*x7*x9*x10*x11^3+2147483645*x2*x4*x6*x7*x9*x10*x11*x12^2+2147483645*x2*x4*x6*x8^2*x10^2*x11*x12+2147483646*x2*x4*x6*x8^2*x11*x12^3+2147483644*x2*x4*x6*x8*x9*x10^2*x11^2+2147483644*x2*x4*x6*x8*x9*x11^2*x12^2+2147483646*x2*x4*x6*x9^2*x10^2*x11*x12+2147483645*x2*x4*x6*x9^2*x11^3*x12+x2*x5*x6*x7^2*x11*x12^3+2*x2*x5*x6*x7*x8*x10*x12^3+2*x2*x5*x6*x7*x9*x10*x11*x12^2+x2*x5*x6*x8^2*x11*x12^3+2147483646*x2*x5*x6*x8*x9*x10^2*x11^2+2*x2*x5*x6*x8*x9*x10^2*x12^2+x2*x5*x6*x8*x9*x11^2*x12^2+x2*x5*x6*x9^2*x10^2*x11*x12+x2*x6^2*x7^2*x11^3*x12+2*x2*x6^2*x7*x8*x10*x11^2*x12+2*x2*x6^2*x7*x9*x10*x11^3+x2*x6^2*x8^2*x10^2*x11*x12+2*x2*x6^2*x8*x9*x10^2*x11^2+2147483646*x2*x6^2*x8*x9*x10^2*x12^2+x2*x6^2*x8*x9*x11^2*x12^2+x2*x6^2*x9^2*x11^3*x12";

int main()
{
    nmod_mpoly_ctx_t ctx;
    nmod_mpoly_ctx_init(ctx, 12, ORD_LEX, (UWORD(1)<<31) - 1);

    nmod_mpoly_t g, h, y;
    nmod_mpoly_init(g, ctx);
    nmod_mpoly_init(h, ctx);
    nmod_mpoly_init(y, ctx);

    nmod_mpoly_set_str_pretty(g, sg2, NULL, ctx);
    nmod_mpoly_set_str_pretty(h, sh2, NULL, ctx);

    nmod_mpoly_gcd_zippel(y, g, h, ctx);
    nmod_mpoly_print_pretty(y, NULL, ctx); flint_printf("\n");
}

Now, this one actually works if one calls nmod_mpoly_gcd_zippel2 instead of nmod_mpoly_gcd_zippel. But nmod_mpoly_gcd_zippel2 hangs if one gives it the original polynomials (!).

@tthsqe12 is obviously the best person to debug this, if he has the time...