#28631 closed enhancement (fixed)
Implement polynomial factorization over universal cyclotomic field
Reported by: | soehms | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.0 |
Component: | number fields | Keywords: | universal cyclotomic field, factorization |
Cc: | tscrim | Merged in: | |
Authors: | Sebastian Oehms | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | a3c9a81 (Commits, GitHub, GitLab) | Commit: | |
Dependencies: | Stopgaps: |
Description
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
Change History (7)
comment:1 Changed 2 years ago by
- Branch set to u/soehms/factorization_universal_cycl_field_28631
comment:2 Changed 2 years ago by
- Commit set to a3c9a81a7ae393a66002153e4303b253c0eec478
- Status changed from new to needs_review
comment:3 Changed 2 years ago by
- Reviewers set to Travis Scrimshaw
- Status changed from needs_review to positive_review
LGTM.
comment:4 Changed 2 years ago by
Thanks!
comment:5 Changed 2 years ago by
- Branch changed from u/soehms/factorization_universal_cycl_field_28631 to a3c9a81a7ae393a66002153e4303b253c0eec478
- Resolution set to fixed
- Status changed from positive_review to closed
comment:6 follow-up: ↓ 7 Changed 2 years ago by
- Commit a3c9a81a7ae393a66002153e4303b253c0eec478 deleted
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.
comment:7 in reply to: ↑ 6 Changed 2 years ago by
Replying to vdelecroix:
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.
I add an implementation of
_factor_univariate_polynomial
.New commits:
28631: inital version