cours 2020/21

Modérateur : xcasadmin

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

cours 2020/21

Message par parisse » ven. sept. 11, 2020 3:21 pm

Mercredi 9/9:
Diaporama https://www-fourier.univ-grenoble-alpes ... cours1.pdf
jusqu'a detection des erreurs non compris
+
debut d'ecriture en base

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

Re: cours 2020/21

Message par parisse » mar. sept. 15, 2020 2:38 pm

Mardi 15/9:
Ecriture en base b: exemple en base 10, observation un nombre a 4 chiffres est entre 10^3 et 10^4.
Cas general: si a s'ecrit avec n+1 chiffres alors b^n<=a<=b^(n+1)-1<b^(n+1), justification avec suite geometrique. Renvoi au poly pour l'unicite de l'ecriture.
Existence de l'ecriture: algorithme, donne en langage naturel puis programme en Xcas.
Exemple 1602 en base 16.
Reciproque: algorithme de Horner, donne en langage naturel.
Nombre d'iterations=taille de l'entier. Mais calculer le cout n'est pas encore possible a cause des operations sur les grands entiers dans une iteration.
Exemple 0x642 retour en base 10

Necessite de savoir faire des operations sur les nombres ecrits en base pour pouvoir calculer avec des grands entiers.
Cas de + et -: comme les polynomes mais avec retenues, exemple en base 10 et 2. Cout max de la taille des 2 entiers, cout optimal car la taille obtenue est <=max(taille des 2 entiers)+1 (retenue eventuelle)
Cas de *: analogie avec les polynomes, mais il faut tenir compte des retenues. Pour les polynomes le cout est le produit du nombre de coefficients (* 1 multiplication + 1 addition).

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

Re: cours 2020/21

Message par parisse » mer. sept. 16, 2020 4:41 pm

Mercredi 16/9 (cours 3/16)
* Exemple de multiplication en base 2 (11x13)
* nombre de chiffres de a*b=nombre de chiffres de a + nombre de chiffres de b ou -1, cout de l'algorithme produit du nombre de chiffres
* si a et b ont le meme nombre de chiffres n, cout propotionnel a n^2, taille du resultat 2*n. Si on multiplie le nombre de chiffres par 2, le temps de calcul est multiplie par 4.
Illustration avec MicroPython viewtopic.php?f=49&t=2543
Avec Xcas c'est plutot multiplie par 2, et avec CPython par 3. Il existe des algorithmes plus efficaces!
Idee de l'algorithme de Karatsuba sur les polynomes, utilise par CPython pour les entiers.
* A retenir absolument (voir § du poly)
* Division euclidienne: idee de la justification de l'algorithme de la potence. Exemple de division euclidienne en base 2.
Cout de a (n+1 chiffres) divise par b (m+1 chiffres) proportionnel a (n-m)*(m) (en fait c'est plutot (n-m+1)*(m+1)), cout maximal si m est proche de n/2.
* Cas des entiers relatifs: on se ramene aux entiers naturels avec des regles de signe.
* Def de divisibilite. Ne depend pas du signe -> on se ramene au cas des entiers positifs.
1 divise tout le monde, le seul diviseur de 1 est 1.
La divisibilite est une relation d'ordre (def de relation d'ordre donnee), mais partiel (contrairement a <= sur R, j'y reviendrai rapidement lors du prochain cours le 22/9).

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

Re: cours 2020/21

Message par parisse » mar. sept. 22, 2020 2:14 pm

Mardi 22/9 (cours 4/16)
Def du PGCD pour 2 entiers naturels (a,b) different de (0,0) comme le plus grand element de l'intersection des listes des diviseurs de a et b.
Exemple avec 10 et 6, inefficace pour de grands entiers.
Propriete PGCD(a,b)=PGCD(b,a-b*q)

Algorithme d'Euclide
Exemple 245, 55
Algorithme en langage naturel recursif et iteratif, illustration sur machine.
Nombre d'etapes <=2*nombre de bits(b) car a une iteration soit le reste est <=b/2 soit le quotient suivant est 1 et le reste suivant est b-r<b/2.
Cout en O(n^2) admis (demo dans poly).
Illustration: le programme recursif atteint vite ses limites si on prend a et b deux nombres de Fibonacci successifs.

Algorithme d'Euclide etendu et identite de Bezout : 2 exemples (dont 245 et 55).
Definition des suites r_n,u_n, v_n et preuve de l'invariant de boucle r_n=u_n*a+v_n*b

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

Re: cours 2020/21

Message par parisse » mer. sept. 23, 2020 4:04 pm

cours du 23/9 (5/16)
Euclide etendu: algorithme en langage naturel et une implementation avec Xcas en syntaxe Python

Divisibilite, PGCD et Bezout pour des entiers relatifs : il suffit d'ajuster les signes.

Def de nombres premiers entre eux, exemple 2,3 contre-exemple 6,15
Caracterisation par a*u+b*v=1
a/pgcd et b/pgcd sont premiers entre eux
a|bc et gcd(a,b)=1 => a|c
a|c et b|c et gcd(a,b)=1 => a*b |c

Resolution de a*x+b*y=c sur un exemple de a,b,c puis cas general: condition pour avoir des solutions PGCD(a,b) divise c, solution particuliere et solution generale.

Restes chinois: a,b premiers entre eux donnes, alpha et beta quelconque, il existe gamma tel que gamma-alpha divisible par a et gamma-beta divisible par b. Ensemble des solutions=solution particuliere+multiple de a*b
Exemple

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

Re: cours 2020/21

Message par parisse » mar. sept. 29, 2020 4:14 pm

cours du 29/9 (6/16)
Definition de nombre premier: 2 diviseurs distincts 1 et lui-meme (1 n'est pas premier).
Prop: p premier, a entier, alors soit p divise a, soit a et p sont premiers entre eux
Prop: Si p premier divise un produit de facteurs, il divise l'un d'eux.
(il peut diviser les 2!) Attention l'hypothese p premier est essentielle. Exemple/contre-exemple

Theoreme: tout entier n>=2 admet une decomposition, unique a ordre pres, comme produit de nombre premiers.
Exemple 60
Prop: si d divise n alors les facteurs premiers de d sont des facteurs premiers de n avec une multiplicite inferieure
Exemple 60|600
Liste des diviseurs d'un entier dont on connait la factorisation, nombre de diviseurs.
Exemple 60
Le PGCD de 2 entiers est le produit des facteurs communs a la puissance le min des multiplicites.

Algorithme de factorisation naif
viewtopic.php?f=49&t=2556
Discussion sur le nombre d'iterations en sqrt(n) vs l'algo d'Euclide en ln(n)^2, pour des entiers ayant une cinquantaine de chiffres.

Les resultats arithmetiques sur les entiers peuvent se generaliser aux polynomes a coefficients reels, rationnels ou complexes. Survol rapide des proprietes d'un anneau euclidien (je n'ai pas eu le temps de montrer Euclide pour le pgcd de polynomes ni Bezout pour decomposer des fractions viewtopic.php?f=49&t=2554, je le ferai rapidement la prochaine fois)

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

Re: cours 2020/21

Message par parisse » mar. oct. 06, 2020 1:17 pm

Illustration avec des polynomes: algo d'Euclide, simplification de fractions de polynomes, Bezout et debut de calcul de primitive. J'ai insiste sur le fait que les questions a l'examen portant sur les polynomes auraient peu de poids et qu'il fallait en priorite travailler les entiers

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.
Diviseurs de 0 (exemple de Z/4Z).

Elements inversibles: caracterisation par pgcd(a,n)=1.
calcul de l'inverse avec Euclide etendu
Exemple: inverse de 21 mod 38.
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: cours 2020/21

Message par parisse » mar. oct. 13, 2020 2:37 pm

cours du 13 octobre (8/16)
Def de l'indicatrice d'Euler. Lagrange: 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/15Z -> Z/3Z*aZ/5Z, calcul des images de Z/15, on peut en deduire la bijection reciproque. Calcul d'un antecedent par la table vs par l'identite de Bezout. La 2eme methode marche meme si a et b sont grands, pas la 1ere methode (par exemple si a=2^100). Exemple calcul de l'antecedent de (1,2).

On peut donc calculer euler(n) si on connait la decomposition de n en facteurs premiers.
Exemple calcul de euler(140).

Verification : a-t-on 3^48=1 mod 140 ?
Observation: Faire le calcul des 47 multiplications est fastidieux.
On peut utiliser les proprietes de la puissance 3^48=(3^24)^2=((3^12)^2)^2=(((3^6)^2)^2)^2=((((3^3)^2)^2)^2)^2
3^3=27, on calcule 27^2 mod 140=29 puis 29^2 mod 140=1 et ensuite 1^2=1 donc OK. On verra la prochaine fois un algorithme de ce type pour calculer a^n mod m.

On a donc 3^12=1 mod 140. Il n'est pas necessaire d'aller jusqu'a la puissance 48 pour trouver 1.
Def: ordre d'un element inversible. Exemple ordre de 2 et 3 dans Z/7Z.
Propriete: l'ordre d'un element divise euler(n).

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

Re: cours 2020/21

Message par parisse » mar. oct. 20, 2020 2:32 pm

Cours du 20/10:
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^12 mod 7.

Principe de l'algorithme iteratif, programmation des deux algorithmes viewtopic.php?f=49&t=2559.

Z/nZ quand n=p est premier: Z/pZ est un corps : tous les elements sont inversibles sauf ). Cette propriete va permettre de travailler comme avec Q et R, mais efficacement et exactement avec un ordinateur. Exemple: un polynome de degre n a au plus n racines, ceci vient de l'absence de diviseurs de 0. Par exemple X^4-1 dans Z/5Z.

Element d'ordre maximal p-1=generateur.
Exemples: Z/5Z 2 est d'ordre 4, Z/7Z 2 est d'ordre 3 et pas 6, 3 est d'ordre 6.
Theoreme admis: existence d'un generateur g.
Les autres generateurs sont des puissances de g premieres avec p-1, il y en a phi(p-1).
Exemple Z/7Z.
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=7

Recherche d'un generateur: au hasard, exemple p=103.

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

Re: cours 2020/21

Message par parisse » mar. nov. 03, 2020 4:09 pm

cours en visio du 3/11:
resolution d'equation du 1er et 2eme degre dans Z/pZ.
1er degre: Exemple modulo 13.
Carres de Z/pZ, exemple p=7. Critere pour etre un carre dans Z/pZ. Exemple p=7. Recherche de racines carrees dans Z/pZ, cas p=3 mod 4 a^((p+1)/4)avec la puissance rapide, cas p=1 mod 4 algo naif. Exemples et programme correspondant.
2nd degre: formules avec Delta pour p impair.
exemple x^2+3*x+5=0 mod 103.

Tests de primalite: par factorisation naive: trop lent pour generer des clefs RSA.
debut du test de Fermat.

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

Re: cours 2020/21

Message par parisse » mar. nov. 17, 2020 4:10 pm

Illustrations machine du cours: viewtopic.php?f=49&t=2582

Rappel petit theoreme de Fermat.
Temoin de non primalite de Fermat.
Menteur de Fermat, exemple avec 23*7
Certains entiers ont beaucoup de menteurs, par ex. 561 tous les entiers premiers avec 561.
-> on veut un test plus efficace.

Test de Miller-Rabin, temoin de MR, menteur de MR en nombre au plus n/4 (admis).
-> si on fait 20 tests qui passent, il y a moins d'une chance sur 10^12 de declarer premier un nombre qui ne l'est pas.
Exemple 561, programmation de MR.

RSA: n=p*q, c et s inverses mod phi(n), a^c=b mod n, b^s=a mod n.
exemple jouet p=7, q=11, c=7.
autre exemple a la machine avec p et q obtenus par nextprime.
Si on connait n et phi(n), on peut factoriser n.

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

Re: cours 2020/21

Message par parisse » mer. nov. 18, 2020 4:11 pm

RSA: public n,c; prive: p,q,phi(n), s tel que c*s=1 mod phi(n)
Exemple de cryptage d'un message (chaine de caracteres->numerisation via code ASCII->cryptage->decryptage->chaine de caracteres). Attention a l'attaque frequentielle ou du dictionnaire si on numerise les caracteres 1 par 1 et qu'on les crypte individuellement. On peut y remedier en regroupant les caracteres par blocs (ecriture en base 256).

RSA permet de s'authentifier en utilisant sa clef secrete, tout le monde peut verifier la signature en utilisant la clef publique.

Attaque sur la factorisation de n: il ne faut pas choisir par exemple p et q deux nombres premiers consecutifs, ou des nombres de la forme nextprime(10^k), il faut de l'aleatoire pour ne pas pouvoir deviner p et q.
Clef publique c=3: mauvais choix si on veut envoyer a 3 destinataires differents ayant des cles publiques (n1,3), (n2,3), (n3,3): on retrouve le message par les restes chinois et extraction de racine cubique dans les entiers.
Mieux vaut prendre c=257 ou c=65537 qui sont premiers et ont beaucoup de 0 dans leur ecriture en base 2.
Interet d'avoir beaucoup de 0 dans l'ecriture de c en base 2 pour que le cryptage soit plus efficace sur une puce ayant peu de puissance de calcul (par exemple puce de carte bancaire).

Illustrations: viewtopic.php?f=49&t=2589,
viewtopic.php?f=49&t=2588

D'autres illustrations que je n'ai pas eu le temps de detailler sont disponibles :
viewforum.php?f=49

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

Re: cours 2020/21

Message par parisse » mar. nov. 24, 2020 2:41 pm

24/11:
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, ou A est une matrice et faire les calculs mod p, il faut alors savoir resoudre des systemes mod p pour decrypter. 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.
Exemple: homogene associe a l'exemple ci-dessus. Pour Z/2Z, z*[1,1,1] pour z quelconque, en fait 2 valeurs possibles pour z.

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

Re: cours 2020/21

Message par parisse » mar. déc. 01, 2020 2:26 pm

1er decembre:
Exemples d'espaces vectoriels sur Z/pZ: Z/pZ^n, P_n=polynomes de degre strictement inferieurs a n, matrices

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: Vect(v1,v2,v3) avec v1=[1,4,7],v2=[2,5,8],v3=[3,6,-2] modulo 11 -> Gauss (combinaison lineaire de lignes=combinaison lineaire de vecteurs, donc engendre le meme sous espace)
{v1,v2-2v1} engendre le meme sous-espace vectoriel (et la famille n'est pas libre).

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. Verification de phi(v) et A*vecteur colonne des coords de v dans le cas polynome

Def Ker(phi), verification sous-espace vectoriel
Calcul dans le cas phi((x,y))=(x+y,x-y) il faut distinguer p=2 et p!=2

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

Re: cours 2020/21

Message par parisse » mar. déc. 08, 2020 2:23 pm

Si Ker(phi)={0} alors phi est injective

Definition de Im(phi), sev de W.
Exemple de calcul d'une base pour phi de matrice [[1,4,0],[2,5,1],[3,-1,2]] mod 7 en faisant Gauss sur la transposee. Si on ajoute en derniere colonne les symboles des elements de la base canoniques, le calcul donne aussi une base de Ker(phi) (lignes nulles). Comme le nombre de lignes = nombre de lignes non nulles + lignes nulles de la fin de la reduction cela prouve le theoreme du rang. La preuve se generalise.

Exemple 2: phi=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,
Si V=W on parle d'endomorphisme. Il suffit alors que Ker phi={0} (ou Im phi=W)
Exemple [[1,4,0],[2,5,2],[3,-1,2]] mod 7, calcul de Ker(phi) en resolvant le systeme (i.e. sans transposer la matrice).

Calcul matriciel: produit de matrices et composition d'applications lineaires. 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
Pour pouvoir coder tous les caracteres, il faut prendre p=257 pour le codage ascii, ou p=37 26 lettres + espace + 10 chiffres), et n plus grand que 2. Le nombre de clefs possibles, i.e. de matrices possibles est p^(n^2) (en fait un peu moins car elles ne sont pas toutes inversibles).

Répondre