using SymPy
function minpoly(x, y, f, g, h, N)
m = sympy.Poly(f, x).degree()
n = sympy.Poly(g, y).degree()
K = sympy.Poly(h, x).degree()
L = sympy.Poly(h, y).degree()
λ = symbols("λ[0:$N]")
z = symbols("z")
P = sum(λ[begin+k]*z^k for k in 0:N-1) + z^N
p = P(z => h).expand()
@time for k in K*N:-1:m
p = p(x^k => x^k - x^(k-m)*f).expand()
end
@time for l in L*N:-1:n
p = p(y^l => y^l - y^(l-n)*g).expand()
end
Q = sympy.Poly(p, x, y)
C = Q.coeffs()
@time sol = solve(C, λ)
P = sum(get(sol, λ[begin+k], λ[begin+k])*z^k for k in 0:N-1) + z^N
[
sympy.Poly(f, x)
sympy.Poly(g, y)
sympy.Poly(h, x, y)
sympy.Poly(P, z)
]
end
minpoly (generic function with 1 method)
@vars a p x y
f = x^2 - a
g = y^2 - p
h = x + y
minpoly(x, y, f, g, h, 4)
0.023271 seconds (297 allocations: 7.094 KiB) 0.019818 seconds (297 allocations: 7.094 KiB) 0.298115 seconds (820.74 k allocations: 49.065 MiB, 2.47% gc time, 1.46% compilation time)
@vars a p x y
f = x^2 - a
g = y^2 - p
h = x * y
minpoly(x, y, f, g, h, 2)
0.000627 seconds (83 allocations: 2.031 KiB) 0.000587 seconds (83 allocations: 2.031 KiB) 0.026929 seconds (61.50 k allocations: 3.820 MiB, 17.14% compilation time)
@vars a p x y
f = x^2 - a
g = y^3 - p
h = x + y
minpoly(x, y, f, g, h, 6)
0.040974 seconds (589 allocations: 14.031 KiB) 0.032724 seconds (489 allocations: 11.656 KiB) 0.052577 seconds (62.55 k allocations: 3.895 MiB, 12.21% compilation time)
@vars a p x y
f = x^2 - a
g = y^3 - p
h = x * y
minpoly(x, y, f, g, h, 6)
0.014113 seconds (589 allocations: 14.031 KiB) 0.007490 seconds (489 allocations: 11.656 KiB) 0.009286 seconds (248 allocations: 7.594 KiB)
@vars a p q x y
f = x^2 - a
g = y^3 + p*y + q
h = x + y
minpoly(x, y, f, g, h, 6)
0.000561 seconds (589 allocations: 14.031 KiB) 0.043253 seconds (489 allocations: 11.656 KiB) 0.060136 seconds (248 allocations: 7.594 KiB)
@vars a p q x y
f = x^2 - a
g = y^3 + p*y + q
h = x * y
minpoly(x, y, f, g, h, 6)
0.000542 seconds (589 allocations: 14.031 KiB) 0.018329 seconds (489 allocations: 11.656 KiB) 0.021076 seconds (248 allocations: 7.594 KiB)
@vars a p q r x y
f = x^2 - a
g = y^4 + p*y^2 + q*y + r
h = x + y
minpoly(x, y, f, g, h, 8)
0.093855 seconds (925 allocations: 22.031 KiB) 0.100663 seconds (679 allocations: 16.188 KiB) 0.212156 seconds (62.62 k allocations: 3.897 MiB, 3.41% gc time, 2.58% compilation time)
@vars a p q r x y
f = x^2 - a
g = y^4 + p*y^2 + q*y + r
h = x * y
minpoly(x, y, f, g, h, 8)
0.036351 seconds (925 allocations: 22.031 KiB) 0.042049 seconds (679 allocations: 16.188 KiB) 0.051188 seconds (314 allocations: 9.562 KiB)
@vars a p q r s x y
f = x^2 - a
g = y^5 + p*y^3 + q*y^2 + r*y + s
h = x + y
minpoly(x, y, f, g, h, 10)
0.198323 seconds (1.29 k allocations: 30.828 KiB) 0.200592 seconds (902 allocations: 21.516 KiB) 30.746824 seconds (62.68 k allocations: 3.899 MiB, 0.02% compilation time)
@vars a p q r s x y
f = x^2 - a
g = y^5 + p*y^3 + q*y^2 + r*y + s
h = (x * y)^2
minpoly(x, y, f, g, h, 5)
0.031418 seconds (1.29 k allocations: 30.828 KiB) 0.048821 seconds (902 allocations: 21.516 KiB) 0.081856 seconds (62.52 k allocations: 3.894 MiB, 6.15% compilation time)
@vars a p x y
f = x^3 - a
g = y^3 - p
h = (x + y)^3
minpoly(x, y, f, g, h, 3)
0.066229 seconds (993 allocations: 23.656 KiB) 0.065860 seconds (993 allocations: 23.656 KiB) 0.048861 seconds (61.95 k allocations: 3.855 MiB, 9.78% compilation time)
@vars a p x y
f = x^3 - a
g = y^3 - p
h = x * y
minpoly(x, y, f, g, h, 3)
0.000927 seconds (107 allocations: 2.594 KiB) 0.000832 seconds (107 allocations: 2.594 KiB) 0.003331 seconds (126 allocations: 4.172 KiB)
@vars a b p q x y
f = x^3 + a*x + b
g = y^3 + p*y + q
h = x + y
minpoly(x, y, f, g, h, 9)
0.185318 seconds (993 allocations: 23.656 KiB) 0.287258 seconds (993 allocations: 23.656 KiB) 3.330868 seconds (62.65 k allocations: 3.898 MiB, 0.18% compilation time)
@vars a b p q x y
f = x^3 + a*x + b
g = y^3 + p*y + q
h = x * y
minpoly(x, y, f, g, h, 9)
0.075285 seconds (993 allocations: 23.656 KiB) 0.238995 seconds (993 allocations: 23.656 KiB) 0.156825 seconds (347 allocations: 10.562 KiB)
@vars a p q x y
f = x^3 - a
g = y^4 + p*y + q
h = x + y
minpoly(x, y, f, g, h, 12)
0.292580 seconds (1.57 k allocations: 37.516 KiB) 0.380052 seconds (1.43 k allocations: 34.047 KiB) 3.643590 seconds (62.84 k allocations: 3.905 MiB, 0.16% compilation time)
@vars a p q x y
f = x^3 - a
g = y^4 + p*y + q
h = x * y
minpoly(x, y, f, g, h, 12)
0.076121 seconds (1.57 k allocations: 37.516 KiB) 0.101282 seconds (1.43 k allocations: 34.047 KiB) 0.051363 seconds (551 allocations: 16.844 KiB)