# Codes avec les polynômes : Reed Solomon (chapitre livre)
* Interet codes Reed Solomon: capacité de correction maximale par rapport à la redondance minimale
* Le message envoyé dans le protocole, c'est la suite d'evaluation d'un polynome dans un ensemble de points d'evaluation. A la reception, la liste d'evalués, peut etre partiellement fausse. Comment la reconstruire ? Déja, on regarde le cas sans erreur : est_il possible de reconstruire un polynome en partant de ses evalués (justes) ?

## Interpolation polynomiale :
* Etant donnés K+1 point d'evaluation distints a_1,..,a_k+1,
il est possible, en partant de F(a_1),..,F(a_k+1), de retrouver le polynome F. Ce polynome (unitaire) de degrée au plus k, appelons le F(x) (preuve d'Armelle sur l'unicité au tableau), il est uniquement determiné. Ecrire la preuve.
* Comment trouver l'interpolateur ? interpolation de Lagrange (à vous )
* Bien comprendre que en partant de points differents on obtient des polynomes differents.

## Et avec des erreurs?
* Si des erreurs surviennent dans la liste des évalués F(a_1),..F(a_k), je ne peux pas reconstruire avec k+1 elements un poly de degré K. Donc, il faut ajouter de la redondance. Donc, plus d'évalués.

# Parametres codes
* role de la distance dans un code pour voir la detection, la correction
(pag 27-28) livre en ligne. Essayez de comprendre la preuve de la prop 1.4.2.

# Ce papier : le cas creux
* les codes Reed Solomon c'est classique (poly denses), dans le papier il y a l'etudes du cas polynomes creux avec erreurs (qui est l'equivalent des polynomes denses.
* Representation creuse des polynomes (l'information n'est plus lié au degré, ici c'est lié à "t" nombre des monomes on a 2 t informations (chaque monome porte 2 informations))
* Les points d'eval: on ne prend pas des points au PIF. On prend 2t points 1,w,w^2 ,..,w^(2t-1). Sur ce type de points, il existe un unique polynome comme dans le cas dense.
* Où on travaille ? Sur les entiers ok, mais souvent, on regarde les corps fini (regardez si vous arrivez à comprendre ce que c'est la problematique de l'ordre d'un point et les corps finis. Aidez vous avec vos souvenirs d'équations modulaires). L'interet des corps fini c'est de faire des calculs exacts qui evitent les grossissement de taille (2^80 -> repres pas exacte).

## RDV 08 juin 2023
### Unicité de l'interpolateur de Lagrange :
-comprendre que si p(x) polynome et a racine alors
-p(a)=0
-(x-a) divise p(x)
-p(x)=(x-a)*g(x) où deg(g(x))<deg(p(x))
Si p(x) s'annulle sur 3 racines (par exemple) son degré sera au moins 3 (car il peut s'ecrire comme p(x)=(x-a1)(x-a2)(x-a3)*q(x))
-Si on avait 2 interpolateurs p1 et p2, il signifie que p1(a)=p2(a) pour chaque point a d'Interpolation.
-Donc p1-p2(a)=0 pour tous les points d'interpolation donc il est le polynome nul car il s'annule dans plus de points que son degré.

Rafael
* nous explique que l'unicité de l'Interpolateur de Lagrange peut se montrer à l'aide de l'ecriture matricielle en utilisant le fait que la matrice de Vandermonde est inversible.
* nous fait la preuve du determinante de la matrice de Vandermonde (très bien ;) )

### Existence de l'interpolateur de Lagrange
Loic
fait la preuve que la forme de l'interpolateur de Lagrange des points (xi,yi) L(x)=\sum yj Lj(x) marche (càd il est tel que L(x_i)=yi) où Lj(x)=prod_{i\neq j}(x-xi)/prod(xj-xi).

## Reed Solomon comme intrepolation

On fait la preuve du Décodage des Reed Solomon (à revoir bien la semaine)

# RDV 16 juin 2023

Reflexion sur la division de polynomes: E divise Q si existe P tq Q=PxE et on appelle Q/E une fraction de polynomes. Si E divise Q, Q/E est un polynome, attention à la difference entre function rationelle et division de polynomes.
## Un peu de creux et de recurrences linéaires
-definition polynome creux
-definition suite recurrente linéaire (defini par rapport à un ensemble de conditions initiales). Existence du polynome caracteristique associé.
-P = \sum ^{t-1} p_i x^{e_i} poly creux de t monomes, avec 2t points d'eval : on peut Interpoler (preuve ?)
-Interp creuse avec erreurs idée:
P(1), P(w),...P(w^{t}),..P(w^{2t+1})
On divise la sequence de termes en blocs de 2t termes : avec 2T(E+1) termes on peut corriger la sequence. Chaque bloc va me donner un poly caract, un vote de majorité va me donner le resultat.---(but papier)
Le resultat sera prod(z-w^{e_i}) où les e_i identifies les monomes differents de 0 dans P. Pour trouver les coeff p-i -> syst lin.
-Papier: aussi nettoyage frequence après le vote de majorité
-representation matricielle de la recurrence lineaire avec matrice circulante Hankel.

#RDV 21 juin 2023 Point sur Ben-Or Tiwari
On fait le point sur l'algo.
But: à partir d'une squence d'évalués d'un polyn creux, sur des puissance d'un point w -> retrouver le polynome creux p(x).
-remarque : la sequence p(1),p(w),..,p(w^n) est recurrente lineaire. Son poly caracteristique est F(x)= Prod(x-w^i), verificaition au tableau (Rafael preuve au tableau, à refaire sur papier). Un fois qu'on sait que F(x) est de cette forme,on peut utiliser un algorithme qui calcule le poly caract de la suite (pour l'instant en boite noire, il s'appelle Berlekamp-Massey)-> on le factorise et cela nous donnera les w^i qui definissent le poly creux. Avec cela (le support) on calcule les coefficients avec un systeme lineaire du type Vandermonde (Rafael au tableau)

Point sur comme choisir les parametres pour garantir l'existence des w^î different de w^j et ordre des éléments dans un corps fini du type F_q avec q premier (les ordres des éléments possibles sont les diviseurs de q-1)

Conseil : regardez ca https://www.youtube.com/watch?v=HBT3SCwlGJU

La suite :
-corriger des sequences avec nombre de points
- commencer le rapport