mat309 2019

Forum pour les etudiants de l'UJF utilisant Xcas.

Modérateur : xcasadmin

parisse
Messages : 4842
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 : 4842
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 : 4842
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 : 4842
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 : 4842
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 : 4842
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 : 4842
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 : 4842
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.

Répondre