Make Roth-Ruckenstein algorithm a method of polynomials

[bgrenet]

The coding part of Sage (see #18846) contains Roth-Ruckenstein algorithm to compute the roots of a polynomial Q(y) with coefficients in F[x] (where F is a finite field). The purpose of this ticket is to move the implementation to make this algorithm a method of polynomials.

Toward this end, we also define a generic implementation for roots of univariate polynomials over univariate polynomial rings, that goes through their factorization. And this requires to implement the factorization for these "recursive" polynomial rings: Currently, the algorithm consists in flattening the recursive polynomial ring and use methods for multivariate polynomial rings.

CC: @johanrosenkilde @sagetrac-dlucas

Component: commutative algebra

Keywords: sd75, polynomial, root finding

Author: Bruno Grenet

Branch/Commit: 01378dc

Reviewer: Turku Ozlum Celik

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

[bgrenet]

Branch: u/bruno/y-root_finding

[bgrenet]

comment:2

There remains one step to perform: Remove Roth-Ruckenstein from coding and branch the new implementation.

---

New commits:

ced566c	Basic infrastructure
e19ef2a	Add ROth Ruckenstein algorithm

[bgrenet]

Commit: e19ef2a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

60972c5	Remove Roth-Ruckenstein alg from coding
4c85e83	Refine default degree bound

[sagetrac-git]

Changed commit from e19ef2a to 4c85e83

[fchapoton]

comment:5

doc, does not build, see patchbot report:

+[dochtml] Warning: Could not import sage.coding.guruswami_sudan.rootfinding No module named rootfinding

and incomplete coverage:
+Decreased doctests in coding/guruswami_sudan/gs_decoder.py: from 17 / 17 = 100% to 17 / 18 = 94%

[bgrenet]

comment:6

Replying to @fchapoton:

doc, does not build, see patchbot report:

+[dochtml] Warning: Could not import sage.coding.guruswami_sudan.rootfinding No module named rootfinding

and incomplete coverage:
+Decreased doctests in coding/guruswami_sudan/gs_decoder.py: from 17 / 17 = 100% to 17 / 18 = 94%

Argh, I did not check to documentation well enough! I'm working on it.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3323e3b	Remove rootfinding from doc
458ffc2	Use polys instead of lists in roth-ruckenstein

[sagetrac-git]

Changed commit from 4c85e83 to 458ffc2

[sagetrac-git]

Changed commit from 458ffc2 to 01378dc

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

01378dc

Doctest roth_ruckenstein_root_finder

[sagetrac-turkuozlum]

Reviewer: Turku Ozlum Celik

[sagetrac-turkuozlum]

comment:10

I checked the ticket by following the checklist and the algorithm by considering the paper of Roth-Ruckenstein. It seems OK.

[vbraun]

Changed branch from u/bruno/y-root_finding to 01378dc