Bug in polynomial GCD (FLINT)

[Anton Mellit]

Here is the code:

R.<q>=QQ[]

X=3*q^12 - 8*q^11 - 24*q^10 - 48*q^9 - 84*q^8 - 92*q^7 - 92*q^6 - 70*q^5 - 50*q^4 - 27*q^3 - 13*q^2 - 4*q - 1

Y=q^13 - 2*q^12 + 2*q^10 - q^9

print gcd(X,Y)

print X(1)

Here is the output:

q - 1 -510

The bug is extremely serious because it affects all computations with rational functions. It is also quite rare, I believe. I traced it down to the function _fmpz_poly_gcd_heuristic in FLINT. The bug is triggered when the heuristic algorithm fails, one of the divisibility checks fails, but still the value is returned as o.k.

The fix is easy, just one line needs to be added

if (divides) /* quotient really was exact */ { --->>>>> divides=0;

[John Cremona]

Thanks, Anton -- I have forwarded to sage-devel and flint-devel and
we'll try to get this fixed before the release of 6.5.

John Cremona

> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.

[John Cremona]

On 17 February 2015 at 09:06, John Cremona <john.c...@gmail.com> wrote:
> Thanks, Anton -- I have forwarded to sage-devel and flint-devel and
> we'll try to get this fixed before the release of 6.5.

Too late, it was released overnight.