> < ^ Date: Tue, 24 Sep 1996 15:13:30 +0200
> < ^ From: Alexander Hulpke <hulpke@math.colostate.edu >
^ Subject: FIX 25 for DANGEROUS bug in GAP/lib 3.4.3.0 'Factors' for rat. pols.

This mail contains a bugfix for a dangerous problem in GAP 3.4.3.
*You should apply this bugfix as soon as possible.*
The problem is in 'RationalsPolynomialsOps.Factors', and might cause it
to return reducible factors.

ACKNOWLEDGEMENT

We thank Willem A. de Graaf (Technische Universiteit Eindhoven) for
bringing this problem to our attention in a GAP forum mail of 1996/09/18.

VERSION

GAP/lib 3.4.3.0

PRIORITY

The problem is a dangerous problem, because it may cause a computation
to produce incorrect results without a warning. This the bugfix has
high priority, and we recommend that you apply it as soon as possible.

HOW TO APPLY

Go to the GAP directory (the directory with the 'lib/' subdirectory),
name this mail 'fix25lib.dif', and issue the command:

patch -p0 < fix25lib.dif

If 'patch' writes "I can't seem to find a patch in there" try 'patch -v'.
If 'patch -v' gives an error message or reports a version older than 2.1,
get 2.1 from 'ftp://FTP.Math.RWTH-Aachen.DE/pub/gap/utils/patch2_1.zoo'.

This fix changes only the library.
Thus you need not recompile the GAP kernel.

DESCRIPTION

Polynomials with integer roots might get factored erraneously,
that is 'Factors' might return reducible factors.

CORRECT BEHAVIOUR

gap> y := Indeterminate( Rationals );;  y.name := "y";;
gap> f := y^33
>       - 398550 * y^31
>       + 66186201873 * y^29
>       - 5971817014857100 * y^27
>       + 319879423075055974416 * y^25
>       - 10453569133068665704152000 * y^23
>       + 207491014558959631527689015040 * y^21
>       - 2448295340120142096293200047744000 * y^19
>       + 16690739160259700445725003902608322560 * y^17
>       - 62701173265160849595209547823580350464000 * y^15
>       + 118869582948995926691687807245961904820322304 * y^13
>       - 95752347343101572852967993673317241915126579200 * y^11
>       + 22338679946180069821565185491251863734781426532352 * y^9
>       - 611471306080989784227382973634662004989868009062400 * y^7
>       + 5410092199316503850833490994152109788519901066952704 * y^5
>       - 16075861728797055597248567344887907079321523585024000 * y^3
>       + 11254997789155806098371908864638669722435410984960000 * y;;
gap> Factors( f );
[ y - 324, y - 270, y - 252, y - 234, y - 216, y - 162, y - 108, y - 90,
  y - 72, y - 54, y - 36, y - 18, y - 4, y - 3, y - 2, y - 1, y + 1, y + 2,
  y + 3, y + 4, y + 18, y + 36, y + 54, y + 72, y + 90, y + 108, y + 162,
  y + 216, y + 234, y + 252, y + 270, y + 324, y ]

COMMENT

The implemented Hensel lifting process does not work correctly if 0 is a
root of the polynomial that is to be factored. As the factoring routine
applies an initial Tschirnhaus transform to get the norm small, this
might also affect polynomials with small absolute value integer roots.
The remedy is to treat the case of root 0 before starting the Hensel
lift. This had been introduced already in the algebraic factoring code,
thus a similar fix there is not needed.

DIFFS

Prereq: 3.31.1.2
--- lib/polyrat.g       Thu Dec 21 15:30:36 1995
+++ lib/polyrat.g       Mon Sep 23 12:28:24 1996
@@ -3,14 +3,17 @@
 #A  polyrat.g                   GAP library                      Frank Celler
 #A                                                         & Alexander Hulpke
 ##
-#A  @(#)$Id: 1.html,v 1.2 2004/04/21 15:04:29 felsch Exp $
+#A  @(#)$Id: 1.html,v 1.2 2004/04/21 15:04:29 felsch Exp $
 ##
 #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
 ##
 ##  This file contains functions for polynomials over the Rationals.
 ##
 #H  $Log: 1.html,v $
 #H  Revision 1.2  2004/04/21 15:04:29  felsch
 #H  Corrected links in the Forum Archive pages.   VF
 #H
 #H  Revision 1.1.1.1  2004/04/20 13:39:35  felsch
 #H  The final GAP-Forum archive until 2003.
 #H
 #H  Revision 1.4  2003/06/12 19:20:34  gap
 #H  Further update. AH
 #H
 #H  Revision 1.3  1997/08/15 11:19:38  gap
 #H  New forum setup. AH
 #H
 #H  Revision 1.2  1997/04/24 15:33:16  gap
 #H  These files were replaced by the versions in WWW. The content is basically the
 #H  same but the formatting has been much more friendly towards the HTML-Converter.
 #H  AH
 #H
 #H  Revision 1.1  1996/10/30 13:07:07  gap
 #H  added forum archive and translation files.
 #H
-#H  Revision 3.31.1.2  1994/09/19  08:28:11  ahulpke
+#H  Revision 3.31.1.3  1996/09/23 10:28:01  ahulpke
+#H  Fixed factoring polynomials with linear factors
+#H
+#H  Revision 3.31.1.2  1994/09/19 08:28:11  ahulpke
 #H  fixed factorization of square part
 #H
 #H  Revision 3.31.1.1  1994/08/02  10:11:48  ahulpke
@@ -1621,7 +1624,16 @@
         InfoPoly2( "#I  <f> is a linear power\n" );
         s := [ q ];
     else
-        s := R.operations.FactorsSquarefree( R, q );
+
+       # treat zeroes
+       if q.valuation>0 then
+         s:=[X(q.baseRing)];
+         q:=q/(X(q.baseRing));
+        else
+         s:=[];
+        fi;
+        s:=Concatenation(s,R.operations.FactorsSquarefree( R, q ));
+
     fi;

     # find factors of <g>
Prereq: 3.1
--- lib/polystff.g      Thu Dec 21 15:30:36 1995
+++ lib/polystff.g      Mon Sep 23 12:28:38 1996
@@ -2,7 +2,7 @@
 ##
 #A  polystff.g                  GAP library                  Alexander Hulpke
 ##
-#A  @(#)$Id: 1.html,v 1.2 2004/04/21 15:04:29 felsch Exp $
+#A  @(#)$Id: 1.html,v 1.2 2004/04/21 15:04:29 felsch Exp $
 ##
 #Y  Copyright (C)  1994,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
 ##
@@ -11,7 +11,10 @@
 ##  fit better, however, in other files.
 ##
 #H  $Log: 1.html,v $
 #H  Revision 1.2  2004/04/21 15:04:29  felsch
 #H  Corrected links in the Forum Archive pages.   VF
 #H
 #H  Revision 1.1.1.1  2004/04/20 13:39:35  felsch
 #H  The final GAP-Forum archive until 2003.
 #H
 #H  Revision 1.4  2003/06/12 19:20:34  gap
 #H  Further update. AH
 #H
 #H  Revision 1.3  1997/08/15 11:19:38  gap
 #H  New forum setup. AH
 #H
 #H  Revision 1.2  1997/04/24 15:33:16  gap
 #H  These files were replaced by the versions in WWW. The content is basically the
 #H  same but the formatting has been much more friendly towards the HTML-Converter.
 #H  AH
 #H
 #H  Revision 1.1  1996/10/30 13:07:07  gap
 #H  added forum archive and translation files.
 #H
-#H  Revision 3.1  1994/06/03  10:49:44  ahulpke
+#H  Revision 3.1.1.1  1996/09/23 10:28:35  ahulpke
+#H  Fixed factoring polynomials with linear factors
+#H
+#H  Revision 3.1  1994/06/03 10:49:44  ahulpke
 #H  initial revision under RCS
 #H
 ##
@@ -756,7 +759,7 @@
   q:=[];
   n:=Length(g.coefficients);
   m:=Length(f.coefficients)-n;
-  f:=ShallowCopy(f.coefficients);
+  f:=ShallowCopy(ShiftedCoeffs(f.coefficients,f.valuation));
   if IsField(R) then
     for i in [0..m] do
       c:=f[(m-i+n)]/g.coefficients[n];
END OF  fix25lib.dif ________________________________________________________

> < [top]