The simple roots problem

International audienceThe simple roots problem is a natural question related to the structure of the error locator polynomial, which is one of the key objects in the decoding algorithms for Alternant codes. Finding the roots of this polynomial enables the error positions and thus the decoding solution for this family of codes. Hence, we propose here to study the structure of the error locator polynomial, denoted σ(x). We prove that when the degree of σ(x) is sub-linear in the length of the code, the probability that all the coefficients of σ(x) are different from zero is extremely high