gap-system / gap

Main development repository for GAP - Groups, Algorithms, Programming, a System for Computational Discrete Algebra
https://www.gap-system.org
GNU General Public License v2.0
763 stars 159 forks source link

Fix a bug where multiplying a compressed matrix by a finite field element could produce a corrupt result leading to subsequent unexpected errors or even wrong results #5688

Closed fingolfin closed 2 months ago

fingolfin commented 2 months ago

There was a long-standing bug where multiplying a compressed matrix over a finite field by a scalar could lead to a corrupt result which exhibited weird behavior in subsequent computations.

The root cause of this is that in GAP, finite field elements like Z(2^2) and Z(2^4)^5 are equal but (internally) not identical. In this case, a GAP library function had an input validation test that check if a scalar is in the right field (in the new test case, the field is GF(64), and Z(2^2) lives in that, hence also Z(2^4)^5 as it is equal). But the kernel code then used a different test which distinguishes between these two elements. For Z(2^2) it happily proceeded as before and all was good. But for Z(2^4)^5 it instead dispatches to a generic function which ends up producing a result over the wrong field. Specifically, before this patch, we had this in the example from the new .tst file:

gap> List(a, Q_VEC8BIT);
[ 64, 64, 4, 4, 4, 4 ]
gap> List(b, Q_VEC8BIT);
[ 64, 64, 64, 64, 64, 64 ]

With the fix, both matrices give the correct second result.

Please provide a short summary of this PR and its purpose here. E.g., does it add a new feature, and which? Does it fix a bug, and which? If there is an associated issue, please list it here.

Resolves #5684