Cours LB partie 2

Question 1

Définition fonctionnelle des codes de Reede-Solomon

Answer 1

F ∈ {F}_q[X]_<k→ (F(α₁), …, F(α_n)) avec α_i != α_j, n ≥ k et α_i ∈ {F}_q

Question 2

Complexité de l’encodage sans erreur naïf

Answer 2

O(k) opérations arithmétiques car n évaluations :
- 2k multiplications et k additions avec l’algorithme naïf
- k multiplications et k additions avec l’algorithmes de Horner

Question 3

Calcul de F(α) utilisé dans l’algorithme dichotomique

Answer 3

F(α) = F mod (X - α)

Question 4

Algorithme d’évaluation multipoints rapide (entrée, sortie, algorithme)

Answer 4

• Entrée : P ∈ {K}[X]_<k, (α₁, …, α_n) ∈ {K} avec n ≥ k)
• Sortie : (P(α_i))_{i = 1..n}
• Algorithme EMR :
  
  • Si deg(P) = 0 :
    
    • Renvoyer(p₁, …, p_n)
  • P₀ ← P mod Π_{i = 1 → n//2} (X - α_i)
  • P₁ ← P mod Π_{i = n//2+1 → n} (X - α_i)
  • Renvoyer CONCAT(EMR(P₀, (α_i)_{i = 1..n//2}), EMR(P₁, (α_i)_{i = n//2..n}))

Question 5

Complexité du produit polynomial naïf

Answer 5

O(n²)

Question 6

Complexité du produit polynomial par Karatsuba

Answer 6

O(n^log₂3)

Question 7

Complexité du produit polynomial par FFT

Answer 7

S’il y a une racine de l’unité dans le corps, O(nlogn)

Question 8

Complexité du produit polynomial retenu pour tous les corps (sans condition)

Answer 8

O(nlog²n)

Question 9

Définition de la super-linéarité

Answer 9

Pour M : M(n) ≥ k × M(n/k)

Question 10

Complexité de la division polynomiale naÏve

Answer 10

Pour A = B×Q + R, O(deg(B) × deg(Q))

Question 11

Complexité de la division polynomiale par dichotomie

Answer 11

Pour A = B×Q + R et n = deg(B), O(M(n)logn)

Question 12

Complexité de la division polynomiale par itération de Newton

Answer 12

Pour A = B×Q + R et n = deg(B), O(M(n))

Question 13

Cas dans lequel la division polynomiale naïve est plus efficace que la division par itération de Newton

Answer 13

Pour A = B×Q + R, si deg(A) = deg(B) + 1, alors deg(Q) = 1 :
- O(n) avec l’algorithme naïf
- O(M(n)) avec l’itération de Newton

Question 14

Complexité du calcul naïf de Π_{i = 1→n} (X - α_i)

Answer 14

Avec une simple boucle sur n, O(nM(n))

Question 15

Complexité du calcul non-naïf de Π_{i = 1 → n} (X - α_i)

Answer 15

Avec la dichotomie Π_{i = 1 → n} (X - α_i) = Π_{i = 1 → n//2} (X - α_i)Π_{i = n//2+1 → n} (X - α_i), O(M(n)logn)

Question 16

Complexité de l’algorithme EMR (Évaluation Multipoints Rapide) sans pré-caclul

Answer 16

O(M(n)log²n)

Question 17

Complexité de l’algorithme EMR (Évaluation Multipoints Rapide) avec pré-caclul

Answer 17

O(M(n)logn) + O(M(n)logn)
(pré-calcul des Π + algorithme même)

Question 18

Formule de complexité de l’algorithme EMR avant calcul

Answer 18

C(n) = 2M(n/2)log(n/2) + 2M(n/2) + 2C(n/2)
(pré-calcul + divisions pour le modulo + récursion)

Question 19

Algorithme de calcul de l’arbre des sous-produits (entrée, sortie, algorithme)

Answer 19

• Entrée : α₁, …, α_n
• Sortie : arborescence des sous-produits
• Algorithme :
  
  • Utiliser l’algorithme dichotomique pour calculer Π_i=1→k (X - α_i) et sauvegarder chaque sous-produit au fur et à mesure

Question 20

Complexité du calcul de l’arbre des sous-produits

Answer 20

O(M(n)logn)

Question 21

Quand est-ce qu’il est possible d’effectuer un décodage sans erreur ?

Answer 21

Lorsqu’il y a au moins k évaluations sans erreur, où deg(P) < k

Question 22

Distance de code en fonction du degré et du nombre d’évaluations

Answer 22

Pour deg(P) < k et n évaluations, on sait qu’il faut au plus n - k effacements, donc d - 1 = n - k ⇔ d = n - k + 1

Question 23

Définition fonctionnelle de l’interpolation de Lagrange

Answer 23

(α_i, y_i)_i=1..k → P ∈ {P}_q[X]_<k tel que P(α_i) = y_i pour i=1..k avec deg(P) < k

Question 24

Formule de Lagrange

Answer 24

P(X) = Σ_i=1..k y_iL_i(X) avec L_i(X) un polynôme de Lagrange

Question 25

Formule des polynômes de Lagrange

Answer 25

L_i = A_i(X)/A_i(α_i) avec A_i(X) = Π_i!=j (X - α_j) = A(x)/(X - α_i)

Question 26

Forme des différents vecteurs utilisés dans le calcul de l'interpolation de Lagrange, pour X = (α_i)_i=1..k

Answer 26

- A_i(X) → (0, 0, ..., !=0, ..., 0, 0) - L_i(X) → (0, 0, ..., 1, ..., 0, 0) - y_iL_i(X) → (0, 0, ..., y_i, ..., 0, 0) - P(X) = (y₁, y₂, ..., y_i, ..., y_n-1, y_n)

Question 27

Étapes de calcul de l'interpolation de Lagrange (version naïve)

Answer 27

- Calculer A_i(X) = Π_i!=j (X - α_j) = A(X)/(X - α_i) - Calculer A_i(α_i) - Calculer L_i = A_i(X)/A_i(α_i) - Calculer y_iL_i - Faire la somme des résultats obtenus

Question 28

Complexité du calcul des polynômes de Lagrange (version naïve)

Answer 28

- O(k) pour A_i(X) car division avec deg(B) = 1 et deg(Q) = k - O(k) pour A_i(α_i) - Total : O(k²)

Question 29

Complexité du calcul naïf de l'interpolation de Lagrange

Answer 29

- Calcul de chaque L_i(X) en O(M(k)logk) donc en tout O(kM(k)logk) - Calcul de chaque y_iL_i(X) en O(k) donc O(k²) en tout - Calcul de la somme finale de P en O(k²) - Total : O(kM(k)logk)

Question 30

Astuce utilisée pour être moins naïf dans le calcul des polynômes de Lagrange

Answer 30

- (uv)' = u'v + uv' - (uvw)' = (uv)'w + (uv)w' = u'vw + uv'w + uvw' - (Π_i=1→k f_i)' = Σ_i=1→k (Π_j!=i f_j)×f_i'

Question 31

Étapes de calcul des polynômes de Lagrange (version non-naïve)

Answer 31

- Calculer A(X) = Π_i=1→k (X - α_i) - Dériver A(X) : A'(X) = Σ_i=1→k Π_j!=i (X - α_j) = Σ_i=1→k A_i(X) - Calculer A'(α_l) = Σ_i=1→k Π_j!=i (α_l - α_j) et comme tous les produits s'annulent sauf 1, A'(α_l) = Π_j!=l (α_l - α_j) et on a la constante qui est en diviseur du polynôme de Lagrange L_k(X)

Question 32

Reformulation de la somme finale de l'interpolation de Lagrange

Answer 32

P(x) = Σ_i=1..k y_iL_i(X) = Σ_i=1..k y_i(A_i(X) / A_i(α_i)) = Σ_i=1..k y_i((A(X)/(X - α_i)) / A_i(α_i)) = Σ_i=1..k y_i(A(X) / (A_i(α_i) × (X - α_i))) = Σ_i=1..k (y_i / A_i(α_i)) × (A(X) /(X - α_i)) = Σ_i=1..k b_i × (A(X) / (X - α_i)) avec b_i = y_i/ A_i(α_i)

Question 33

Complexité détaillée de la somme naïve finale de l'interpolation de Lagrange

Answer 33

- Divisions naïves (car deg(Q) = 1) en O(n) - Multiplications par b_i en O(n) - Sommes en O(n) - Total O(n²) car n fois les opérations précédentes

Question 34

Idée sur laquelle est basée l'algorithme dichotomique pour la somme finale de l'interpolation de Lagrange

Answer 34

Soient - A⁰ Π_j=1..n//2 (X - α_j) - A¹ Π_j=n//2+1..n (X - α_j) alors Σ_i=1..n b_i × (A(x) / (X - α_i)) = (Σ_i=1..n//2 b_i × (A⁰(x) / (X - α_i))) × A¹(x) + (Σ_i=n//2+1..n b_i × (A¹(x) / (X - α_i))) × A⁰(x)

Question 35

Algorithme de calcul de la somme finale de l'interpolation de Lagrange (entrée, sortie, algorithme)

Answer 35

- Entrée : n, (α_i)_i=1..n, (b_i)_i=1..n - Sortie : Σ_i=1..k b_i × (A(X) / (X - α_i)) - Algorithme : - Si n = 1, renvoyer b₁ - S₀ = Algorithme(n//2, (α_i)_i=1..n//2, (b_i)_i=1..n//2) - S₁ = Algorithme(n-n//2, (α_i)_i=n//2+1..n, (b_i)_i=n//2+1..n) - S = S₀A¹ + S₁A⁰ - Renvoyer S

Question 36

Formule de complexité de l'algorithme de calcul de la somme finale de l'interpolation de Lagrange

Answer 36

M(n)logn + S(n) ≤ M(n)logn + 2S(n/2) + 2M(n/2) (ASP + 2 appels récursifs + 2 produits)

Question 37

Complexité de l'algorithme de calcul de la somme finale de l'interpolation de Lagrange

Answer 37

O(M(n)logn)

Question 38

Définition du problème de décodage unique des codes de Reede-Solomon

Answer 38

Instance : Message (α_i, y_i)_i=1..n reçu avec au plus e erreur où e = (n - k)//2 = (d - 1)//2 avec d la distance de code Problème : Retrouver F ∈ {F}_q[X] _{satisfaisant F(αi) = yi sauf en eu plus e indices}

Question 39

Idée derrière le polynôme locateur d'erreur

Answer 39

On sait que dans le décodage unique des code de Reede-Solomon, on a presque toujours (F(α_i) = y_i) ⇔ (F(α_i) -y_i = 0), donc si on trouve un polynôme Λ qui est nul en les erreurs, Λ(X) × (F(X) - y_i) est toujours nul en X = α_i

Question 40

Polynôme locateur d'erreur

Answer 40

Λ(x) = Π_{i tel que F(αi) != yi} (X - α_i)

Question 41

Équation clé (première écriture)

Answer 41

Λ(α_i)y_i = (ΛF)(α_i)

Question 42

Équation clé (première reformulation)

Answer 42

- Inconnues : φ, ψ ∈ {F}_q[X] avec deg(φ) ≤ e et deg(ψ) < k + e - Équations : φ(α_i)y_i = ψ(α_i) pour i = 1..n

Question 43

Solution évidente non-nulle de l'équation clé

Answer 43

(Λ, ΛF)

Question 44

Lemme d'"unicité" des solutions de l'équation-clé (énoncé)

Answer 44

Soient (φ₁, ψ₁) et (φ₂, ψ₂) des solutions non-nulles, alors (ψ₁ / φ₁) = (ψ₂ / φ₂)

Question 45

Lemme d'"unicité" des solutions de l'équation-clé (schéma de preuve)

Answer 45

- Montrer que ψ₁φ₂ et ψ₂φ₁ sont égaux - Montrer que φ₁ et φ₂ sont non-nuls sinon les deux solutions sont nulles - Montrer qu'on a alors ψ₁φ₂ = ψ₂φ₁ ⇔ (ψ₁ / φ₁) = (ψ₂ / φ₂)

Question 46

Algorithme de décodage de Reese-Solomon (entrée, sortie, algorithme)

Answer 46

- Entrée : (y_i)_i=1..n, k, n, e, (α_i)_i=1..n, {F}_q - Sortie : F ∈ {F}_q[X] _{telle que F(αi) = yi en ≥ n - e points, ou "NON" - Algorithme : - Si l'espace de l'équation-clé est {(0, 0)}, renvoyer NON - Si φ divise ψ et deg(ψ / φ) < k, renvoyer (ψ / φ) - Renvoyer NON}

Question 47

Propriété de correction de l'algorithme de décodage de Reese-Solomon (énoncé)

Answer 47

L'algorithme réussit si et seulement le mot reçu était proche d'un mot de code

Question 48

Propriété de correction de l'algorithme de décodage de Reese-Solomon (schéma de preuve)

Answer 48

⇐ : - Montrer que si le mot reçu était proche d'un mot de code, alors il existe une solution (φ, ψ) telle que φ divise ψ et deg(ψ / φ) < k en utilisant le lemme d'unicité avec (Λ, F) et (φ, ψ) ⇒ : - Définir g tel que φ(α_i)y_i = ψ(α_i) = g(α_i)φ(α_i) - Montrer que g(α_i) = y_i là où φ(α_i) est non-nul - Montrer que φ(α_i) est nul sur au plus e points par définition de l'équation-clé

Question 49

Équation clé (reformulation avec Lagrange)

Answer 49

φ(α_i)y_i = ψ(α_i) ⇔ φ(α_i)L(α_i) = ψ(α_i) ⇔ (φL - ψ)(α_i) = 0 avec L l'interpolant de Lagrange des y_i en α_i

Question 50

Degré du polynôme (φL - ψ)

Answer 50

- deg(φ) ≤ e - deg(L) = n - 1 - deg(ψ) ≤ k + e - 1 - deg(φL - ψ) > n

Question 51

Comment peut-on montrer que (φL - ψ) est nul ?

Answer 51

- On ne peut pas utiliser la technique dans laquelle un polynôme de degré n s'annule en n-1 points, parce qu'on sait que deg(φL - ψ) > n - Soit G = Π_i=1..n (X - α_i), alors (φL - ψ)(α_i) est nul si et seulement si G divise (φL - ψ)(α_i), c'est-à-dire que φL - ψ vaut 0 modulo G

Question 52

Équation clé (dernière reformulation avec G = Π_i=1..n (X - α_i))

Answer 52

- Inconnues : φ, ψ ∈ {F}_q[X] avec deg(φ) ≤ e et deg(ψ) < k + e - Équations : φL = ψ mod G

Question 53

Forme des solutions de l'équation clé (denière reformulation)

Answer 53

Soient u et v des coefficients de Bezout, c'est-à-dire des coefficients tels que uG + vL = R avec R multiple du PGCD de G et L, alors (V, R) est solution de l'équation-clé (si on fait attention aux degrés)

Question 54

Algorithme d'Euclide pour le PGCD

Answer 54

PGCD(A, B) : - Q₁, R₂ = DivEucl(R₀ = A, R₁ = B) - Q₂, R₃ = DivEucl(R₁ = B, R₂) - Q₃, R₄ = DivEucl(R₂, R₃) - ... - Q_l-1, R_l = DivEucl(R_l-2, R_l-1) avec R_l = 0 - Renvoyer R_l-1

Question 55

Correction de l'algorithme d'Euclide (schéma de preuve)

Answer 55

- Preuve de la récurrence : - Montrer que PGCD(A, B) = PGCD(B, R) en montrant que A = BQ + R, c'est à dire que (D divise A et D divise B) ⇔ (D divise B et D divise R) ou encore que si les diviseurs communs sont les mêmes, les plus grands d'entre eux sont égaux - Pour cela, faire les deux sens de ⇔ - Preuve de la terminaison : - Montrer qu'on finit bien par avoir R_l = 0 - Pour cela, poser l = deg(A), alors deg(R_l) ≤ deg(R_l-1) - 1 ≤ ... ≤ deg(R₀) - l, donc l'algorithme se termine en l + 1 = deg(A) + 1 étapes au plus

Question 56

Complexité de l'algorithme d'Euclide

Answer 56

Avec la division naïve, chaque divisions coûte O(deg(R_i)deg(Q_i)) = O(deg(R_i)(deg(R_i-1) - deg(R_i))), donc en tout Σ_i=1..l-1 deg(R_i)(deg(R_i-1) - deg(R_i)) ≤ deg(A)deg(B)

Question 57

Cas de base de l'algorithme d'Euclide étendu

Answer 57

u_iA + v_iB = R_i : - Pour i = 0, A = R₀ = 1A + 0B → u₀ = 1, v₀ = 0 - Pour i = 1, B = R₁ = 0A + 1B → u₁ = 0, v₁ = 1

Question 58

Principe de l'agorithme d'Euclide étendu

Answer 58

On travaille avec des couples, c'est à dire qu'on exprime (R_i, R_i+1) en fonction de (R_i-1, R_i) : (R_i....) = (0 1...)(R_i-1) (R_i+1) = (1 -Q_i)(R_i ) = T_i×T_i-1×...×T₁(R₀, R₁) Donc (R_i....) = (u_i... v_i...)(R₀) (R_i+1) = (u_i+1 v_i+1)(R₁)

Question 59

Algorithme d'Euclide étendu

Answer 59

- AEE(A, B) avec deg(A) > deg(B) : - i = 1 - (R₀, R₁) ← (A, B) - (u₀ v₀) ← (1 0) ..(u₁ v₁) ......(0 1) - Tant que R_i != 0 : - (Q_i, R_i+1) ← DivEucl(R_i-1, R_i) - (u_i+1, v_i+1) ← (1 - Q_i)(u_i-1 v_i-1) ....................................(u_i... v_i...) - i = i + 1 - Renvoyer R_i-1, u_i-1, v_i-1

Question 60

Correction de l'algorithme d'Euclide étendu (schéma de preuve)

Answer 60

- Même terminaison que le PGCD - Correction : - On a déjà montré que R_i-1 = PGCD(A, B) - On doit montrer que u_i-1A + v_i-1B = Ru_i-1 par récurrence - Cas de base pour i = 0 et i = 1 - Hérédité avec des manipulations de matrices

Question 61

Complexité de l'algorithme d'Euclide étendu (détails de calcul)

Answer 61

- Montrer que ∀ i≥1, deg(v_i) = Σ_j=1..i-1 deg(Q_i) = r₀ - r_i-1 par récurrence - Montrer que ∀ i≥2, deg(u_i) = Σ_j=1..i-1 deg(Q_i) = r₁ - r_i-1 par récurrence - Additionner le coût des divisions euclidiennes (deg(A)deg(B)) au coût de calcul de u_i+1 (deg(A)deg(B))

Question 62

Complexité de l'algorithme optimal d'Euclide étendu (qui n'est pas celui que l'on a vu en cours)

Answer 62

O(M(n)logn)

Question 63

Défaut de l'algorithme optimal d'Euclide étendu (qui n'est pas celui que l'on a vu en cours)

Answer 63

On ne peut pas sortir toutes les informations car cela dépasserait la complexité, donc on ne peut récupérer que les Q_i