Sage cannot factor polynomials over number fields with unfactorable discriminant

[jdemeyer]

Let K be a number field with a discriminant which cannot be factored. Let f be a polynomial in K[x]. Then Sage is unable to factor f because it calls PARI's nfinit() on K:

sage: p = next_prime(10^50); q = next_prime(10^51)
sage: K = QuadraticField(p*q)
sage: x = polygen(K); factor(x^2+1)
[... takes a very long time ...]

The solution is to call nfinit() with the defining polynomial when the discriminant cannot be factored. If that fails, fall back to factornf().

See also #10910.

Apply 11890_rebased.patch​, 11890_try_nffactor.patch​ and 11890_reviewer.patch​.

[lftabera]

Jeroen,

This ticket is a duplicate of #10910

In that ticket I presented another approach. I still use nffactor but do not use nfinit UNLESS nfinit has already been computed and cached. A couple of comments regarding both approaches:

• Now we do not need nfinit for nffactor. So we can use either nffactor or factornf at will.
• In most cases nffactor will be faster than factornf (I should give numbers to sustain that though).
• My patch also work for non-integral generators.
• But my patch fails in your example with a PariError? exception: precision too low.

I have to investigate this error. It might be a Pari bug or there are instances where we really need factornf.

[jdemeyer]

Replying to lftabera:

• But my patch fails in your example with a PariError? exception: precision too low.

This is exactly the reason why I am using factornf instead of nffactor: nffactor somehow computes a partial nfinit structure which does some floating-point stuff. Apparently, the floating-point precision is not sufficient in the example.

[lftabera]

Then, we need to be smarter. My experience tells that when nffactor is slower than factornf is for a small relative amount while the other way around is false.

Doing a couple of examples suggest that the PariError? appears quite soon.

sage: K=NumberField(x^20+ZZ[x].random_element(19,10**20),'a')[x]
sage: f=K.random_element(50)
sage: g=K.random_element(50)
sage: F=f*g

In the above exameple, with my patch, the PariError? appears after 6 s. I have not yet computed the factorization of the polynomial with factornf but I claim that it will be quite hard to compute. Pari will use Trager's trick, that means that it will perform gcd's of polynomials in K. And Pari is not very good at it, cf. #8558

We need to figure out which method use, one option is the following:

• If nfinit structure is already known, use (or try) nfffactor(nfinit,f)
• If nfinit is not computed, try nffactor
• If the above fails, use factornf.

Another alternative is to use one algorithm or the other depending on the discriminant of the field if that is the relevant data for the PariError?.

We may even consider implementing our own Trager's ticket (but that should be in another ticket, after #8558 is merged).

I am not yet sure what is the best way to proceed. I also feel that there should be a way for allowing the user to override the algorithm to use. But factor does not allow optional arguments and I do not want to mess the rest of univariate rings.

[jdemeyer]

Replying to lftabera:

We need to figure out which method use, one option is the following:

• If nfinit structure is already known, use (or try) nfffactor(nfinit,f)
• If nfinit is not computed, try nffactor
• If the above fails, use factornf.

Agreed. Except that we really should do nfinit() if the discriminant is easy.

I am not yet sure what is the best way to proceed. I also feel that there should be a way for allowing the user to override the algorithm to use.

Why? If one algorithm is clearly better than another, why complicate things with extra arguments?

[lftabera]

The solution here to test the use of nffactor is more elegant than in #10910 and with these patches there are no known failing cases. All doctest pases on sage-4.7.2-alpha3 + #11130 + #11891

I give a positive review to Jeroen's patches but I add a patch that needs review with a couple of things:

-On a complicated case we show that the discriminant is not fully factored by trial division.

-The second example is a test case that shows that we really need the new version of Pari in #11130 this case will fail with older versions of Pari (See Pari bug pari bug #1207)

[jdemeyer]

Reviewer patch looks good to me. Thanks!

For those interested: the PARI bug is ​http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1207

[jdemeyer]

Trivial rebase.

[jdemeyer]

Milestone sage-4.7.3 deleted