segfault in division_points and factoring torsion_polynomial

[ncalexan]

John Cremona reports:

In 4.0.alpha0, this causes a segmentation fault:

----------------------------------------------------------------------
| Sage Version 4.0.alpha0, Release Date: 2009-05-15                  |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: K.<a>=NumberField(x^2-x+22)
sage: w=-13*a-14
sage: E=EllipticCurve([0,0,0,0,-1728*w])
sage: P1 = E.lift_x(-3*a-66)
sage: P2 = E.lift_x((-21*a-93)/4)
sage: P2.division_points(19)

It works fine to do

sage: g = P2.division_points(19, poly_only=True)

which defines a polynomial of degree 361 over Q(sqrt(-87)), but then
g.roots() goes Boom.

ncalexan verified this on Mac OS X; it looks like the crash is in an NTL function:

(gdb) bt
#0  0x01293247 in modii ()
#1  0x014278bc in FpX_red ()

CC: @JohnCremona

Component: elliptic curves

Keywords: segfault division points torsion polynomial

Issue created by migration from https://trac.sagemath.org/ticket/6113

[JohnCremona]

comment:1

Nick, do you know what the roots function is actually doing in this case (univariate poly over a number field)? I think it is calling factor(), but NTL has no support for polynomials over number fields so I thought it must be calling pari after that.

[sagetrac-stankewicz]

comment:2

Replying to @JohnCremona:

Nick, do you know what the roots function is actually doing in this case (univariate poly over a number field)? I think it is calling factor(), but NTL has no support for polynomials over number fields so I thought it must be calling pari after that.

I recently ran into a similar problem trying to factor over the field generated by the hilbert class polynomial over QQ. For small degree (< 50 or so) it's okay but for larger degree polynomials it gives a segmentation fault with PARI. If there's a way I can help here and get a patch up for this I want to know about it!

[JohnCremona]

comment:3

If we can come up with an example which fails in gp then it would be easy to send a bug report to the pari developers. It is harder if we can only get the error using the pari library, since then they might want a C program in the report. I think (quite reasonably) that the pari developers cannot be expected to debug things which can only be demonstrated in a Sage run -- even if the use of pari in Sage has increased the number of pari users worldwide by a lot!

[sagetrac-stankewicz]

comment:4

Replying to @JohnCremona:

If we can come up with an example which fails in gp then it would be easy to send a bug report to the pari developers. It is harder if we can only get the error using the pari library, since then they might want a C program in the report. I think (quite reasonably) that the pari developers cannot be expected to debug things which can only be demonstrated in a Sage run -- even if the use of pari in Sage has increased the number of pari users worldwide by a lot!

Well, I ran it on gp and it worked just fine. The results are included in the text file I've attached along with the same example failing in sage. When I -gdb it I get pointed to /usr/local/sage/local/LIB/libpari-gmp.so.2

That in addition to the fact that the code for factoring a univariate polynomial over a number field appears to essentially consist of "make PARI do it" is why it appeared that PARI was causing the SegFault.

[sagetrac-stankewicz]

Attachment: ProblematicPari.txt

A run of identical jobs, one in gp which succeeds and one in sage which results in a SegFault

[sagetrac-stankewicz]

comment:5

Attachment: nffactorsegfault.txt

Replying to @sagetrac-stankewicz:

Ah ha!. The problem is nonexistent with factornf, but that uses a different algorithm than nffactor, which is the pari command that sage uses for factoring. This is indeed a problem with Pari and will be reported.

Would it be possible to call factornf through gp and pull the factorization back to sage?

[sagetrac-stankewicz]

comment:6

http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=979

At the next upgrade of PARI this problem should be fixed(it's already fixed in the unstable version).

[JohnCremona]

comment:9

This probably has the same cause as #7097: see the comments there. I am going to check if the patch I put up there works here too.

[JohnCremona]

comment:10

Replying to @JohnCremona:

This probably has the same cause as #7097: see the comments there. I am going to check if the patch I put up there works here too.

It does not...

[JohnCremona]

comment:11

In 4.6.alpha1:

sage: K.<a>=NumberField(x^2-x+22)
sage: sage: w=-13*a-14
sage: sage: E=EllipticCurve([0,0,0,0,-1728*w])
sage: sage: P1 = E.lift_x(-3*a-66)
sage: sage: P2 = E.lift_x((-21*a-93)/4)
sage: sage: P2.division_points(19)
[]
sage: g = P2.division_points(19, poly_only=True)
sage: g.roots()
[]

so this can be closed as fixed.