Guruswami-Sudan decoder for (Generalized) Reed-Solomon codes#

REFERENCES:

AUTHORS:

Johan S. R. Nielsen, original implementation (see [Nie] for details)
David Lucas, ported the original implementation in Sage

class sage.coding.guruswami_sudan.gs_decoder.GRSGuruswamiSudanDecoder(code, tau=None, parameters=None, interpolation_alg=None, root_finder=None)[source]#

Bases: Decoder

The Guruswami-Sudan list-decoding algorithm for decoding Generalized Reed-Solomon codes.

The Guruswami-Sudan algorithm is a polynomial time algorithm to decode beyond half the minimum distance of the code. It can decode up to the Johnson radius which is \(n - \sqrt(n(n-d))\), where \(n, d\) is the length, respectively minimum distance of the RS code. See [GS1999] for more details. It is a list-decoder meaning that it returns a list of all closest codewords or their corresponding message polynomials. Note that the output of the decode_to_code and decode_to_message methods are therefore lists.

The algorithm has two free parameters, the list size and the multiplicity, and these determine how many errors the method will correct: generally, higher decoding radius requires larger values of these parameters. To decode all the way to the Johnson radius, one generally needs values in the order of \(O(n^2)\), while decoding just one error less requires just \(O(n)\).

This class has static methods for computing choices of parameters given the decoding radius or vice versa.

The Guruswami-Sudan consists of two computationally intensive steps: Interpolation and Root finding, either of which can be completed in multiple ways. This implementation allows choosing the sub-algorithms among currently implemented possibilities, or supplying your own.

INPUT:

code – A code associated to this decoder.
tau – (default: None) an integer, the number of errors one wants the Guruswami-Sudan algorithm to correct.
parameters – (default: None) a pair of integers, where:
- the first integer is the multiplicity parameter, and
- the second integer is the list size parameter.
interpolation_alg – (default: None) the interpolation algorithm that will be used. The following possibilities are currently available:
- "LinearAlgebra" – uses a linear system solver.
- "LeeOSullivan" – uses Lee O’Sullivan method based on row reduction of a matrix
- None – one of the above will be chosen based on the size of the code and the parameters.
You can also supply your own function to perform the interpolation. See NOTE section for details on the signature of this function.
root_finder – (default: None) the rootfinding algorithm that will be used. The following possibilities are currently available:
- "Alekhnovich" – uses Alekhnovich’s algorithm.
- "RothRuckenstein" – uses Roth-Ruckenstein algorithm.
- None – one of the above will be chosen based on the size of the code and the parameters.
You can also supply your own function to perform the interpolation. See NOTE section for details on the signature of this function.

Note

One has to provide either tau or parameters. If neither are given, an exception will be raised.

If one provides a function as root_finder, its signature has to be: my_rootfinder(Q, maxd=default_value, precision=default_value). \(Q\) will be given as an element of \(F[x][y]\). The function must return the roots as a list of polynomials over a univariate polynomial ring. See roth_ruckenstein_root_finder() for an example.

If one provides a function as interpolation_alg, its signature has to be: my_inter(interpolation_points, tau, s_and_l, wy). See sage.coding.guruswami_sudan.interpolation.gs_interpolation_linalg() for an example.

EXAMPLES:

Sage

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = codes.decoders.GRSGuruswamiSudanDecoder(C, tau=97); D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251)
 decoding 97 errors with parameters (1, 2)

Python

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(251)).list()[:Integer(250)], Integer(70))
>>> D = codes.decoders.GRSGuruswamiSudanDecoder(C, tau=Integer(97)); D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251)
 decoding 97 errors with parameters (1, 2)

One can specify multiplicity and list size instead of tau:

Sage

sage: D = codes.decoders.GRSGuruswamiSudanDecoder(C, parameters=(1,2)); D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251)
 decoding 97 errors with parameters (1, 2)

Python

>>> from sage.all import *
>>> D = codes.decoders.GRSGuruswamiSudanDecoder(C, parameters=(Integer(1),Integer(2))); D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251)
 decoding 97 errors with parameters (1, 2)

One can pass a method as root_finder (works also for interpolation_alg):

Sage

sage: from sage.coding.guruswami_sudan.gs_decoder import roth_ruckenstein_root_finder
sage: rf = roth_ruckenstein_root_finder
sage: D = codes.decoders.GRSGuruswamiSudanDecoder(C, parameters=(1,2),
....:                                             root_finder=rf);  D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251)
 decoding 97 errors with parameters (1, 2)

Python

>>> from sage.all import *
>>> from sage.coding.guruswami_sudan.gs_decoder import roth_ruckenstein_root_finder
>>> rf = roth_ruckenstein_root_finder
>>> D = codes.decoders.GRSGuruswamiSudanDecoder(C, parameters=(Integer(1),Integer(2)),
...                                             root_finder=rf);  D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251)
 decoding 97 errors with parameters (1, 2)

If one wants to use the native Sage algorithms for the root finding step, one can directly pass the string given in the Input block of this class. This works for interpolation_alg as well:

Sage

sage: D = codes.decoders.GRSGuruswamiSudanDecoder(C, parameters=(1,2),
....:                                             root_finder="RothRuckenstein"); D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251)
 decoding 97 errors with parameters (1, 2)

Python

>>> from sage.all import *
>>> D = codes.decoders.GRSGuruswamiSudanDecoder(C, parameters=(Integer(1),Integer(2)),
...                                             root_finder="RothRuckenstein"); D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251)
 decoding 97 errors with parameters (1, 2)

Actually, we can construct the decoder from C directly:

Sage

sage: D = C.decoder("GuruswamiSudan", tau=97); D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251)
 decoding 97 errors with parameters (1, 2)

Python

>>> from sage.all import *
>>> D = C.decoder("GuruswamiSudan", tau=Integer(97)); D
Guruswami-Sudan decoder for [250, 70, 181] Reed-Solomon Code over GF(251)
 decoding 97 errors with parameters (1, 2)

decode_to_code(r)[source]#

Return the list of all codeword within radius self.decoding_radius() of the received word \(r\).

INPUT:

r – a received word, i.e. a vector in \(F^n\) where \(F\) and \(n\) are the base field respectively length of self.code().

EXAMPLES:

Sage

sage: GSD = codes.decoders.GRSGuruswamiSudanDecoder
sage: C = codes.GeneralizedReedSolomonCode(GF(17).list()[:15], 6)
sage: D = GSD(C, tau=5)
sage: c = vector(GF(17), [3,13,12,0,0,7,5,1,8,11,1,9,4,12,14])
sage: c in C
True
sage: r = vector(GF(17), [3,13,12,0,0,7,5,1,8,11,15,12,14,7,10])
sage: r in C
False
sage: codewords = D.decode_to_code(r)
sage: len(codewords)
2
sage: c in codewords
True

Python

>>> from sage.all import *
>>> GSD = codes.decoders.GRSGuruswamiSudanDecoder
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(17)).list()[:Integer(15)], Integer(6))
>>> D = GSD(C, tau=Integer(5))
>>> c = vector(GF(Integer(17)), [Integer(3),Integer(13),Integer(12),Integer(0),Integer(0),Integer(7),Integer(5),Integer(1),Integer(8),Integer(11),Integer(1),Integer(9),Integer(4),Integer(12),Integer(14)])
>>> c in C
True
>>> r = vector(GF(Integer(17)), [Integer(3),Integer(13),Integer(12),Integer(0),Integer(0),Integer(7),Integer(5),Integer(1),Integer(8),Integer(11),Integer(15),Integer(12),Integer(14),Integer(7),Integer(10)])
>>> r in C
False
>>> codewords = D.decode_to_code(r)
>>> len(codewords)
2
>>> c in codewords
True

decode_to_message(r)[source]#

Decode r to the list of polynomials whose encoding by self.code() is within Hamming distance self.decoding_radius() of r.

INPUT:

r – a received word, i.e. a vector in \(F^n\) where \(F\) and \(n\) are the base field respectively length of self.code().

EXAMPLES:

Sage

sage: GSD = codes.decoders.GRSGuruswamiSudanDecoder
sage: C = codes.GeneralizedReedSolomonCode(GF(17).list()[:15], 6)
sage: D = GSD(C, tau=5)
sage: F.<x> = GF(17)[]
sage: m = 13*x^4 + 7*x^3 + 10*x^2 + 14*x + 3
sage: c = D.connected_encoder().encode(m)
sage: r = vector(GF(17), [3,13,12,0,0,7,5,1,8,11,15,12,14,7,10])
sage: (c-r).hamming_weight()
5
sage: messages = D.decode_to_message(r)
sage: len(messages)
2
sage: m in messages
True

Python

>>> from sage.all import *
>>> GSD = codes.decoders.GRSGuruswamiSudanDecoder
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(17)).list()[:Integer(15)], Integer(6))
>>> D = GSD(C, tau=Integer(5))
>>> F = GF(Integer(17))['x']; (x,) = F._first_ngens(1)
>>> m = Integer(13)*x**Integer(4) + Integer(7)*x**Integer(3) + Integer(10)*x**Integer(2) + Integer(14)*x + Integer(3)
>>> c = D.connected_encoder().encode(m)
>>> r = vector(GF(Integer(17)), [Integer(3),Integer(13),Integer(12),Integer(0),Integer(0),Integer(7),Integer(5),Integer(1),Integer(8),Integer(11),Integer(15),Integer(12),Integer(14),Integer(7),Integer(10)])
>>> (c-r).hamming_weight()
5
>>> messages = D.decode_to_message(r)
>>> len(messages)
2
>>> m in messages
True

decoding_radius()[source]#

Return the maximal number of errors that self is able to correct.

EXAMPLES:

Sage

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau=97)
sage: D.decoding_radius()
97

Python

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(251)).list()[:Integer(250)], Integer(70))
>>> D = C.decoder("GuruswamiSudan", tau=Integer(97))
>>> D.decoding_radius()
97

An example where tau is not one of the inputs to the constructor:

Sage

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", parameters=(2,4))
sage: D.decoding_radius()
105

Python

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(251)).list()[:Integer(250)], Integer(70))
>>> D = C.decoder("GuruswamiSudan", parameters=(Integer(2),Integer(4)))
>>> D.decoding_radius()
105

static gs_satisfactory(tau, s, l, C=None, n_k=None)[source]#

Return whether input parameters satisfy the governing equation of Guruswami-Sudan.

See [Nie2013] page 49, definition 3.3 and proposition 3.4 for details.

INPUT:

tau – an integer, number of errors one expects Guruswami-Sudan algorithm to correct
s – an integer, multiplicity parameter of Guruswami-Sudan algorithm
l – an integer, list size parameter
C – (default: None) a GeneralizedReedSolomonCode
n_k – (default: None) a tuple of integers, respectively the length and the dimension of the GeneralizedReedSolomonCode

Note

One has to provide either C or (n, k). If none or both are given, an exception will be raised.

EXAMPLES:

Sage

sage: GSD = codes.decoders.GRSGuruswamiSudanDecoder
sage: tau, s, l = 97, 1, 2
sage: n, k = 250, 70
sage: GSD.gs_satisfactory(tau, s, l, n_k=(n, k))
True

Python

>>> from sage.all import *
>>> GSD = codes.decoders.GRSGuruswamiSudanDecoder
>>> tau, s, l = Integer(97), Integer(1), Integer(2)
>>> n, k = Integer(250), Integer(70)
>>> GSD.gs_satisfactory(tau, s, l, n_k=(n, k))
True

One can also pass a GRS code:

Sage

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: GSD.gs_satisfactory(tau, s, l, C=C)
True

Python

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(251)).list()[:Integer(250)], Integer(70))
>>> GSD.gs_satisfactory(tau, s, l, C=C)
True

Another example where s and l does not satisfy the equation:

Sage

sage: tau, s, l = 118, 47, 80
sage: GSD.gs_satisfactory(tau, s, l, n_k=(n, k))
False

Python

>>> from sage.all import *
>>> tau, s, l = Integer(118), Integer(47), Integer(80)
>>> GSD.gs_satisfactory(tau, s, l, n_k=(n, k))
False

If one provides both C and n_k an exception is returned:

Sage

sage: tau, s, l = 97, 1, 2
sage: n, k = 250, 70
sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: GSD.gs_satisfactory(tau, s, l, C=C, n_k=(n, k))
Traceback (most recent call last):
...
ValueError: Please provide only the code or its length and dimension

Python

>>> from sage.all import *
>>> tau, s, l = Integer(97), Integer(1), Integer(2)
>>> n, k = Integer(250), Integer(70)
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(251)).list()[:Integer(250)], Integer(70))
>>> GSD.gs_satisfactory(tau, s, l, C=C, n_k=(n, k))
Traceback (most recent call last):
...
ValueError: Please provide only the code or its length and dimension

Same if one provides none of these:

Sage

sage: GSD.gs_satisfactory(tau, s, l)
Traceback (most recent call last):
...
ValueError: Please provide either the code or its length and dimension

Python

>>> from sage.all import *
>>> GSD.gs_satisfactory(tau, s, l)
Traceback (most recent call last):
...
ValueError: Please provide either the code or its length and dimension

static guruswami_sudan_decoding_radius(C=None, n_k=None, l=None, s=None)[source]#

Return the maximal decoding radius of the Guruswami-Sudan decoder and the parameter choices needed for this.

If s is set but l is not it will return the best decoding radius using this s alongside with the required l. Vice versa for l. If both are set, it returns the decoding radius given this parameter choice.

INPUT:

C – (default: None) a GeneralizedReedSolomonCode
n_k – (default: None) a pair of integers, respectively the length and the dimension of the GeneralizedReedSolomonCode
s – (default: None) an integer, the multiplicity parameter of Guruswami-Sudan algorithm
l – (default: None) an integer, the list size parameter

Note

One has to provide either C or n_k. If none or both are given, an exception will be raised.

OUTPUT:

(tau, (s, l)) – where
- tau is the obtained decoding radius, and
- (s, l) are the multiplicity parameter and the list size parameter giving the radius

EXAMPLES:

Sage

sage: GSD = codes.decoders.GRSGuruswamiSudanDecoder
sage: n, k = 250, 70
sage: GSD.guruswami_sudan_decoding_radius(n_k=(n, k))
(118, (47, 89))

Python

>>> from sage.all import *
>>> GSD = codes.decoders.GRSGuruswamiSudanDecoder
>>> n, k = Integer(250), Integer(70)
>>> GSD.guruswami_sudan_decoding_radius(n_k=(n, k))
(118, (47, 89))

One parameter can be restricted at a time:

Sage

sage: n, k = 250, 70
sage: GSD.guruswami_sudan_decoding_radius(n_k=(n, k), s=3)
(109, (3, 5))
sage: GSD.guruswami_sudan_decoding_radius(n_k=(n, k), l=7)
(111, (4, 7))

Python

>>> from sage.all import *
>>> n, k = Integer(250), Integer(70)
>>> GSD.guruswami_sudan_decoding_radius(n_k=(n, k), s=Integer(3))
(109, (3, 5))
>>> GSD.guruswami_sudan_decoding_radius(n_k=(n, k), l=Integer(7))
(111, (4, 7))

The function can also just compute the decoding radius given the parameters:

Sage

sage: GSD.guruswami_sudan_decoding_radius(n_k=(n, k), s=2, l=6)
(92, (2, 6))

Python

>>> from sage.all import *
>>> GSD.guruswami_sudan_decoding_radius(n_k=(n, k), s=Integer(2), l=Integer(6))
(92, (2, 6))

interpolation_algorithm()[source]#

Return the interpolation algorithm that will be used.

Remember that its signature has to be: my_inter(interpolation_points, tau, s_and_l, wy). See sage.coding.guruswami_sudan.interpolation.gs_interpolation_linalg() for an example.

EXAMPLES:

Sage

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau=97)
sage: D.interpolation_algorithm()
<function gs_interpolation_lee_osullivan at 0x...>

Python

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(251)).list()[:Integer(250)], Integer(70))
>>> D = C.decoder("GuruswamiSudan", tau=Integer(97))
>>> D.interpolation_algorithm()
<function gs_interpolation_lee_osullivan at 0x...>

list_size()[source]#

Return the list size parameter of self.

EXAMPLES:

Sage

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau=97)
sage: D.list_size()
2

Python

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(251)).list()[:Integer(250)], Integer(70))
>>> D = C.decoder("GuruswamiSudan", tau=Integer(97))
>>> D.list_size()
2

multiplicity()[source]#

Return the multiplicity parameter of self.

EXAMPLES:

Sage

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau=97)
sage: D.multiplicity()
1

Python

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(251)).list()[:Integer(250)], Integer(70))
>>> D = C.decoder("GuruswamiSudan", tau=Integer(97))
>>> D.multiplicity()
1

parameters()[source]#

Return the multiplicity and list size parameters of self.

EXAMPLES:

Sage

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau=97)
sage: D.parameters()
(1, 2)

Python

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(251)).list()[:Integer(250)], Integer(70))
>>> D = C.decoder("GuruswamiSudan", tau=Integer(97))
>>> D.parameters()
(1, 2)

static parameters_given_tau(tau, C=None, n_k=None)[source]#

Return the smallest possible multiplicity and list size given the given parameters of the code and decoding radius.

INPUT:

tau – an integer, number of errors one wants the Guruswami-Sudan algorithm to correct
C – (default: None) a GeneralizedReedSolomonCode
n_k – (default: None) a pair of integers, respectively the length and the dimension of the GeneralizedReedSolomonCode

OUTPUT:

(s, l) – a pair of integers, where:
- s is the multiplicity parameter, and
- l is the list size parameter.

Note

One should to provide either C or (n, k). If neither or both are given, an exception will be raised.

EXAMPLES:

Sage

sage: GSD = codes.decoders.GRSGuruswamiSudanDecoder
sage: tau, n, k = 97, 250, 70
sage: GSD.parameters_given_tau(tau, n_k=(n, k))
(1, 2)

Python

>>> from sage.all import *
>>> GSD = codes.decoders.GRSGuruswamiSudanDecoder
>>> tau, n, k = Integer(97), Integer(250), Integer(70)
>>> GSD.parameters_given_tau(tau, n_k=(n, k))
(1, 2)

Another example with a bigger decoding radius:

Sage

sage: tau, n, k = 118, 250, 70
sage: GSD.parameters_given_tau(tau, n_k=(n, k))
(47, 89)

Python

>>> from sage.all import *
>>> tau, n, k = Integer(118), Integer(250), Integer(70)
>>> GSD.parameters_given_tau(tau, n_k=(n, k))
(47, 89)

Choosing a decoding radius which is too large results in an errors:

Sage

sage: tau = 200
sage: GSD.parameters_given_tau(tau, n_k=(n, k))
Traceback (most recent call last):
...
ValueError: The decoding radius must be less than
the Johnson radius (which is 118.66)

Python

>>> from sage.all import *
>>> tau = Integer(200)
>>> GSD.parameters_given_tau(tau, n_k=(n, k))
Traceback (most recent call last):
...
ValueError: The decoding radius must be less than
the Johnson radius (which is 118.66)

rootfinding_algorithm()[source]#

Return the rootfinding algorithm that will be used.

Remember that its signature has to be: my_rootfinder(Q, maxd=default_value, precision=default_value). See roth_ruckenstein_root_finder() for an example.

EXAMPLES:

Sage

sage: C = codes.GeneralizedReedSolomonCode(GF(251).list()[:250], 70)
sage: D = C.decoder("GuruswamiSudan", tau=97)
sage: D.rootfinding_algorithm()
<function alekhnovich_root_finder at 0x...>

Python

>>> from sage.all import *
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(251)).list()[:Integer(250)], Integer(70))
>>> D = C.decoder("GuruswamiSudan", tau=Integer(97))
>>> D.rootfinding_algorithm()
<function alekhnovich_root_finder at 0x...>

sage.coding.guruswami_sudan.gs_decoder.alekhnovich_root_finder(p, maxd=None, precision=None)[source]#: Wrapper for Alekhnovich’s algorithm to compute the roots of a polynomial with coefficients in \(F[x]\).

sage.coding.guruswami_sudan.gs_decoder.n_k_params(C, n_k)[source]#

Internal helper function for the GRSGuruswamiSudanDecoder class for allowing to specify either a GRS code \(C\) or the length and dimensions \(n, k\) directly, in all the static functions.

If neither \(C\) or \(n,k\) were specified to those functions, an appropriate error should be raised. Otherwise, \(n, k\) of the code or the supplied tuple directly is returned.

INPUT:

C – A GRS code or None
n_k – A tuple \((n,k)\) being length and dimension of a GRS code, or None.

OUTPUT:

n_k – A tuple \((n,k)\) being length and dimension of a GRS code.

EXAMPLES:

Sage

sage: from sage.coding.guruswami_sudan.gs_decoder import n_k_params
sage: n_k_params(None, (10, 5))
(10, 5)
sage: C = codes.GeneralizedReedSolomonCode(GF(11).list()[:10], 5)
sage: n_k_params(C, None)
(10, 5)
sage: n_k_params(None,None)
Traceback (most recent call last):
...
ValueError: Please provide either the code or its length and dimension
sage: n_k_params(C, (12, 2))
Traceback (most recent call last):
...
ValueError: Please provide only the code or its length and dimension

Python

>>> from sage.all import *
>>> from sage.coding.guruswami_sudan.gs_decoder import n_k_params
>>> n_k_params(None, (Integer(10), Integer(5)))
(10, 5)
>>> C = codes.GeneralizedReedSolomonCode(GF(Integer(11)).list()[:Integer(10)], Integer(5))
>>> n_k_params(C, None)
(10, 5)
>>> n_k_params(None,None)
Traceback (most recent call last):
...
ValueError: Please provide either the code or its length and dimension
>>> n_k_params(C, (Integer(12), Integer(2)))
Traceback (most recent call last):
...
ValueError: Please provide only the code or its length and dimension

sage.coding.guruswami_sudan.gs_decoder.roth_ruckenstein_root_finder(p, maxd=None, precision=None)[source]#: Wrapper for Roth-Ruckenstein algorithm to compute the roots of a polynomial with coefficients in \(F[x]\).