Bug in modp sparse matrix multiply

[Daniel Roche]

Hi sagers,

First let me say thanks for the great piece of software that is sage. You all do a tremendous job and maybe don't get thanked enough.

There appears to be a bug in sparse matrix multiplication over small finite fields:

sage: p = next_prime(2**15); p
32771
sage: M = Matrix(GF(p), 1,3, lambda i,j: -1, sparse=True); M
[32770 32770 32770]
sage: M*M.transpose()
[32738] # INCORRECT, should be 3
sage: M*M.transpose() + 2**32
[3] # it was off by 2^32, hmmm...

Being off by 2^32 hints that there is an integer overflow or signedness issue, and indeed I believe the culprit is in the _matrix_times_matrix_ method on line 387 of matrix_modn_sparse.pyx, where a cdef int s is added up without reducing modulo p.

I am currently running release 8.0 on a 64-bit Debian machine. I had some old versions of sage lying around and the bug seems to be present in versions going back at least to 5.6; it's not a recent change.

Thanks for taking a look!

-Dan

[Vincent Delecroix]

Dear Dan,

Thanks for the report! This is indeed a bug. If you want to go further
and fix the bug yourself, the procedure is described here

http://doc.sagemath.org/html/en/developer/

Otherwise I will open the relevant ticket.

Vincent

On 20/08/2017 19:59, Daniel Roche wrote:
> Hi sagers,
>
> First let me say thanks for the great piece of software that is sage. You
> all do a tremendous job and maybe don't get thanked enough.
>
> There appears to be a bug in sparse matrix multiplication over small finite
> fields:
>
> sage: p = next_prime(2**15); p
> 32771
> sage: M = Matrix(GF(p), 1,3, lambda i,j: -1, sparse=True); M
> [32770 32770 32770]
> sage: M*M.transpose()
> [32738] # INCORRECT, should be 3
> sage: M*M.transpose() + 2**32
> [3] # it was off by 2^32, hmmm...
>
> Being off by 2^32 hints that there is an integer overflow or signedness
> issue, and indeed I believe the culprit is in the _matrix_times_matrix_
> method on line 387 of matrix_modn_sparse.pyx

> <https://github.com/sagemath/sage/blob/master/src/sage/matrix/matrix_modn_sparse.pyx#L387>,

[Daniel Roche]

Thanks, I submitted and fixed the bug here (in case anyone wants to review it):

https://trac.sagemath.org/ticket/23669