Finding F[x]-roots for polynomials over F[x][y], with`F` is a (finite) field, as used in the Guruswami-Sudan decoding.

This module contains functions for finding two types of F[x] roots in a polynomial over F[x][y], where F is a field. Note that if F is an infinite field, then these functions should work, but no measures are taken to limit coefficient growth. The functions also assume the existence of a root finding procedure in F[x].

Given a Q(x,y) \in F[x,y], the first type of root are actual F[x] roots, i.e. polynomials f(x) \in F[x] such that Q(x, f(x)) = 0.

The second type of root are modular roots: given Q(x,y) \in F[x,y] and a precision d \in \ZZ_+, then we find all f(x) \in F[x] such that Q(x, f(x))
\equiv 0 \mod x^d. Since this set is infinite, we return a succinct description of all such polynomials: this is given as pairs (f(x), h) such that f(x) +
g(x)x^h is a modular root of Q for any g \in F[x].

AUTHORS:

  • Johan S. R. Nielsen, original implementation (see [Nielsen] for details)
  • David Lucas, ported the original implementation in Sage
sage.coding.guruswami_sudan.rootfinding.rootfind_roth_ruckenstein(Q, maxd=None, precision=None)

Returns the list of roots of a bivariate polynomial Q.

Uses the Roth-Ruckenstein algorithm to find roots or modular roots of a Q
\in \mathbb{F}[x][y] where \mathbb{F} is a field.

If precision = None then actual roots will be found, i.e. all f \in
\mathbb{F}[x] such that Q(f) = 0. This will be returned as a list of \mathbb{F}[x] elements.

If precision = d for some integer d, then all f \in \mathbb{F}[x] such that Q(f) \equiv 0 \mod x^d will be returned. This set is infinite, and so it will be returned as a list of pairs in \mathbb{F}[x] \times
\mathbb{Z}_+, where (f, h) denotes that Q(f + x^h g) \equiv 0 \mod x^d for any g \in \mathbb{F}[x].

If maxd is given, then find only f with deg f \leq maxd. In case precision=d setting maxd means to only find the roots up to precision maxd, i.e. h \leq maxd in the above; otherwise, this will be naturally bounded at precision-1.

INPUT:

  • Q – a bivariate polynomial, represented either over F[x,y], F[x][y] or F[x] list.
  • maxd – (default: None) an non-negative integer degree bound, as defined above.
  • precision – (default: None) an integer, as defined above.

EXAMPLES:

sage: from sage.coding.guruswami_sudan.rootfinding import rootfind_roth_ruckenstein
sage: F = GF(17)
sage: Px.<x> = F[]
sage: Py.<y> = Px[]
sage: Q = (y - (x**2 + x + 1)) * (y**2 - x + 1) * (y - (x**3 + 4*x + 16))
sage: roots = rootfind_roth_ruckenstein(Q); set(roots)
{x^2 + x + 1, x^3 + 4*x + 16}
sage: Q(roots[0])
0
sage: set(rootfind_roth_ruckenstein(Q, maxd = 2))
{x^2 + x + 1}
sage: modroots = rootfind_roth_ruckenstein(Q, precision = 3); set(modroots)
{(4*x + 16, 3), (x^2 + x + 1, 3), (8*x^2 + 15*x + 4, 3), (9*x^2 + 2*x + 13, 3)}
sage: (f,h) = modroots[0]
sage: Q(f + x^h * Px.random_element()) % x^3
0
sage: modroots2 = rootfind_roth_ruckenstein(Q, maxd=1, precision = 3); set(modroots2)
{(x + 1, 2), (2*x + 13, 2), (4*x + 16, 2), (15*x + 4, 2)}

TESTS:

Test that if Q = 0, then the appropriate response is given

sage: F = GF(17) sage: R.<x,y> = F[] sage: rootfind_roth_ruckenstein(R.zero()) ValueError(‘The zero polynomial has infinitely many roots.’,) sage: rootfind_roth_ruckenstein(R.zero(), precision=1) [(0, 0)]