Finding
-roots for polynomials over
, with`F` is a (finite) field, as used in the Guruswami-Sudan decoding.¶
This module contains functions for finding two types of roots in a
polynomial over
, where
is a field. Note that if
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
.
Given a , the first type of root are actual
roots,
i.e. polynomials
such that
.
The second type of root are modular roots: given and a
precision
, then we find all
such that
. Since this set is infinite, we return a succinct description
of all such polynomials: this is given as pairs
such that
is a modular root of
for any
.
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
where
is a field.
If
precision = None
then actual roots will be found, i.e. allsuch that
. This will be returned as a list of
elements.
If
precision = d
for some integerd
, then allsuch that
will be returned. This set is infinite, and so it will be returned as a list of pairs in
, where
denotes that
for any
.
If
maxd
is given, then find onlywith
. In case
setting
means to only find the roots up to precision
, i.e.
in the above; otherwise, this will be naturally bounded at
.
INPUT:
Q
– a bivariate polynomial, represented either over,
or
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
, 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)]