Implement polynomial factorization over universal cyclotomic field

[soehms]

Indeed, that hasn't been done so far:

sage: UCF = UniversalCyclotomicField()
sage: P.<x> = UCF[]
sage: p = x**5-1
sage: p.roots()
Traceback (most recent call last):
...
NotImplementedError: root finding for this polynomial not implemented

CC: @tscrim

Component: number fields

Keywords: universal cyclotomic field, factorization

Author: Sebastian Oehms

Branch: a3c9a81

Reviewer: Travis Scrimshaw

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

[soehms]

Branch: u/soehms/factorization_universal_cycl_field_28631

[soehms]

comment:2

I add an implementation of _factor_univariate_polynomial.

---

New commits:

a3c9a81

28631: inital version

[soehms]

Commit: a3c9a81

[tscrim]

comment:3

LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[soehms]

comment:4

Thanks!

[vbraun]

Changed branch from u/soehms/factorization_universal_cycl_field_28631 to a3c9a81

[videlec]

comment:6

What is your code supposed to do!?

sage: x = polygen(UCF)
sage: (x**2 - 3).factor()
x^2 - 3

But there is a square root

sage: UCF(3).sqrt()
E(12)^7 - E(12)^11
sage: UCF(3).sqrt()**2
3

I propose to simply revert all of what this ticket did in #28659.

Note that the sqrt used above is implemented for integers only since this is more or less trivial. But it fails for general UCF elements. Implementing more is definitely welcome

• factorization of rational polynomials over UCF
• square root for any UCF element
  (these are non-trivial tasks)

Please be more careful with your code submissions and reviews. Code discussion is very welcome on sage-devel and sage-nt.

[videlec]

Changed commit from a3c9a81 to none

[soehms]

comment:7

Replying to @videlec:

Please be more careful with your code submissions and reviews. Code discussion is very welcome on sage-devel and sage-nt.

I'm sorry for that, Vincent, and will be more careful in future! I didn't become aware, that there was a serious reason that this was not implemented.

On the other hand, I think there are reasons, that Sage should be able to find roots of unity over the UCF. At least the following two:

1. Code which needs a root of unity over an unspecified ring should not need an separate implementation for UCF.

2. Sage is not only a tool for experts, but satisfies educational requirements, as well. But, what I've displayed in the ticket-description would at least cause irritations.

My code can be easily improved (adding two lines), in order to be not vastly any more. I will explain this in the new ticket.