Opened 3 years ago

Closed 3 years ago

# problem factoring polynomial over number field

Reported by: Owned by: wuthrich minor sage-duplicate/invalid/wontfix factorization pari, polynomial, factorization cremona, jdemeyer Reported upstream. No feedback yet.

```sage: E = EllipticCurve([1,0])
sage: K.<t> = E.division_field(5)
sage: EK = E.base_extend(K)
sage: EK.isogenies_prime_degree(5)
```

goes boom and ends with

```PariError: inconsistent concatenation t_VEC (2 elts) , t_COL (2 elts)
```

with the curve `E = EllipticCurve("11a1")` it works fine.

### comment:1 Changed 3 years ago by cremona

Tracking this down, it is not in the isogeny code as such:

```sage: E = EllipticCurve([1,0])
sage: K.<t> = E.division_field(5)
sage: EK = E.base_extend(K)
sage: E2 = EK.short_weierstrass_model()
sage: EK.isomorphism_to(E2)
```

which I wrote even longer ago (10 years?). Something has gone wrong wit hthe interface to pari's factorization of polynomials over number fields.

### comment:2 Changed 3 years ago by cremona

Here is code which triggers the problem which has nothing to do with elliptic curves:

```x = polygen(QQ)
pol = x^32 - 40*x^31 + 2200*x^30 - 70000*x^29 + 1926760*x^28 - 47410000*x^27 + 893166000*x^26 - 15151540000*x^25 + 218980686600*x^24 - 2222863736000*x^23 + 16167594760000*x^22 - 35393484200000*x^21 - 1983124979264000*x^20 + 31818541845880000*x^19 + 32676134745200000*x^18 - 887920368940000000*x^17 - 20567097546680290000*x^16 + 428473384974975200000*x^15 - 2816072502532216000000*x^14 - 7788706298586140000000*x^13 + 252808056677292000000000*x^12 - 1002263969671718500000000*x^11 + 2230707722334140000000000*x^10 - 54420521465975000000000000*x^9 + 523500114521163406250000000*x^8 - 973463314441488125000000000*x^7 + 2944910228721053125000000000*x^6 - 25691035501284500000000000000*x^5 + 9541139003641484375000000000*x^4 + 203162239445609375000000000000*x^3 + 791581188305121093750000000000*x^2 + 187244754882460937500000000000*x + 215978078004907226562500000000
K.<a> = NumberField(pol)
y = polygen(K, 'y')
(y^4-1).roots()
```

### comment:3 Changed 3 years ago by cremona

Note that

```(y^2+1).roots()
```

returns two roots with no problem.

### comment:4 Changed 3 years ago by wuthrich

• Component changed from elliptic curves to factorization
• Description modified (diff)
• Keywords pari polynomial factorization added; isogeny removed
• Report Upstream changed from N/A to Not yet reported upstream; Will do shortly.
• Summary changed from fails to create isogenies on a cm curve over a number field to problem factoring polynomial over number field

Thanks for chasing. I went a bit further and found that this is likely a bug in pari:

```? f = y^32 - 40*y^31 + 2200*y^30 - 70000*y^29 + 1926760*y^28 - 47410000*y^27 + 893166000*y^26 - 15151540000*y^25 + 218980686600*y^24 - 2222863736000*y^23 + 16167594760000*y^22 - 35393484200000*y^21 - 1983124979264000*y^20 + 31818541845880000*y^19 + 32676134745200000*y^18 - 887920368940000000*y^17 - 20567097546680290000*y^16 + 428473384974975200000*y^15 - 2816072502532216000000*y^14 - 7788706298586140000000*y^13 + 252808056677292000000000*y^12 - 1002263969671718500000000*y^11 + 2230707722334140000000000*y^10 - 54420521465975000000000000*y^9 + 523500114521163406250000000*y^8 - 973463314441488125000000000*y^7 + 2944910228721053125000000000*y^6 - 25691035501284500000000000000*y^5 + 9541139003641484375000000000*y^4 + 203162239445609375000000000000*y^3 + 791581188305121093750000000000*y^2 + 187244754882460937500000000000*y + 215978078004907226562500000000
%1 = y^32 - 40*y^31 + 2200*y^30 - 70000*y^29 + 1926760*y^28 - 47410000*y^27 + 893166000*y^26 - 15151540000*y^25 + 218980686600*y^24 - 2222863736000*y^23 + 16167594760000*y^22 - 35393484200000*y^21 - 1983124979264000*y^20 + 31818541845880000*y^19 + 32676134745200000*y^18 - 887920368940000000*y^17 - 20567097546680290000*y^16 + 428473384974975200000*y^15 - 2816072502532216000000*y^14 - 7788706298586140000000*y^13 + 252808056677292000000000*y^12 - 1002263969671718500000000*y^11 + 2230707722334140000000000*y^10 - 54420521465975000000000000*y^9 + 523500114521163406250000000*y^8 - 973463314441488125000000000*y^7 + 2944910228721053125000000000*y^6 - 25691035501284500000000000000*y^5 + 9541139003641484375000000000*y^4 + 203162239445609375000000000000*y^3 + 791581188305121093750000000000*y^2 + 187244754882460937500000000000*y + 215978078004907226562500000000
? g = x^2-1
%2 = x^2 - 1
? nffactor(f,g)
%3 =
[x - 1 1]

[x + 1 1]

? g = x^4-1
%4 = x^4 - 1
? nffactor(f,g)
***   at top-level: nffactor(f,g)
***                 ^-------------
*** nffactor: inconsistent concatenation t_VEC (2 elts) , t_COL (2 elts).
```

is the cause of this.

### comment:5 Changed 3 years ago by cremona

• Authors set to jdemeyer

### comment:6 Changed 3 years ago by cremona

• Authors jdemeyer deleted

### comment:7 Changed 3 years ago by wuthrich

• Report Upstream changed from Not yet reported upstream; Will do shortly. to Reported upstream. No feedback yet.

### comment:8 follow-up: ↓ 9 Changed 3 years ago by jdemeyer

• Milestone changed from sage-8.3 to sage-duplicate/invalid/wontfix
• Resolution set to duplicate
• Status changed from new to closed

Fixed by #25567

### comment:9 in reply to: ↑ 8 Changed 3 years ago by cremona

Fixed by #25567

I believe you, despite #25567's current status "needs work".

### comment:10 Changed 3 years ago by jdemeyer

To clarify: the updated PARI/GP on #25567 builds and I checked (within GP, not Sage) that the problem is fixed.

### comment:11 Changed 3 years ago by cremona

Thanks.

Note: See TracTickets for help on using tickets.