id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
28199 gcd can be very slow in AA[x] vdelecroix "Here is a x50 slower example
{{{
sage: x,y = polygens(QQ,""x,y"")
sage: p1 = x^5 + 6*x^4 - 42*x^3 - 142*x^2 + 467*x + 422
sage: p2 = p1(x=(x-1)^2)
sage: p3 = p2(x=x*y).resultant(p2,x).univariate_polynomial()
sage: p4, = [f[0] for f in p3.factor() if f[0].degree() == 80]
sage: %time _ = p4.squarefree_decomposition()
CPU times: user 807 µs, sys: 0 ns, total: 807 µs
Wall time: 883 µs
sage: %time _ = p4.change_ring(AA).squarefree_decomposition()
CPU times: user 40.1 s, sys: 3.21 ms, total: 40.1 s
Wall time: 40.1 s
}}}
This problem originally appeared in #17895 (where a better workaround has been found)." defect new major sage-9.7 algebra bruno mmezzarobba N/A u/bruno/gcd_via_UFD 62db08ca0b85c535f3d6ef5bacac19ecefa8908b