# Guruswami-Sudan utility methods#

AUTHORS:

• Johan S. R. Nielsen, original implementation (see [Nie] for details)

• David Lucas, ported the original implementation in Sage

sage.coding.guruswami_sudan.utils.gilt(x)[source]#

Returns the greatest integer smaller than x.

EXAMPLES:

sage: from sage.coding.guruswami_sudan.utils import gilt
sage: gilt(43)
42

>>> from sage.all import *
>>> from sage.coding.guruswami_sudan.utils import gilt
>>> gilt(Integer(43))
42


It works with any type of numbers (not only integers):

sage: gilt(43.041)
43

>>> from sage.all import *
>>> gilt(RealNumber('43.041'))
43


Returns the Johnson-radius for the code length $$n$$ and the minimum distance $$d$$.

The Johnson radius is defined as $$n - \sqrt(n(n-d))$$.

INPUT:

• n – an integer, the length of the code

• d – an integer, the minimum distance of the code

EXAMPLES:

sage: sage.coding.guruswami_sudan.utils.johnson_radius(250, 181)                # needs sage.symbolic
-5*sqrt(690) + 250

>>> from sage.all import *
>>> sage.coding.guruswami_sudan.utils.johnson_radius(Integer(250), Integer(181))                # needs sage.symbolic
-5*sqrt(690) + 250

sage.coding.guruswami_sudan.utils.ligt(x)[source]#

Returns the least integer greater than x.

EXAMPLES:

sage: from sage.coding.guruswami_sudan.utils import ligt
sage: ligt(41)
42

>>> from sage.all import *
>>> from sage.coding.guruswami_sudan.utils import ligt
>>> ligt(Integer(41))
42


It works with any type of numbers (not only integers):

sage: ligt(41.041)
42

>>> from sage.all import *
>>> ligt(RealNumber('41.041'))
42

sage.coding.guruswami_sudan.utils.polynomial_to_list(p, len)[source]#

Returns p as a list of its coefficients of length len.

INPUT:

• p – a polynomial

• len – an integer. If len is smaller than the degree of p, the returned list will be of size degree of p, else it will be of size len.

EXAMPLES:

sage: from sage.coding.guruswami_sudan.utils import polynomial_to_list
sage: F.<x> = GF(41)[]
sage: p = 9*x^2 + 8*x + 37
sage: polynomial_to_list(p, 4)
[37, 8, 9, 0]

>>> from sage.all import *
>>> from sage.coding.guruswami_sudan.utils import polynomial_to_list
>>> F = GF(Integer(41))['x']; (x,) = F._first_ngens(1)
>>> p = Integer(9)*x**Integer(2) + Integer(8)*x + Integer(37)
>>> polynomial_to_list(p, Integer(4))
[37, 8, 9, 0]

sage.coding.guruswami_sudan.utils.solve_degree2_to_integer_range(a, b, c)[source]#

Returns the greatest integer range $$[i_1, i_2]$$ such that $$i_1 > x_1$$ and $$i_2 < x_2$$ where $$x_1, x_2$$ are the two zeroes of the equation in $$x$$: $$ax^2+bx+c=0$$.

If there is no real solution to the equation, it returns an empty range with negative coefficients.

INPUT:

• a, b and c – coefficients of a second degree equation, a being the coefficient of the higher degree term.

EXAMPLES:

sage: from sage.coding.guruswami_sudan.utils import solve_degree2_to_integer_range
sage: solve_degree2_to_integer_range(1, -5, 1)                                  # needs sage.symbolic
(1, 4)

>>> from sage.all import *
>>> from sage.coding.guruswami_sudan.utils import solve_degree2_to_integer_range
>>> solve_degree2_to_integer_range(Integer(1), -Integer(5), Integer(1))                                  # needs sage.symbolic
(1, 4)


If there is no real solution:

sage: solve_degree2_to_integer_range(50, 5, 42)
(-2, -1)

>>> from sage.all import *
>>> solve_degree2_to_integer_range(Integer(50), Integer(5), Integer(42))
(-2, -1)