Géométrie et algèbre effectives

In this talk, we will focus on particular decoding algorithms for Reed Solomon codes. It is known that for these codes, it is possible to correct an amount of errors equal to or even superior than half the minimum distance. In general though, beyond this bound, the uniqueness of the solution is no longer entailed. Hence, given a vector $y\in\mathbb{F}_q^n$, it is possible to either use list decoding algorithms, like Sudan algorithm and Guruswami-Sudan algorithm, which return the list of all the closest codewords to $y$, or unique decoding algorithms, like the Power Decoding algorithm, which return the closest codeword to $y$ if unique at the prize of some failure cases. In this scenario, I will present a new unique decoding algorithm, that is the Power Error Locating Pairs algorithm. Based on Pellikaan's Error Correcting Pairs algorithm, it has for Reed Solomon codes the same decoding radius as Sudan algorithm and Power Decoding algorithm, but with an improvement in terms of complexity. Moreover, like the Error Correcting Pairs algorithm, it can be performed on all codes which dispose from a special structure (among them, Reed Solomon codes, algebraic geometry codes and cyclic codes).

Le but de l'exposé sera de présenter des nouveaux résultats sur les group codes qui suggèrent des applications possibles à la cryptographie basée sur les codes et à la protection contre des attaques par canaux auxiliaires.