1/4

Forum pour les étudiants de la préparation agreg option C de Grenoble

Modérateur : xcasadmin

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1/4

Message par parisse » mer. avr. 01, 2020 9:05 am

J'explique pourquoi on est obligé d'utiliser des polynomes pour représenter GF(p,n) si p et n sont grands. L'alternative c'est de prendre g un générateur du corps, et de stocker son exposant. La multiplication et l'inversion deviennent alors très faciles, mais c'est l'inverse pour l'addition et la soustraction! Il faut etre capable de representer 1+g^t comme une puissance de g, ce qui nécessite de construire une table (ca s'appelle le logarithme de Zech, https://en.wikipedia.org/wiki/Zech%27s_logarithm), chose qu'on ne peut faire que si le cardinal du corps p^n n'est pas trop grand. Par comparaison, les complexités des opérations arithmétiques sur le corps font intervenir n*ln(p) et son carré, il faut donc que le logarithme de p^n (et non p^n) ne soit pas trop grand pour pouvoir faire ces calculs.

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 9:12 am

Pour le 4), le calcul de la division euclidienne du polynôme N par le polynôme M, tous deux à coefficients dans F_p, de degrés respectifs n,m (avec n\geq m) est : (n-m+1)*m
où on considère que le calcul d'un inverse dans F_p est en tant constant, qu'on peut multiplier sans coût un polynôme par une puissance de X (puisque cela revient juste à rajouter des 0 dans un vecteur), et l'addition ou la soustraction d'un polynôme avec un polynôme possédant au plus m coefficient non nuls a un coût de m

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1/4

Message par parisse » mer. avr. 01, 2020 9:17 am

oui, ca permet de retrouver le cout du PGCD de 2 polynomes de degré<=n en O(n^2) opérations arithmétiques sur le corps, puisque n-m+1 est (à 1 près) la différence des degrés de deux restes successifs dans la suite des restes de l'algorithme d'Euclide.

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 9:21 am

Pour calculer le PGCD de deux polynômes, on répète la division euclidienne. Il faut calculer le nombre d'étape (c'est-à-dire le nombre de divisions euclidiennes à faire). Si on note R_n,Q_n le reste et le quotient obtenu à l'étape n, le coût de l'étape n est : (deg(Q_n)+1)*(deg(R_{n+1})+1)

On utilise que le reste diminue (en degré) au moins de 1 à chaque étape, et trouve un coût en O(n^2).

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 9:24 am

Le calcul d'inverse se fait par l'algorithme d'Euclide, puisque l'inverse d'un polynôme Q dans (F_p[X]/P) est donné par l'identité de Bezout appliquée à P et Q. Donc on a un coût en O(n^2) pour calculer l'inverse d'un élément de GF(p,n) (puisque c'est l'algorithme d'Euclide appliqué à P et Q, qui sont de degré n et au plus (n-1), qui donne l'identité de Bezout).

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1/4

Message par parisse » mer. avr. 01, 2020 9:25 am

Absolument pour le PGCD
N.B.: a l'oral vous pouvez donner le cout en O(n^2) opérations arithmétiques directement, mais c'est bien de savoir le justifier, car on peut aussi vous le demander!
Après, par rapport a mon énoncé, il faudrait encore estimer la dépendance des opérations arithmétiques de base sur GF(p,n) en fonction de n.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1/4

Message par parisse » mer. avr. 01, 2020 9:27 am

Pareil pour l'inverse, cout en O(n^2), vous pouvez le dire directement, mais il faut aussi savoir le justifier.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1/4

Message par parisse » mer. avr. 01, 2020 9:30 am

Mes notes pour le 4/:
Le pgcd de 2 polynomes de degré <= N est en O(N^2) opérations arithmétiques sur le corps (algorithme naif). Si le corps est GF(p,n) le cout des multiplications/divisions est en O(n^2) (dépendance par rapport à n, on ne s'intéresse pas à la dépendance par rapport à p dans cette question), celle des additions/soustractions est en O(n) donc à fortiori O(n^2). D'où un cout de PGCD en O(N^2*n^2) et si N=n (énoncé), O(n^4).
Si n est très grand, on peut améliorer avec une multiplication/division de polynomes meilleure (Karatsuba, FFT). Si N est très grand, il existe aussi des algorithmes plus efficaces (qui ne sont pas au programme : half-gcd).

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 9:33 am

Pour calculer l'inverse d'une matrice, on procède par pivot de Gauss. A chaque étape de la descente, on calcul un inverse dans GF(p,n) (à savoir l'inverse du pivot). Si la matrice est de taille k*k, on a donc O(k*n^2) comme coût pour les inverses. Les coûts des autres opérations sont en O(k*n) (il s'agit d'additionner des vecteurs de longueur k dont les coordonnées sont les polynômes de degré n).
On a donc un coût total en O(k*n^2). Et comme les opérations qui transforment A en la matrice identité (par opérations élémentaires sur les lignes) transforme la matrice identité en l'inverse de A, on a un coût en O(k*n^2).

En fait je me rends compte que ça marche bien pour n très grand, mais si on veut k grand ça ne fonctionne plus trop
Dernière modification par megarbane le mer. avr. 01, 2020 9:42 am, modifié 1 fois.

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 9:36 am

Oui pour le PGCD j'avais fait sur Fp (par GF(p,n)). Donc il faut reprendre le résultat pour ensuite calculer le PGCD de polynômes sur GF(p,n).

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: 1/4

Message par megarbane » mer. avr. 01, 2020 9:39 am

Après on peut améliorer le calcul de l'inverse avec la méthode de Strassen...

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1/4

Message par parisse » mer. avr. 01, 2020 9:39 am

megarbane a écrit :
mer. avr. 01, 2020 9:33 am
Pour calculer l'inverse d'une matrice, on procède par pivot de Gauss. A chaque étape de la descente, on calcul un inverse dans GF(p,n) (à savoir l'inverse du pivot). Si la matrice est de taille k*k, on a donc O(k*n^2) comme coût pour les inverses.
Oui.
Les coûts des autres opérations sont en O(k*n) (il s'agit d'additionner des vecteurs de longueur k dont les coordonnées sont les polynômes de degré n).
On a donc un coût total en O(k*n^2).
Ceci n'est pas correct, en effet pour réduire une colonne on a O(k) combinaison linéaires de lignes à effectuer, il faut réduire k colonnes, ce qui donne donc en tout O(k^2) combinaisons linéaires de lignes, donc O(k^3) opérations arithmétiques sur le corps. Si le corps est GF(p,n) avec n grand, cela va nous donner un cout total en O(k^3*n^2).

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1/4

Message par parisse » mer. avr. 01, 2020 9:43 am

A retenir:
Sur un corps fini, en nombre d'opérations arithmétiques sur le corps de base
  • opérations polynomiales
    addition/soustraction : O(taille),
    multiplication, PGCD, Bezout : O(taille^2) (multiplication naive, avec Karatsuba multiplication en O(taille^(ln(3)/ln(2))), avec FFT O(taille*ln(taille))
  • opérations matricielles
    addition/soustraction/multiplication par un vecteur: O(taille^2)
    multiplication et inversion de matrice O(taille^3) (multiplication naive et pivot de Gauss, avec Strassen on arrive a O(taille^(ln(7)/ln(2)))
Pour les entiers, cf. opérations polynomiales pour + - * / PGCD Bezout. Calcul de a^n mod p en O(ln(p)^2*ln(n))

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1/4

Message par parisse » mer. avr. 01, 2020 9:48 am

Indication pour Fibonacci: il faut déterminer la taille de F(n) en utilisant la relation de récurrence linéaire entre 3 termes successifs.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 1/4

Message par parisse » mer. avr. 01, 2020 10:00 am

La semaine prochaine, soit quelqu'un prend un des deux textes, soit on peut refaire des exercices, dites-moi sur quel thème.
D'ici-là n'hésitez pas à poster des messages, je consulte le forum au moins une fois par jour.

Répondre