cours 2021/2022

Modérateur : xcasadmin

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

cours 2021/2022

Message par parisse » jeu. sept. 02, 2021 3:17 pm

cours du 2/9:
Présentation de l'UE, cf. https://www-fourier.univ-grenoble-alpes ... cours1.pdf
Sur la partie motivations, j'ai traité: crypto de Cesar, monoalphabétique, attaques (nombre de clefs, fréquentielle).
a->a+clef mod n,
a->a*clef mod n : on verra que cela nécessite gcd(a,n)==1
a->a^clef mod n ? c'est RSA si n=p*q et pgcd(clef,(p-1)*(q-1))=1
Exemple RSA avec p et q grands qui a buggué en cours:
session Xcas
J'ai juste dit un mot sur les codes (il me restait 10 minutes).

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

Re: cours 2021/2022

Message par parisse » mer. sept. 08, 2021 9:13 am

8/9:
Division euclidienne
Ecriture en base b: exemple 1234 en base 10
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.
session Xcas
Exemple 0o2232 en base 8.
Reciproque: algorithme de Horner.
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 0o2232 en base 8, retour en base 10
session Xcas

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 : 5383
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2021/2022

Message par parisse » mer. sept. 15, 2021 4:00 pm

cours 3/14 du 15 septembre:
* Rappel: si a et b ont le meme nombre de chiffres n, cout du calcul du produit 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 session .
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, remplacer 4 * par 3 * d'entiers de taille n pour multiplier des entiers de taille 2n
* Division euclidienne: idee de la justification de l'algorithme de la potence.
Cout de a (n+1 chiffres) divise par b (m+1 chiffres) proportionnel a difference nombre de chiffres*nombre de chiffres de b, cout maximal si b a a peu pres la moitie du nombre de chiffres de a.
* 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. Tout le monde divise 1. b divise a non nul entraine b<=a
La divisibilite est une relation d'ordre (def de relation d'ordre donnee), mais partiel contrairement a <= sur R

* Def du PGCD pour 2 entiers naturels (a,b) different de (0,0) comme le plus grand element commun aux listes des diviseurs de a et b.
Extension si b=0.
Exemple avec 14 et 10, inefficace pour de grands entiers.
Propriete PGCD(a,b)=PGCD(b,reste de a par b)
Exemple d'application a 14 et 10,
Algorithme en langage naturel recursif et iteratif. Cout en n^2 (admis).

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

Re: cours 2021/2022

Message par parisse » mer. sept. 22, 2021 7:07 pm

Cours du 22/9 (4/14)
Algorithme d'Euclide: programme en iteratif (voir session a la fin)
Exemple a la main: 255 et 35, calcul fait en base 10 puis en base 2 (a cette occasion algorithme de la potence pour la division euclidienne en base 2)

Identite de Bezout et algorithme d'Euclide etendu:
2 exemples 255 et 35 ; 222 et 19
Cas general: Definition des suites r_n,u_n, v_n et preuve de l'invariant de boucle r_n=u_n*a+v_n*b
algorithme en langage naturel et une implementation avec Xcas en syntaxe Python.

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

Def de nombres premiers entre eux, exemple 2,3 contre-exemple 4,6.
Il existe alors u et v tels que a*u+b*v=1
Consequence de Bezout:
* a/pgcd et b/pgcd sont premiers entre eux
* pgcd(ac,bc)=pgcd(a,b)*c
Application si c=2 : Algorithme du PGCD binaire sans division, exemple fait a la main en base 2 pour 255 et 35.

Autres consequences de Bezout:
* Lemme de Gauss: a|bc et gcd(a,b)=1 => a|c
* a|c et b|c et gcd(a,b)=1 => a*b |c

session Xcas

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

Re: cours 2021/2022

Message par parisse » mer. sept. 29, 2021 9:05 pm

Cours 29/9 (5/14)
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.
Exemples 5x+7y=3, 10x+14y=3, 10x+14y=4

Restes chinois: a,b premiers entre eux donnes, alpha et beta quelconque, il existe gamma tel que le reste gamma par a soit alpha et le reste de gamma par b soit beta. Ensemble des solutions=solution particuliere+multiple de a*b, unicite de la solution dans [0,a*b[
Exemple reste par 5 =2 et reste par 7 =5.

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, comme produit de nombre premiers.
(je n'ai pas encore fait l'unicite a permutation pres)
Algorithme de factorisation recursif selon la preuve.
Exemple 27

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

Re: cours 2021/2022

Message par parisse » mer. oct. 06, 2021 5:07 pm

cours du 6/10 (6/14)
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
Exemples

Le PGCD de 2 entiers est le produit des facteurs communs a la puissance le min des multiplicites.
Exemple.
Utiliser uniquement si on connait la factorisation des 2 entiers, sinon Euclide est bien plus rapide.

Algorithme de factorisation naif
session Xcas
Discussion sur le nombre d'iterations en sqrt(n) vs l'algo d'Euclide en log(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.
Division euclidienne de polynomes. Exemple avec un reste non nul et avec un reste nul.
2 exemples de calcul de PGCD (defini a une constante multiplicative pres): x^3-x^2+x-1 et x^2-1, x^3+8 et x^2-2, polynomes premiers entre eux.
Bezout sur cet exemple.
Les nombres premiers dans Z correspondent aux facteurs irreductibles dans les polynomes et on a un theoreme de factorisation analogue.

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

Re: cours 2021/2022

Message par parisse » lun. oct. 11, 2021 4:19 pm

cours du 11/10 (7/14)
Exemple d'application de Bezout sur les polynomes : decomposition en elements simples et calcul d'une primitive de 1/(x^3+8)

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.

Def de l'indicatrice d'Euler.

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.
Exemple dans Z/5 et Z/4
Theoreme de Lagrange: g^cardinal du groupe (fini) des inversibles=1 et ordre(g) divise cardinal du groupe.
Preuve la prochaine fois

Répondre