Re: polisirreducible and factor

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

On Tue, 18 Sep 2001, Jean-Marc Sac-Epée wrote:
> I have strange problems with "polisirreducible" and "factor" functions,
> which fail with some peculiar polynomial.
>
> Let me give the following sample:
>
> ? p=x^44 + x^42 - x^31 - x^29 - x^26 - x^24 - x^23 - x^21 - x^20 -
>  x^18 - x^15 - x^13 + x^2 + 1
> %1 = x^44 + x^42 - x^31 - x^29 - x^26 - x^24 - x^23 - x^21 - x^20- x^18
> - x^15 - x^13 + x^2 + 1
> ? factor(p)
>   ***   bug in GP (Segmentation Fault), please report
> ? polisirreducible(p)
>  ***   bug in GP (Segmentation Fault), please report
>
> I think that  polisirreducible and factor functions have problems with
> polynomials which are divisible by cyclotomic polynomials. Is it
> possible?

It's quite an annoying bug to correct: it has been fixed in the unstable
version (e.g current CVS) for a while, but the unstable and stable versions
have diverged significantly, esp. in the area of rational polynomial
arithmetic.

The following patch fixes your specific problem (true rational factors missed
during exhaustive enumeration due to inadequate degree bound). It doesn't fix
a number of other (less severe) problems, but which require extensive changes
in the code [the diff between the relevant files is more than 1000 lines
long...]. If you make extensive use of polynomial arithmetic, and have access
to CVS, I'd advise checking the unstable version from times to times.

Hope this helps,

    Karim.

diff -c -r1.42.2.3 polarit2.c
*** src/basemath/polarit2.c     2001/05/29 13:00:21     1.42.2.3
--- src/basemath/polarit2.c     2001/09/18 13:47:27
***************
*** 1290,1296 ****
  #if 0
    res = combine_factors_old(a, famod, prime, klim, hint);
  #else
!   res = combine_factors(a, famod, prime, klim, hint);
  #endif
    return gerepileupto(av, gcopy(res));
  }
--- 1290,1296 ----
  #if 0
    res = combine_factors_old(a, famod, prime, klim, hint);
  #else
!   res = combine_factors(a, famod, prime, da-1, hint);
  #endif
    return gerepileupto(av, gcopy(res));
  }


-- 
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://www.parigp-home.de/