[with patch, positive review] multivariate factoring over some rings gives incorrect results

[dmharvey]

This example is from Genya Zaytman:

sage: version()
'SAGE Version sage-2.11, Release Date: 2008-03-30'
sage: q = 1073741789
sage: T.<aa, bb> = PolynomialRing(GF(q))
sage: f = aa^2 + 12124343*bb*aa + 32434598*bb^2; f
aa^2 + 12124343*aa*bb + 32434598*bb^2
sage: f.factor()
(32434598) * (16373350*aa^2 + 437239695*aa*bb + bb^2)
sage: g = (32434598) * (16373350*aa^2 + 437239695*aa*bb + bb^2); g
aa^2 - 49344938*aa*bb + 32434598*bb^2
sage: f == g
False

Michael Abshoff reports that this is a bug in Singular itself.

See also

 http://groups.google.com/group/sage-devel/browse_thread/thread/bb040b4580b44184

[malb]

We got word from the Singular team: My rough translation follows:

Our analysis revealed that the cause is that the characteristic is too big: despite the fact that the Singular kernel can compute with characteristics up to 2³¹ since 3-0-0, Factory has a limit of p <2²⁹ (31 bit for signed int, 2 bit as "Type indicator"). Unfortunately this wasn't tested, since the former limit for Singular was much lower (2¹⁵).

[dmharvey]

Replying to malb:

We got word from the Singular team: My rough translation follows:

Our analysis revealed that the cause is that the characteristic is too big: despite the fact that the Singular kernel can compute with characteristics up to 2³¹ since 3-0-0, Factory has a limit of p <2²⁹ (31 bit for signed int, 2 bit as "Type indicator"). Unfortunately this wasn't tested, since the former limit for Singular was much lower (2¹⁵).

Clarification: is "Factory" something in Sage, or something in Singular? i.e. is this still a bug (or possibly documentation bug) at their end, or do we just need to stop using Singular when the characteristic gets this big?

Another question: is it really always 29 bits, or is it going to be 61 bits on a 64-bit machine?

[mabshoff]

Replying to dmharvey:

Clarification: is "Factory" something in Sage, or something in Singular? i.e. is this still a bug (or possibly documentation bug) at their end, or do we just need to stop using Singular when the characteristic gets this big?

Factory is a library that is part of Singular and used to do factorization. Other projects like M2 also use it. As you write we need to check the characteristic before passing the polynomial to factory nee Singular and otherwise throw an exception.

Another question: is it really always 29 bits, or is it going to be 61 bits on a 64-bit machine?

It seems to be always 29 bits. I tested on sage.math with a 64 bit Singular.

Cheers,

Michael

[malb]

Clarification: is "Factory" something in Sage, or something in Singular? i.e. is this still a bug (or possibly documentation bug) at their end, or do we just need to stop using Singular when the characteristic gets this big?

"Factory" is a Singular thing and we need to raise an Exception if the user attempts to factor of fields that large. I'll provide a patch later.

Another question: is it really always 29 bits, or is it going to be 61 bits on a 64-bit machine?

The word is 29 bits, but I'll check later, too.

[dmharvey]

Replying to malb:

"Factory" is a Singular thing and we need to raise an Exception if the user attempts to factor of fields that large. I'll provide a patch later.

Ummm.... do we have any other way to provide the factorisation? For example, Genya (who reported this bug) actually wanted to factor the polynomial :-) I agree that an exception is better than an incorrect result, but it would be nice if.....

[malb]

The attached patch raises a NotImplementedError if a factorisation with characteristic > 2²⁹ is attempted.

[mabshoff]

Patch looks good to me. It adds the original bug report as a doctest. Positive review.

Cheers,

Michael

[mabshoff]

Merged in Sage 3.0.alpha2