1/4
Modérateur : xcasadmin
Re: 1/4
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.
Re: 1/4
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
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
Re: 1/4
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.
Re: 1/4
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).
On utilise que le reste diminue (en degré) au moins de 1 à chaque étape, et trouve un coût en O(n^2).
Re: 1/4
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).
Re: 1/4
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.
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.
Re: 1/4
Pareil pour l'inverse, cout en O(n^2), vous pouvez le dire directement, mais il faut aussi savoir le justifier.
Re: 1/4
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).
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).
Re: 1/4
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
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.
Re: 1/4
Oui.
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).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).
Re: 1/4
A retenir:
Sur un corps fini, en nombre d'opérations arithmétiques sur le corps de base
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)))
Re: 1/4
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.
Re: 1/4
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.
D'ici-là n'hésitez pas à poster des messages, je consulte le forum au moins une fois par jour.