option C 2016/17

Utilisation à l'épreuve de modélisation de l'agrégation de mathématiques

Modérateur : xcasadmin

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

option C 2016/17

Message par parisse » jeu. sept. 08, 2016 9:07 am

7/9:

Chapitre I: representation des objets mathematiques, algorithmes fondementaux.
1/ entiers machine, precision limitee. Entiers long, lien avec les polynomes.
2/ cout des operations de base + - * sur les entiers (algorithme naif) et comparaison avec la taille du resultat, il existe des algorithmes meilleurs pour la multiplication (ce qu'on peut deviner vu la taille du résultat),
3/ division en O(n^2) + precisement a=b*q+r en O(#b*#q) ou #b=nombre de bits de b, le calcul des bits de q en base 2 a un cout nul
a1/ PGCD binaire: si a ou b est nul on renvoie l'autre, si a et b sont pairs pgcd(a,b)=2*pgcd(a/2,b/2), si a est pair b impair, pgcd(a,b)=pgcd(a/2,b), si les 2 sont impairs pgcd(a,b)=pgcd((a-b)/2,min(a,b)) temps en O(n^2) pour entiers longs de taille n,
a2/ PGCD classique: pour montrer la complexite en O(n^2) il faut observer que dans une division euclidienne #q=#a-#b+1, donc si r0=a, r1=b et r_{k+2}=r_k-q_n*r_{k+1} alors on a
somme O(#r_{k+1}*#q) majoree par O(#b)*somme(O(#r_k-#r_{k+1}+1)) <= O(#a*#b) + O(#b)*nombre d'etapes d'Euclide.
Il faut donc majorer le nombre d'etapes N, ce qui peut se faire en observant que r_k>=r_{k+1}+r_{k+2} (si a>=b), donc r_0=a est >= au terme d'indice N de la suite de Fibonacci F_0=0 et F_1=1 (<=dernier reste non nul r_N). Comme F_N est equivalent a une constante * nombre d'or^N on obtient bien la majoration annoncee.
b/ identite de Bezout classique pour a>=b>0 a*u+b*v=pgcd(a,b) calcul de u et v avec u_0=1, u_1=0, v_0=0, v_1=1, r_0=a, r_1=b.
Pour verifier
a*u_n+b*v_n=r_n
on definit u_n et v_n par recurrence
u_(n+2)=u_n-q_n*u_(n+1)
v_(n+2)=v_n-q_n*v_(n+1)
ou r_(n+2)=r_n-q_n*u_(n+1)
On a par récurrence v_n*r_(n+1)-v_(n+1)*r_n=(-1)^(n+1)*a, et |v_n| strictement croissante, au cran apres Bezout, on a v_n*pgcd(a,b)=a d'ou la suite |v_n| est majoree par a et |v|<a. De meme on prouve que |u|<b.
Complexite en O(taille(max(a,b))^2), se montre comme pour Euclide classique, en majorant les |v_k| par a.
Remarque: on peut calculer une seule des suites u_n ou v_n, l'autre coefficient de Bezout se deduit avec a*u+b*v=pgcd(a,b).

Applications:
-> inverse modulaire inv(a mod n) s'obtient par Bezout a*u+v*n=1
Pour l'inverse modulaire on n'a pas besoin de calculer v.
-> restes chinois on cherche c=alpha mod a et =beta mod b, avec a et b premiers entre eux
donc alpha+a*U=beta+b*V et a*U-b*V=beta-alpha
donc on part de a*u+b*v=1, on pose U=(beta-alpha)*u et c=alpha+U*a
Dans les applications en calcul modulaire, a est souvent un grand entier, produit de n nombres premiers et b un entier court nombre premier. On a alors interet a faire les calculs intermediaires de U modulo b (comme ensuite on multiplie U par a, cela ne change pas le fait que c est solution).
U=irem((beta-irem(alpha,b))*u,b)
Ainsi le calcul de U est en O(n), et le calcul de c en O(n).
On peut par exemple calculer le determinant d'une matrice a coeff entiers en le calculant pour plusieurs nombres premiers dont le produit est > a 2 fois une borne a priori sur le determinant (produit des normes des vecteurs lignes ou colonnes).

Puissance modulaire rapide, algorithme récursif, le calcul de a^n mod p se fait en log2(n) etapes necessitant chacune 1 ou 2 multiplications et 1 division d'entiers <p^3 (O(ln(p)^2) operations par des methodes naives).
Application:
Test de Miller-Rabin. Complexité en O(ln(p)^3) si on multiplie les entiers naivement.
Thm admis: si p n'est pas premier, le cardinal de l'ensemble des a<p tels que Miller-Rabin reussit est <=p/4
Si on prend a au hasard, on a donc 1 malchance sur 4 au plus de reussir le test alors que p n'est pas premier. Si on prend une vingtaine de a "independants", si tous les tests passent, on a au plus 1 malchance sur 4^20 que p ne soit pas premier. En pratique on prend des a premiers.

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

Re: option C 2016/17

Message par parisse » mer. sept. 21, 2016 6:54 pm

14/9: TP prise en main et programmation de PGCD/Bezout/restes chinois. http://www-fourier.ujf-grenoble.fr/~par ... regtp1.pdf

21/9:
Puissance modulaire rapide: algorithme iteratif.
Racine carre modulo p, cas ou p=3[4] a^(p+1)/4 mod p, cas ou p=1 [4] par calcul de gcd(x^2-a,(x+r)^(p-1)/2-1) mod p avec r aleatoire. Calcul des complexites. On calcule (x+r)^((p-1)/2) modulo p, x^2-a par la puissance rapide.

Racine carree entiere de a par l'algorithme de soustraction d'impairs consecutifs, exercice: determiner la complexite si n est le nombre de chiffres de a.

Polynomes à 1 variable: représentation dense par la liste des coefficients, complexite de + - * pgcd (comme pour les entiers en remplacant nombre de chiffres par degre)
Etude detaillee de Karatsuba pour multiplier 2 polynômes à coeffs dans un corps fini de degre<2^n -> temps en 9*3^n-8*2^n, existence d'un seuil pour multiplication naive puis Karatsuba.
Algorithme de multiplication de 2 polynômes à coeffs approchés par FFT
Si P1 et P2 sont 2 polynomes tels que degré(P1*P2)<n, il suffit de connaitre P1*P2 en n points pour déterminer P1*P2, par exemple les puissances xi^j d'une racine primitive n-ième complexe de 1. Comme P1*P2(x)=P1(x)*P2(x), il suffit de savoir passer des coefficients de P1 (complétés par des 0 pour en avoir n) aux valeurs P1(xi^j) et réciproquement, ce qui est la transformée de Fourier discrète (dft) de C^n dans C^n et son inverse (qui se calcule par une dft en changeant xi en 1/xi). Si n est pair, le calcul de dft(P) se déduit du calcul de dft(coeffs_pairs_de_P) et dft(coeffs_impairs_de_P) en O(n) opérations, car P(x)=Ppair(x^2)+x*Pimpair(x^2) et xi^2 est une racine primitive n/2-ième de 1. Donc si n est une puissance de 2, le calcul de dft(P) se fait en O(n*ln(n)) opérations (algorithme de la fft).

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

Re: option C 2016/17

Message par parisse » jeu. oct. 06, 2016 12:08 pm

28/9: TP suite ex. 3, 5, 7, 13, 12, 14, 17 (debut)

5/10: Produits de polynomes a coefficients dans Z/pZ par FFT lorsque p=k*2^n+1, avec 2^n>degre(A)+degre(B). On construit une racine 2^n-ieme primitive de 1 en prenant un generateur de Z/pZ a la puissance k (pour construire un generateur on prend un entier a au hasard, il faut que son ordre ne soit pas un diviseur strict de (p-1), il suffit de tester powmod(a,(p-1)/d,p)!=1 pour tous les d facteurs premiers de p-1.
Remarque si p n'est pas de la forme k*2^n+1, on fait comme pour Z, par restes chinois avec suffisamment de premiers de la forme k*2^n+1.

Evaluation: methode de Horner. Changement d'origine avec Horner repete (cf. ex 17).

Polynomes a plusieurs variables: représentation recursive, representation distribuee creuse, ordre des monomes (ex. ordre lexicographique), multiplication en O(n*m*ln(taille du produit)), discussion sur la densité (formule comb(n+d,n) pour le nombre de monomes possibles d'un polynome de degre total d en n variables)

Arithmetique d'intervalle

"Bestiaire" d'objets mathematiques et representation en machine
* rationnel,
* complexe,
* variable libre/affectee/hypothese
* expression symbolique, evaluation. Niveau d'évaluation (nombre de remplacements récursifs d'un nom de variable par une expression qu'on évalue). Par défaut 25 en mode interactif dans Xcas, 1 en programme. Empêcher l'évaluation, quote. Quote implicite dans certaines instructions comme := pour le membre de gauche, et le membre de droite dans une définition de fonction/programme.
Différence expression/fonction, passage d'une expression à une fonction par unapply. subst pour substituer dans une expression.
* liste/vecteurs, liste de listes de meme taille=matrice
Affectation := remplacement de la liste en temps O(taille de la liste), =< affectation en place en temps O(1).
* autres types de listes : sequences (pas de profondeur), polynome 1d dense poly1[...]
* extension algebrique de Q (rootof) couple de polynomes A/B, vaut A(alpha) avec B(alpha)=0, B irreductible sur Q.
* corps fini premiers : notation % p, pour creer un element de Z/pZ, % 0 pour revenir dans Z
* corps fini non premiers: GF(p,n) cree un corps K et affecte par defaut a g un generateur de K*, le polynome minimal M de g est irreductible de degre n mais aussi "primitif" (def: la classe de X modulo M engendre tout K*).
* construction de corps non premiers: 2 phases: recherche d'un irreductible (prochain cours), puis on cherche un generateur g de K*, son polynome minimal (obtenu en regardant les puissances 0 a n de g comme des vecteurs dans (Z/pZ)^n et en appliquant le pivot de Gauss pour trouver une relation lineaire) est irreductible primitif.

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

Re: option C 2016/17

Message par parisse » jeu. oct. 06, 2016 12:23 pm

Conseils pour faire son expose de 35 minutes (Edit: 5 mn de moins a partir de la session 2017)
* considerer qu'on fait une sorte de "seminaire" sur le sujet du texte.
* le jury n'est pas cense connaitre le texte
* au debut (2-3 minutes) commencer par presenter rapidement la problematique du texte puis ecrire au tableau un plan des points qu'on va developper (pas un plan de lecon, juste les titres), et indiquer ou il y aura des illustrations informatiques. Piocher dans les suggestions en fin de texte pour construire son plan.
* puis derouler un expose mathematique (avec des definitions/propositions/lemmes/theoremes... ne pas oublier qu'il s'agit d'une epreuve de maths) en developpant des points en relation avec le programme de l'oral (par exemple eviter de recycler un theoreme d'existence theorique d'une lecon d'algebre sans construction explicite), inserer les illustrations sur machine au moment qui parait le plus opportun.
* les illustrations sur machine sont en gros de 2 types: utilisation de commandes du logiciel ou petits programmes. En preparation en temps limite, je conseille de cerner quelques commandes "builtin" du logiciel permettant d'illustrer en premiere partie de preparation (pas de programme de plus de 2 ou 3 lignes a ce moment-la), puis bien assurer la partie mathematique de l'expose, avant de se lancer dans des programmes un peu plus ambitieux. Si un programme ne marche pas, ne pas passer trop de temps a le debugguer (disons pas plus de 5 minutes sans rien trouver), et surtout ne pas hesiter a le montrer au jury en disant qu'il ne marche pas.
* si on est un peu a l'aise sur le sujet, on peut terminer par une conclusion prenant du recul sur le texte/les algorithmes mis en oeuvre/la modelisation.
* anticiper que le jury posera surement des questions de complexite d'algorithmes si on n'evoque pas soi-meme la question.

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

Re: option C 2016/17

Message par parisse » mer. oct. 19, 2016 6:14 pm

12/10: fin du TP1

19/10: texte du jury sur RSA.
Construction d'un corps fini (fin)
-> démonstration de la formule X^(p^n)-X modulo p=produit des irreductibles de degré divisant n et coeff dominant=1.
Dans un sens, on utilise que si A est irréductible de degré k, alors Z/pZ[X]/A est un corps ayant p^k éléments donc alpha^p^k=alpha pour tout alpha dans le corps, d'où on déduit que X^p^k-X est divisible par A, et X^p^k=X mod A entraint X^p^n=X mod A en réitérant "prendre à la puissance p^k" n/k fois.
Dans l'autre sens on fait le quotient euclidien de n par k, si n=k*q+r
alors X=X^(p^(k*q+r))=X^(p^r) mod A et cela entraine que r=0 sinon il y a trop de racines pour X^(p^r)=X dans le corps Z/pZ[X]/A
-> on en déduit une majoration du nombre de polynôme irréductibles de degré n, puis une minoration, en raisonnant sur les degrés. Pour p pas trop petit, on a environ une chance sur n de tomber sur un irréductible en prenant un unitaire de degré n à coefficients aléatoires.
-> Critere d'irreductibilite pour F de degre d dans Z/pZ[X]
gcd(F,X^(p^k)-X)=1 pour k=1,...,floor(d/2)
Attention: p^k peut vite devenir tres gros, on calcule donc gcd(F,powmod(X,p^k,p,F,X))
Cout: pour un pgcd k*ln(p)*cout multiplication mod F,p soit k*ln(p)^3*deg(F)^2
pour le test complet ln(p)^3*deg(F)^4 a cause de la somme des k

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

Re: option C 2016/17

Message par parisse » lun. nov. 14, 2016 9:55 am

26/10: Retour sur le texte RSA du jury, plus particulierement sur la factorisation d'entiers
division triviale: on divise x par les entiers entre 2 et sqrt(x), le cout est majoree par sqrt(x)*ln(x)^2 (nombre de divisions*cout maximal d'une division). Inutilisable pour prouver la primalite de x sauf si x est petit (pas plus de 10^14 environ), par contre sert a trouver les facteurs premiers les plus petits d'un entier x, typiquement on a une table des nombres premiers < a par exemple 10000.
Pour creer la table des premiers <=n, on peut utiliser le crible d'Eratosthene: on barre les multiples stricts de 2 puis du premier entier non barre, etc. jusqu'a sqrt(n). Le cout est en le nombre d'entiers que l'on barre donc n/2+n/3+n/5+...+n/dernier premier<=sqrt(n) que l'on peut majorer par n*(1/2+...+1/sqrt(n))=O(n*ln(n)).

La méthode de Pollard-rho:
théorème des anniversaires, la proba d'avoir n nombres entre 0 et N-1 distincts 2 à 2 est équivalente pour N grand à exp(-n^2/(2*N)) si n^2/N tend vers une limite non nulle (on calcule ln(P), on encadre avec une integrale).
Pour l'appliquer à un entier n à factoriser, notons N le plus petit facteur premier de n. On génère les n entiers par une suite récurrente u_{k+1}=f(u_k), avec typiquement f(x)=x^2+1 mod n. Comme on ne connait pas N, on teste l'égalité modulo N par gcd(u_k-u_k',n) non trivial. On ne teste pas toutes les paires k,k', mais seulement k'=2k, en effet la suite est ultimement périodique (d'où le nom rho de la méthode). Il faut de l'ordre de O(sqrt(N)) termes pour trouver le facteur N.
Remarque on ne prend pas f(x)=a*x+b mod n car mod N cette suite a une probabilite assez grande d'avoir une periodicite quasi-maximale N-1 (donc pas du tout en O(sqrt(N)): c'est le cas si a engendre (Z/NZ)*.
Ce type de méthode de factorisation a une complexité qui dépend de la taille du plus petit facteur de x, comme la division. Il diffère des méthodes comme le crible quadratique dont la complexité dépend de x. On utilise en général d'abord des méthodes comme Pollard-rho (ou les courbes elliptiques) pour détecter les "petits" facteurs d'un entier x (de taille jusqu'à 10^18 environ pour Pollard-rho).

9/11: 2eme etudiant sur le texte RSA.
Complement: exemple d'attaque si n=p*q avec q<p<2*q et si la clef privee est "petite", cette methode utilise le developpement en fractions continues de n/e ou e est la clef publique.
Definition du developpement en fraction continue et lien avec Bezout:
autre methode iterative pour Bezout avec a*u_n-b*v_n=(-1)^n*r_n, les suites u_n et v_n verifient u_{n+2}=u_n+q_n*u_{n+1} et v_{n+2}=v_n+q_n*v_{n+1}, et sont donc positives, et on a la relation u_n*r_{n+1}+u_{n+1}*r_n=b et v_n*r_{n+1}+v_{n+1}*r_n=a.
Lien avec la decomposition en fraction continue de a/b=[q0,...,q_{N-1}], l'avant-derniere reduite [q0,...,q_{N-2}]=v_N/u_N ou u_N et v_N sont les coefficients de Bezout de a et b definis comme ci-dessus. On montre pour cela par recurrence que
[q0,...,q_{n-1},x]=(v_n+x*v_{n+1})/(u_n+x*u_{n+1})
et on fait x=q_n et n=N-2

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

Re: option C 2016/17

Message par parisse » mer. janv. 11, 2017 9:36 am

16, 23, 30/11: PGCD dans Z[X] et resultant, voir resume dans les posts option C 2015/16.
7/12, 14/12, 4/1: pas de seances en raison des oraux blancs et des ecrits.

Le 11/1 et le 18/1 localisation des racines d'un polynome: pour le cours voir la section 7 localisation du manuel algorithmes de Xcas (http://www-fourier.ujf-grenoble.fr/~par ... /algo.html) ainsi que la section 18.1 factorisation pour se ramener a des racines simples, des exercices sont disponibles en section 18.9, en particulier 1, 5, 6.

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

Re: option C 2016/17

Message par parisse » jeu. janv. 26, 2017 12:38 pm

25/1: algebre lineaire sur un corps: pivot de Gauss, decomposition LU en O(n^3), application de PA=LU pour resoudre un systeme lineaire en O(n^2), en Xcas p,l,u:=lu(a) puis linsolve(p,l,u,b) au lieu de linsolve(a,b)
Inverse et determinant en utilisant LU
Algorithme de Danilevsky en O(n^3) pour transformer une matrice n,n en une matrice compagnon semblable ou une matrice bloc compagnons, calcul du polynome caracteristique en O(n^3). Methode de Krylov v_{k+1}=Av_k, Ker(v_0|...|v_n) donne tres souvent le polynome caracteristique, egalement en O(n^3).
Algorithme de Gauss-Bareiss (reduction sans fractions sur Z ou un anneau de polynomes). Cout en O(n^5*ln(n)^2) pour le calcul du determinant d'une matrice n,n a coefficients entiers. Moins bien que l'algorithme modulaire en O(n^4*ln(n)).
Calcul du determinant par developpement en O(n*2^n) utile si on ne peut pas diviser ou si la division coute tres cher (par exemple s'il y a beaucoup de variables).

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

Re: option C 2016/17

Message par parisse » mer. mars 01, 2017 12:25 pm

1/2: TP algebre lineaire sur un corps (voir section 22.12.2 du manuel algorithme de xcas)
8/2 et 15/2: texte du jury sur la molecule, algebre lineaire sur les entiers, interpolation de Lagrange
1/3: TP algebre lineaire sur Z, TP interpolation
8/3: texte du jury sur le partage de secret
15/3: codes
22/3: semaine des ecrits

Répondre