mat309 2019

Modérateur : xcasadmin

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

mat309 2019

Message par parisse » mer. sept. 04, 2019 11:37 am

Cours 1 et 2 (3 et 4/9)
Motivations: 2 domaines d'application
1/ crypto (securisation des donnees)
* monoalphabetique a clef secrete: Cesar, exemple. Variante avec n'importe quelle permutation, attaque possible par frequences. Crypto symetrique: la connaissance de la clef de cryptage donne la clef de decryptage.
* pas toujours la meme lettre pour une lettre donnee: necessite l'echange prealable de la clef
* systeme ne necessitant pas d'echange prealable. Exemple RSA, esquisse rapidement (petit theoreme de Fermat...), en disant qu'on allait revenir dessus pendant toute la premiere partie du semestre. Les clefs ne sont pas symetriques.
La securite repose sur la difficulte de factoriser des entiers vs les multiplier. L'algorithme de codage/decodage doit etre efficace -> importance d'evaluer l'efficacite des algorithmes.
2/ codes (fiabilite des donnees)
detection d'erreur: exemple du bit de parite, mais ne permet pas de corriger une erreur
correction d'erreur: repetition 3 fois, mais couteux en bande passante -> on peut faire mieux.
exemple d'un code de Hamming 7,4 permettant de corriger une erreur. Utilise l'algebre lineaire a coefficients dans Z/2.

Chapitre 1: arithmetique des entiers
Def de la division euclidienne pour a entier naturel, b entier naturel non nul, a=bq+r, 0<=r<b
Ecriture en base b: unicite, existence par l'algorithme de construction, exemple 123 en base 7, 13 en base 2.
Nombre de digits 1+n avec n=floor(log en base b(N))
Petit entier (calcul par le CPU modulo 2^t pour t=8,16,32,64,128) et grand entier=ecriture d'un entier en base 2^t avec t=32 ou 64
Necessite de savoir effectuer les operations de base sur leur ecriture en base b. Parallele avec les operations sur les polynomes ayant comme coefficients les digits des entiers.
Cas de l'addition/soustraction: addition de polynomes mais il faut tenir compte des retenues, meme algo que celui appris a l'ecole primaire. Cout proportionnel au nombre de digits du plus grand des 2 entiers.
Cas de la multiplication: multiplication de polynomes, la prise en compte des retenues pour le cout est un peu plus delicate, on admet que le nombre d'operations conserve le meme cout (a une constante pres). Avec l'algorithme ecole primaire, le cout est proportionnel au produit du nombre de digits. Donc multiplie par 4 si le nombre de digits est multiplie par 2. Par contre la taille du resultat est multipliee par 2 dans ce cas. On peut esperer des algorithmes meilleurs.
Algorithme de Karatsuba sur les polynomes: on remplace 4 multiplications en degre moitie par 3, au prix d'additions.

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

Re: mat309 2019

Message par parisse » mar. sept. 10, 2019 3:36 pm

10/9 (cours 3/16):
rappel: ecriture en base b, addition/soustraction entier/polynome O(max(n,m)), multiplication native O(n*m)
Karatsuba: illustration de l'existence d'un seuil en-dessous duquel il faut utiliser la multiplication naive

Division euclidienne: algorithme de la potence pour les entiers, cout proportionnel a (n-m+1)*(m+1). Exemple en base 10 et en base 2.
Passage des entiers naturels aux entiers relatifs: + et - peuvent s'interchanger, * regle des signes, pour la division, en general on suppose b>0, il existe plusieurs conventions: r entre 0 et b-1, r peut etre negatif si a est negatif (par exemple en langage C, mais pas en Python), dans ce cas il faut ajouter b a r.
Convention du reste symetrique: -b/2<=r<b/2 (ou -b/2<r<=b/2) (si r>b/2 on remplace r par r-b et q par q+1). Sera utile pour l'algorithme d'Euclide.
Cas des polynomes, exemple, cout proportionnel a (n-m+1)*(m+1) avec n et m les degres au lieu du nombre de digits.

Parenthese sur les structures algebriques vues jusqu'a present:
groupe: associatif, symetrique, neutre. Groupe commutatif. Exemple Z,+, matrices inversibles (non commutatif), permutations (non commutatif).
anneau: groupe commutatif pour +, * associatif et distributif.
anneau commutatif
anneau unitaire
anneau integre
Exemple Z,+,* est un anneau commutatif unitaire integre. De meme les polynomes a coefficients reels, complexes ou rationnels.
Anneau euclidien: anneau muni d'une division euclidienne avec propriete de decroissance pour le reste (valeur absolue sur les entiers, degre pour les polynomes, peut se generaliser avec un stasthme)

Def de divisibilite.
Prochain cours mardi 17, je parlerai rapidement de relation d'ordre partiel, puis PGCD.

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

Re: mat309 2019

Message par parisse » mer. sept. 11, 2019 12:02 pm

Correction Xcas pour l'exo 1 de crypto de Cesar
session Xcas
En C:

Code : Tout sélectionner

#include "string.h"
#include "stdio.h"

void cesar(char * s,int k){
  int l=strlen(s);
  for (int i=0;i<l;++i){
    if (s[i]>='A' && s[i]<='Z')
      s[i]=((s[i]-'A')+k)%26+'A';
    if (s[i]>='a' && s[i]<='z')
      s[i]=((s[i]-'a')+k)%26+'a';
  }
}

int main(int argc,const char ** argv){
  char msg[1024];
  if (argc>=2)
    strcpy(msg,argv[1]);
  else 
    scanf("%s",msg);
  char buf[strlen(msg)+1];
  for (int k=1;k<26;++k){
    strcpy(buf,msg); // on peut aussi ne faire la copie qu'une fois et cesar(buf,1)
    cesar(buf,k);
    printf("%i: %s\n",k,buf);
  }
  return 0;
}
Debut de correction pour l'exercice 2
session Xcas

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

Re: mat309 2019

Message par parisse » mar. sept. 17, 2019 4:18 pm

17/9:
Divisibilite: rappel defintion, diviseurs de 1 = inversibles = 1 et -1, on peut se ramener aux entiers naturels. Relation d'ordre (reflexivite, antisymetrie, transitivite), partiel (contrairement a <= sur R ou l'ordre lexicographique).
PGCD de 2 entiers naturels: plus grand element de l'ensemble des diviseurs communs. Convention PGCD(0,0)=0.
Preuve de PGCD(a,b)=PGCD(b,r) => algorithme d'Euclide. Exemple avec 245 et 55.
Se termine en au plus b etapes. On peut montrer mieux (exercice de TD), ou plus simplement en remplacant r par b-r si r>b/2, on a alors au plus log2(b)+1 etapes. Cout en n^2 si n=max(log2(a),log2(b)).
PGCD binaire, exemple avec 490 et 220. Cout en n^2.
Identite de Bezout via l'algorithme d'Euclide. Exemple avec 245 et 55. Cas general avec les 3 suites recurrentes.

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

Re: mat309 2019

Message par parisse » mer. sept. 18, 2019 5:39 pm

18/9:
Programmation de l'algorithme d'Euclide etendu.
session Xcas
Corollaires
* si d|a et d|b alors d|pgcd(a,b)
Nombre premiers entre eux, def. a/pgcd et b/pgcd sont premiers entre eux
* lemme Gauss
* si a|c et b|c et pgcd(a,b)=1 alors ab|c
* resolution de a*x+b*y=c. Exemple 14x+10y=5 puis 4
* decomposition en elements simples de fraction d'entiers. Pas d'application, mais celle des fractions de polynomes en a.
Passage aux polynomes: on change de division euclidienne, les inversibles sont les polynomes constants non nuls, on normalise les PGCD par des polynomes unitaires. Le reste est identique. Exemple: calcul de PGCD de x^3-1 et x^2-1 (zut, il est en exo 11... tant pis), Bezout pour x^3-1 et x^2-1. Decomposition en elements simples de 1/(x^2-1) avec Bezout pour x-1 et x+1, application au calcul de primitive.
J'ai dit qu'il fallait en priorite comprendre l'arithmetique des entiers.

Prochain cours commencera par les restes chinois.

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

Re: mat309 2019

Message par parisse » mar. sept. 24, 2019 2:55 pm

24/9:
Restes chinois: m et n premiers entre eux, a et b quelconques, il existe c tel que c-a multiple de m et c-b multiple de n. Les solutions different par un multiple de m*n, unicite dans un intervalle de longueur m*n, par ex. [0,m*n[ ou ]-m*n/2,m*n/2].
Exemple c-2 multiple de 13 et c-4 de 5 -> c=-11, et 54.
J'ai dit que ca servait pour faire des algorithmes efficaces (modulaires), mais je n'ai pas eu le temps de l'illustrer. En expliquant cet enonce, j'ai pris conscience qu'il vaudrait mieux le faire apres avoir introduit Z/nZ.

Nombres premiers: definition p>=2, p=1 n'est pas premier, exemples.
Prop: p et q distincts premiers sont premiers entre eux. p et p_1*...*p_n sont premiers entre eux si p est distinct des p_i
Thm: tout entier n>=2 se factorise de maniere unique comme produit de nombres premiers ecrits en ordre croissant.
Remarque: caracterisation des diviseurs d'un entier avec les multiplicites des facteurs premiers. Nombre de diviseurs d'un entier dont on connait la factorisation. Caracterisation du PGCD de 2 entiers dont on connait la factorisation. Il ne faut pas utiliser cette methode pour calculer un PGCD!

Algorithme naif de factorisation d'un entier n>=2:
Initialiser p a 2, l (liste des diviseurs) a liste vide
Tantque p<=n
Tantque n est divisible par p, ajouter p a la liste l et remplacer n par n/p
p <- p+1
Renvoyer l
Au pire n iterations.
Amelioration: si n non premier, il a un diviseur <=sqrt(n), on limiter la boucle a tantque p*p<=n.
Nombre d'iterations: au pire sqrt(n). On peut diviser par 2 en testant 2 d'abord, puis les nombres impairs, par 3 en testant 2,3 et 6*k-1 et 6*k+1, mais pour n de l'ordre de 10^40 cela fait environ 10^20 divisions, donc 10^10 secondes, i.e. de l'ordre de 300 ans.
Il existe des algorithmes plus efficaces, il faut quelques secondes pour factoriser un produit de 2 nombres premiers de l'ordre de 10^60
Illustration avec Xcas, n:=10; p:=nextprime(10^n); q:=nextprime(p); N:=p*q; time(ifactor(N));
On peut aller a environ 150 chiffres avec des algorithmes encore plus efficaces et plusieurs ordinateurs en parallele et du temps, au-dela cela devient vite impraticable (le record cite par wikipedia est de 768 bits pour 2000 ans de temps CPU).

Prochain cours: on attaque Z/nZ

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

Re: mat309 2019

Message par parisse » mar. oct. 01, 2019 4:53 pm

1/10:
Congruence et Z/nZ
def. de a=b mod n, relation d'equivalence (reflexive/symetrique/transitive), classe d'equivalence. Classe(a)=Classe(b) ou sont disjointes. n classes -> Z/nZ.
Operations sur Z/nZ def de +, independance du representant choisi (compatibilite avec la relation d'equivalence), exemple table de Z/5Z. Structure de groupe additif heritee de celle de Z.
def de *, independance du representant choisi, exemple table de Z/5Z et de Z/4Z. Structure d'anneau unitaire commutatif heritee de celle de Z. Mais pas anneau integre (exemple de Z/4Z).

Elements inversibles: caracterisation par pgcd(a,n)=1.
Exemple pour n=15: 8 inversibles 1, 2, 4, 7, 8, 11, 13, 14
calcul de l'inverse avec Euclide etendu
Exemple: inverse de 11 mod 15.
Remarque, il n'est pas necessaire de calculer la colonne des coefficients de n.

Prop: Les inversibles de Z/nZ forment un groupe (multiplicatif) commutatif.
Definition: puissance g^k=g*...*g, ordre: plus petit entier>0 tel que g^ordre=1.
Theoreme de Lagrange: g^cardinal du groupe (fini) des inversibles=1 et ordre(g) divise cardinal du groupe.
Preuve en utilisant la commutativite.

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

Re: mat309 2019

Message par parisse » mar. oct. 08, 2019 2:19 pm

8/10:
Indicatrice d'Euler: definition.
Propriete si a inversible dans Z/nZ a^euler(n)=1
Calcul pour n=p premier, pour n=p^k, pour n=a*b avec a et b premiers entre eux en utilisant:
Interpretation dans Z/nZ des restes chinois: existence d'une bijection entre Z/abZ et Z/a*Z/b si a et b premiers entre eux.
Exemple Z/12Z -> Z/4Z*aZ/3Z, calcul des images de Z/12, on peut en deduire la bijection reciproque. Calcul d'un antecedent par la table et par l'identite de Bezout. La 2eme methode marche meme si a et b sont grands, pas la 1ere methode.
Formule euler(n) si on connait la decomposition de n en facteurs premiers.
Exemple calcul de euler(140). Verification que 3^48=1 mod 140 en faisant le calcul de la puissance par produit naif -> remarque sur l'inefficacite.
=========
Calcul efficace de a^n mod m.
Methode recursive: si n=0, 1; si n=1, a mod m, si n pair b=a^(n/2) mod m et on renvoie b*b mod m, si n impair b=a^((n-1)/2) et on renvoie b*b*a mod m.
Nombre d'etapes=nombre de bits de n. Cout d'une etape 1 ou 2 multiplications et 1 division.
Exemple calcul de 3^48 mod 140.
Methode iterative en calculant simultanement le developpement en base 2 de n
res<-1, a2k<- a
tantque n>0 faire
si n est impair, res <- res*a2k mod m
a2k <- a2k*a2k mod m
n <- quotient de n par 2
fintantque
renvoyer res

Meme nombre d'etapes, proportionnel a log2(n), a comparer avec n-1 produits par la methode naive.
Attention, il faut imperativement reduire mod m, sinon les entiers a multiplier deviennent gigantesques!
===========
Z/nZ quand n=p est premier: Z/pZ est un corps (anneau commutatif unitaire dont tous les elements sont inversibles sauf 0). Cette propriete va permettre de travailler comme avec Q et R. Exemple: factorisation des polynomes, un polynome de degre n a au plus n racines, ceci vient de l'absence de diviseurs de 0.

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

Re: mat309 2019

Message par parisse » mar. oct. 15, 2019 3:00 pm

Sur un corps Z/pZ on peut travailler comme sur les rationnels, reels ou complexes. Exemple: division euclidienne de 2 polynomes dans Z/7Z. Remarque: cas particulier de la division par X-alpha: algorithme de Horner.

Factorisation d'un polynome P a coeffs dans Z/pZ lorsqu'on en connait les racines. Au plus degre(P) racines.
Exemple X^(p-1)-1 a pour racines 1,...,p-1 mod p et se factorise comme (X-1)*...*(X-(p-1))
Verification avec p=5
Sur les complexes X^(p-1)-1 a p-1 racines qui sont les puissances d'une meme racine g=exp(2*i*pi/(p-1)). Est-ce encore vrai sur Z/pZ?
Exemple p=5 g=2, p=7 g=2 ne va pas, mais g=3 oui.
Theoreme (admis) Il existe au moins un generateur de Z/pZ*
Critere pour etre generateur: l'ordre de g ne doit pas etre un diviseur strict de p-1, donc g^((p-1)/p_k)!=1 pour tous les facteurs premiers p_k de p-1. Exemple p=5 et p=7.
Autres generateurs: si g^k est generateur alors (g^k)^n=1 si k*n est multiple de p-1. Si k et p-1 sont premiers entre eux, n est multiple de p-1. Exemple avec Z/5Z et Z/7Z
Il y a euler_phi(p-1) generateurs.
Algorithme de recherche: on teste le critere sur un a pris au hasard. La proba de succes est le produit des 1-1/p_k ou p_k facteur premier de p-1.

Resolution de a*x=b mod p
Resolution de a*x^2+b*x+c=0 mod p,
cas p=2 a part
formules avec le discriminant pour p impair, il faut savoir extraire une racine carree modulo p.
Exemple: carres dans Z/5Z et dans Z/7Z.
Il y a (p-1)/2 carres non nuls, car ils sont les carres de 2 entiers modulo p (x^2=y^2 a au plus, donc exactement, 2 solutions y et -y si y non nul). Si a=b^2 alors a^((p-1)/2)=b^(p-1)=1 mod p. Donc reciproquement aussi car l'equation a au plus (p-1)/2 solutions -> critere facilement verifiable avec l'algorithme de la puissance modulaire rapide.
Si p=3 mod 4, alors a^((p+1)/2)=a mod p donc b=a^((p+1)/4) mod p est une des 2 racines carrees de a.
Exemple Z/7Z
J'esquisserai rapidement comment on peut faire si p=1 mod 4 la prochaine fois...

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

Re: mat309 2019

Message par parisse » mar. nov. 05, 2019 3:53 pm

5/11:
Resolution de a*x=b mod n pour n non premier
1er cas si a premier avec n, solution unique, exemple 5x=1 mod 6
2eme cas sinon d=pgcd(a,n) doit diviser b pour qu'il y ait des solutions. On en trouve une avec Bezout, et les autres sont egales a un multiple de n/d pres. Il y a donc d solutions. exemple 2x=1 mod 6 et 2x=4 mod 6

En general une equation de degre p peut avoir plus de p solutions. Exemple calcul des carres mod 15, 1 a 4 racines carrees.

Test de primalite de Fermat, temoin et menteur de Fermat. Test reussi ne veut pas dire premier, test rate veut dire non premier.
Exemple 2 est un temoin de Fermat pour 15, par contre 4 est un menteur.
Il existe des entiers tels que a^(n-1)=1 mod n pour tout a premier avec n, ces entiers ont beaucoup de menteurs (cf. exo de TD) -> recherche d'un test meilleur.
Utilise le fait que x^2=1 mod p n'a que 2 solutions 1 et -1, et ce de maniere repetee, tant que l'exposant de a^(p-1)/2^ a un exposant pair.
Test de Miller-Rabin n-1=2^s*t avec t impair, on calcule a^t mod n, si 1 ou -1 test vrai, si (a^t)^2 mod n=-1 test vrai, etc. jusqu'a (a^t)^(2^(s-1)) mod n=-1. Sinon on renvoie faux.
Comme Fermat, faux signifie non premier, vrai ne prouve rien. Exemple 4 temoin de non primalite de 15.
Mieux que Fermat, car on peut montrer qu'il y a au plus n/4 "menteurs".
Si n renvoie vrai pour 20 valeurs de a, la probabilite que n ne soit pas premier est <=1/4^20 environ 10^-12.
Nombre d'etapes de Miller-Rabin: log2(n) (beaucoup plus petit que sqrt(n) le nombre de divisions a faire pour chercher un diviseur <=sqrt(n)).

Demain, je ferai RSA et j'attaquerai peut-etre l'algebre lineaire sur Z/pZ.

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

Re: mat309 2019

Message par parisse » mer. nov. 06, 2019 6:14 pm

RSA
1/ description de la fonction de codage et de decodage n=p*q, c et s inverses mod phi(n), b=powmod(a,c,n), proposition a=powmod(b,s,n) preuve si a est inversible mod n puis pour a quelconque
Exemple p=3, q=5, n=15, phi(n)=8, c=3 son inverse est lui-meme, a=2
2/ utilisation pour envoyer un message a un destinataire avec (n,c) publics. Autre utilisation possible pour authentifier le detenteur de la clef secrete.
3/ cout du cryptage log2(c)*log2(n)^2, la securite repose sur un cout de factorisation bien plus eleve (sqrt(n) divisions pour factorisation naive, exp(sqrt(ln(n)*ln(ln(n))) pour des methodes plus avancees. On peut etre tente de prendre c ou s petits pour accelerer le cryptage (ou le decryptage) mais attention aux attaques!
4/ 1ere attaque: si a est juste un caractere, on peut tester tous les caracteres^c et comparer
Solution: regrouper plusieurs codes de caracteres par ecriture en base + ajouter des caracteres aleatoires
5/ attaques arithmetique (pour culture generale, pas exigible en examen, sauf la 1ere)
* si on envoie un message a 3 destinataires avec la meme clef publique c=3, on peut retrouver le message par les restes chinois -> prendre c=257 ou mieux 65537
* si l'ordre de c dans le groupe des inversibles de Z/phi(n)Z vaut delta petit, alors en iterant delta-1 fois la fonction de cryptage sur b on retombe sur a. Exemple p=7 q=11 n=77 phi(n)=60, c=7 est d'ordre 4, verification avec a=2
* attaque par l'algorithme d'Euclide etendu, lorsque p<q<2p et s<1/3*n^(1/4) on montre que s apparait dans les suites u_n et v_n d'Euclide etendu, illustration a la machine avec s=65537

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

Re: mat309 2019

Message par parisse » mar. nov. 12, 2019 4:59 pm

Algebre lineaire sur Z/pZ
Motivation: on a vu avec RSA qu'il fallait regrouper plusieurs caracteres pour eviter l'attaque par analyse frequentielle, plutot que de le faire par ecriture en base 256, on va travailler avec des vecteurs. On peut alors calculer A*v+b, ou A est une matrice et faire les calculs mod p, il faut alors savoir resoudre des systemes mod p pour decrypter (en dimension 1 c'est un code affine, inversible si a est inversible mod p). On prefere les calculs mod p pour eviter d'avoir des rationnels avec des grands numerateurs/denominateurs (calculs couteux).

Resolution de systemes lineaires: matrice associee avec second membre, sans second membre, systemes equivalents en faisant une combinaison lineaire de lignes/equations.
Algorithme du pivot de Gauss (cf cours en ligne)
Forme possible des matrices reduites, cas generique ou il n'y a pas de colonne avec uniquement des 0 a partir de la ligne du pivot. Si cela se produit la "diagonale" separant les 0 des coefficients quelconques se decale de 1.
Exemple: 2x+3y+z=5, -2x+y-z=1, 3x+2y+z=0 dans R puis dans Z/5Z puis dans Z/2Z.
Puis resolution en partant de la derniere equation et en remontant vers le haut.

Structure de l'ensemble des solutions.
Systeme homogene associe: stabilite par + et * de l'ensemble des solutions -> sous-espace vectoriel de K^n.
Rappel def espace vectoriel: groupe commutatif + loi de multiplication respectant distributivite et a*(b*v)=(a*b)*v et 1*v=v. Prop (laissee a titre d'exercice) : stabilite d'un sous-ensemble par + et * implique espace vectoriel
Exemple: homogene associe a l'exemple ci-dessus. Ensemble reduit au vecteur nul pour R ou Z/5Z. Pour Z/2Z, z*[1,1,1] pour z quelconque, en fait 2 valeurs possibles pour z.
Rappel def famille libre, famille generatrice. Notation Vect(v_1,..,v_n). Definition: espace vectoriel de dim finie s'il existe une famille generatrice avec un nombre fini d'elements.

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

Re: mat309 2019

Message par parisse » mar. nov. 19, 2019 3:26 pm

Exemples d'espaces vectoriels sur Z/pZ: Z/pZ^n, P_n=polynomes de degre strictement inferieurs a n, matrices
Remarque: les entiers naturels < p^d sont en bijection avec Z/pZ^n mais l'addition et la multiplication n'est pas compatible

Famille libre engendrant le meme sous-espace qu'une famille donnee, cas d'une famille generatrice finie de V -> base.
Nombre d'elements=p^n (c'est la principale propriete qui differe de ce qui se passe si le corps est R)
Ceci prouve que toutes les bases ont meme cardinal qui est la dimension, et on peut montrer que les familles libres ont au plus n elements, les familles generatrices au moins n en comptant les elements.
Exemple: extraction d'une base de {1,x,1+x^2,x^2}

Une base permet de se ramener les questions d'algebre lineaire a des calculs de pivot de Gauss.

Exemple: v1=[1,2,3],v2=[4,2,5],v3=[0,1,2] modulo 5 -> Gauss (combinaison lineaire de lignes=combinaison lineaire de vecteurs, donc engendre le meme sous espace)
{v1,v2-4v1} engendre le meme sous-espace vectoriel (et la famille n'est pas libre).
Conclusion differente si p=7.

Applications lineaires: compatible avec + et .
Exemples phi((x,y))=(x+y,x-y) (ecrit en colonne au tableau)
phi(P)=x*P de P_2 dans P_3
Caracterise par la valeur des phi(v_j) d'une base {v_j} de V dans une base {w_i} de W. Matrice A=(a_{ij}) colonne j les coordonees des phi(v_j)
phi(v) a pour coordonnees (en colonne) A*vecteur colonne des coordonnees de v
Exemple: calcul de A dans les 2 cas.

Def Ker(phi), verification sous-espace vectoriel
Im(phi), verification sous-espace
Exemple: calcul de Ker(phi) pour les deux exemples, en distinguant p=2 et p!=2 dans le 1er exemple. Calcul de Im(phi) pour le 1er exemple.

Proposition dim(Ker(phi))+dim(Im(phi))=dim espace de depart.

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

Re: mat309 2019

Message par parisse » mar. nov. 26, 2019 3:54 pm

26/11:
phi : V -> W lineaire, V et W de dimensions finies n et m
retour sur une preuve par Gauss de dim Ker(phi)+dim Im(phi)=dim espace de depart
Exemple: calcul simultane de Ker/Im pour M:=[[1,1,1],[1,2,3]] modulo 5 en faisant Gauss sur la transposee de M (et en tracant de qui les lignes de la matrice sont des images).
Exemple 2: reste de P par X^2+1 des polynomes de degre < 3 vers les polynomes de degre < 2

Ker phi={0} et injectivite, Im phi=espace d'arrivee et surjectivite, bijectivite, dans ce cas dim V= dim W. Reciproquement il suffit que Ker phi={0} ou Im phi=W
Si V=W on parle d'endomorphisme.
Calcul matriciel: produit de matrices et composition d'applications lineaires, associatif mais pas commutatif. Inverse de matrice et bijection reciproque.
Exemple de calcul inverse de A=[[1,2],[3,4]] modulo 5 par le pivot de Gauss.

Applications de l'algebre lineaire dans Z/pZ
1ere application cryptographie de Hill
A matrice tenue secrete (clef de cryptage)
v dans (Z/pZ)^n message en clair -> w=A*v message crypte
Si A inversible on retrouve v en calculant A^-1*w
Exemple avec la matrice A ci-dessus
En realite, on travaille avec p plus grand (pour pouvoir coder tous les caracteres, par ex. p=257 pour le codage ascii, ou p=37 26 lettres + espace + 10 chiffres), et n plus grand que 2

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

Re: mat309 2019

Message par parisse » mar. déc. 03, 2019 2:35 pm

Codes correcteurs.
Symbole: ici element Z/2Z, donnee (Z/2Z)^k, ajout d'informations complementaires (n-k)-> message dans (Z/2Z)^n
Exemple bit de parite (k=7,n=8), code de repetition (k=1,n=3)
Detection d'erreur != correction d'erreur, possible pour le code de repetition (1 erreur par vote a la majorite)
phi: Z/2Z^k -> Z/2Z^n doit etre injective, on veut aussi pouvoir verifier facilement que w est dans Im(phi) et si oui determiner v tel que phi(v)=w
Les applications lineaires sont interessantes pour ca -> code lineaire. En particulier si on a un bloc identite de taille k comme k premieres lignes de la matrice -> code systematique. Exemples bit de parite, code de repetition, une matrice 7,4
Matrice de controle H. Syndrome Hw. Si Hw=0, pas d'erreur detectee. Comment corriger w si Hw!=0? On souhaite corriger le moins de bits possible (erreur la plus probable).
Quantification par la distance de Hamming. Verification des proprietes de distance mathematique.
Distance du code, cas d'un code lineaire.
Enonce de la borne de Singleton distance code<=n-k+1
Enonce de nombre t d'erreurs corrigeables au plus proche verifie 2t+1<=distance du code.
Je donnerai les preuves la prochaine fois.
Exemples.

Répondre