cours 2021/2022

Modérateur : xcasadmin

Répondre
parisse
Messages : 5417
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 : 5417
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 : 5417
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 : 5417
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 : 5417
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 : 5417
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 : 5417
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

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

Re: cours 2021/2022

Message par parisse » mer. oct. 20, 2021 4:32 pm

Preuve de Lagrange et de ordre(n) divise euler(n).
Exemple Z/4Z et Z/5Z.
Application a^m[n]=a^irem(m,euler(n)) [n], exemple 2^2021 mod 5.
Calcul de euler(n) pour n=p premier, pour n=p^k, pour n=a*b avec a et b premiers entre eux.
exemple n=15 et liste des inversibles de Z/15Z.
Formule lorsqu'on connait la factorisation de n, exemple n=300.
Exponentiation rapide: methode recursive et methode iterative, exemple calcul de 5^10 mod 7 par les 2 methodes.
ALgorithmes
session Xcas

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

Re: cours 2021/2022

Message par parisse » lun. oct. 25, 2021 6:09 pm

cours 9/14:
Interpretation des restes chinois Z/nZ isomorphe a Z/aZ*Z/bZ si n=a*b avec a et b premiers entre eux.
Exemple Z/15Z
Resolution d'equation du 1er degre a*x=b dans Z/nZ. Cas a inversible, cas ou a est non inversible, on peut avoir 0 ou plusieurs solution, exemples modulo 15.

Cas ou n=p est premier.
Un polynome de degre n a au plus n racines (idee de preuve).
Resolution de l'equation du 1er degre.
Degre 2: cas de x^2=a.
Exemple p=5 et 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.
2nd degre general: formules avec Delta pour p impair. Exemple x^2+x+1=0 mod 11, x^2+x+2=0 mod 11.

Definition de generateur.
Exemple p=5 et p=7.
Thm admis: existence d'un generateur.
Suite le 17 novembre.

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

Re: cours 2021/2022

Message par parisse » mer. nov. 17, 2021 6:55 pm

cours 10/14:
Rappel def generateur Exemples Z/5Z et 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
Si g generateur, les autres generateurs sont des puissances de g premieres avec p-1, il y en a phi(p-1).
Recherche d'un generateur: algorithme (si on dispose d'un algo de factorisation d'entiers)
viewtopic.php?f=29&t=2745

Tests de primalite: par factorisation naive: trop lent pour generer des clefs RSA.
Test 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.
viewtopic.php?f=49&t=2582
-> 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.

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

Re: cours 2021/2022

Message par parisse » mer. nov. 24, 2021 5:37 pm

24/11:
Exemple de temoin de Miller-Rabin qui est un menteur de Fermat: 5 pour 561.
Programmes pour Miller-Rabin viewtopic.php?f=49&t=2582

RSA. Principe. Exemple avec p=5 et q=11. Proposition justifiant le cryptage/decryptage et preuve. Parametres secrets et publics. Utilisation pour signature.
Exemple session Xcas
La securite repose sur la difficulte a factoriser des grands entiers, mais il ne faut pas negliger les autres attaques possibles. Exemples d'attaques: dictionnaire, mauvais choix de p et q (par exemple nextprime d'une puissance de 10). Il ne faut pas utiliser un meme n pour 2 paires de clefs, car avec une paire de clef on peut arriver a determiner phi(n) et n et phi(n) permettent de determiner p et q.
viewtopic.php?f=49&t=2585

Efficacite du cryptage: choix de c=3 (a deconseiller, car il ne faut pas envoyer le meme message a 3 destinataires ayant c=3 comme clef publique!), c=257, c=65537.

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

Re: cours 2021/2022

Message par parisse » lun. nov. 29, 2021 5:21 pm

Cours du 29/11 (12/14):
Attaque sur RSA par les restes chinois viewtopic.php?f=49&t=2588. Ordre de grandeur du temps de cryptage/decryptage vs factorisation naive pour rsa 2048 bits.

Algebre lineaire sur Z/pZ
Motivation: crypto a clef secrete en regroupant plusieurs caracteres en un vecteur puis multiplication par une matrice, modulo p. Exemple dans Z/37Z avec une matrice 2x2. Decryptage=resolution de systeme lineaire. Il faut une solution unique.

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
session Xcas

Exemple a la main: 2x+3y+z=5, -2x+y-z=1, 3x+2y+z=0 dans Z/5Z puis dans Z/2Z.
Puis resolution en partant de la derniere equation et en remontant vers le haut. Pour avoir une solution unique il faut des elements non nuls sur la diagonale

Structure de l'ensemble des solutions dans le cas homogene:
Stabilite par + et * de l'ensemble des solutions -> sous-espace vectoriel de K^n.

Def d'espace vectoriel sur K=Z/pZ. Exemple Z/pZ^d, polynomes de degre<d, matrices.

Répondre