UJF 2012/13- agreg option C

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

Modérateur : xcasadmin

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

UJF 2012/13- agreg option C

Message par parisse » mer. sept. 12, 2012 3:03 pm

Cours du 12/9:
Chapitre I: representation des objets mathematiques, algorithmes fondementaux.
1/ entiers machine, precision limitee. Entiers long, lien avec les polynomes, cout des operations de base + - * (algorithme naif) et comparaison avec la taille du resultat, algorithmes meilleurs pour la multiplication, etude detaillee de Karatsuba degre<2^n -> temps en 9*3^n-8*2^n, existence d'un seuil pour multiplication naive puis Karatsuba.
2/ algorithmes fondementaux:
a/ PGCD, temps en O(n^2) pour entiers longs,
b/ identite de Bezout 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, et pour verifier
a*u_n-b*v_n=(-1)^n*r_n
on definit u_n et v_n par recurrence
u_(n+2)=u_n+q_(n+2)*u_(n+1)
v_(n+2)=v_n+q_(n+2)*v_(n+1)
ou r_(n+2)=r_n-q_(n+2)*u_(n+1)
On a v_n*r_(n+1)+v_(n+1)*r_n=a, v_n strictement croissantes, 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 pour u<b.
Lien avec les reduites du developpement en fraction continue de a/b, ce sont les v_n/u_n pour n>=2.
c/ applications de Bezout: inverse modulaire pour au+nv=1, le calcul de u_n suffit, restes chinois
d/ Puissance modulaire rapide (methode recursive) il faut O(log_2(k)) multiplications et divisions pour calculer a^k modulo n.

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

Re: UJF 2012/13- agreg option C

Message par parisse » mar. oct. 02, 2012 12:00 pm

19 et 26/9:
TP prise en main et chapitre 1:
http://www-fourier.ujf-grenoble.fr/~par ... regtp1.pdf

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

Re: UJF 2012/13- agreg option C

Message par parisse » mer. oct. 03, 2012 4:55 pm

cours du 3/10: Représentation des objets mathématiques sur machine, suite:
* puissance modulaire rapide, algorithme itératif
* test de Miller-Rabin
* entier modulo n: représentation symétrique dans ]-n/2,n/2]
* flottants m*b^e ou b=base (en général 2 ou 10), mantisse m, exposant e. Dans Xcas, si Digits>14 on utilise des flottants multiprécision (m entier long de taille fixée paramétrée par Digits), sinon des flottants "double"
* rationnels: couple d'entiers
* complexes: couple des précédents
* polynomes à 1 variable: représentation dense par la liste des coefficients (par ordre décroissant dans Xcas).
* couple de polynomes à 1 variable (le 2ème étant irréductible) pour représenter une extension algébrique de Q (rootof) ou un corps fini (GF).
* polynome à plusieurs variables, représentation 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)
* variable affectee ou non et expression symbolique, evaluation
* liste/vecteurs, liste de listes de meme taille=matrice
* autres types : sequences (pas de profondeur), tables, attention aux tables vs listes, attention à l'affectation := et l'affectation en place =<
Distribué une petite liste d'exposé au choix à préparer en 20 minutes environ avec une illustration informatique de 5 minutes max pour après les vacances de toussaint
http://www-fourier.ujf-grenoble.fr/~par ... regtp2.pdf

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

Re: UJF 2012/13- agreg option C

Message par parisse » lun. oct. 22, 2012 4:55 pm

TP du 10/10: fin de la feuille (Horner/Taylor shift).

Cours du 17/10: Chapitre 2 Autour de l'algorithme d'Euclide polynomial (1ère partie)
PGCD dans Z[X]
- Definition: contenu, partie primitive, lcoeff=coefficient dominant, le produit de 2 polynomes primitifs est primitif, lcoeff(A*B)=lcoeff(A)*lcoeff(B), cont(A*B)=cont(A)*cont(B)
- Prop: si A et B sont dans Z[X], si B divise A dans Q[X] et B primitif, alors B divise A dans Z[X]
- Def du pgcd G de A et B dans Z[X] comme etant le produit d'un polynome pgcd dans Q[X] par un entier tel que G est dans Z[X] et divise A et B dans Z[X] et de coefficient dominant maximal. On peut se ramener à A et B primitifs.
- Illustration de différentes variantes d'Euclide (par exemple avec pseudo-division euclidienne) qui donnent des résultats intermédiaires énormes, cf. par exemple dans xcas menu Aide->Exemples->poly->pgcd.xws. Necessite d'utiliser d'autres algorithmes, 2 polynomes pris au hasard ayant toutes les chances d'être premiers entre eux.

Algorithme modulaire:
Prop: si p premier ne divise pas g=gcd(lcoeff(A),lcoeff(B)) alors degre(gcd(A mod p,B mod p)) >= degre(gcd(A,B)). Il y a égalité pour tous les p qui ne divisent pas les lcoeff des restes d'Euclide avec pseudo-division (on dit que p est de bonne réduction).
Si le degre du pgcd modulo p est nul, on conclut. Sinon, il faut reconstruire un multiple entier connu du pgcd, on prend le multiple de lcoeff g. On normalise le pgcd mod p pour avoir lcoeff=g. Si p est assez grand et de bonne réduction, alors le pgcd dans Z est le reconstruit symétrique du pgcd modulo p. Pour tester on vérifie que le reconstruit symétrique divise A et B dans Z[X]. Mais cela nécessite un p souvent grand (attention, la norme inf du pgcd n'est pas toujours inférieure à la norme inf de A et B!) avec un risque de tomber sur un p de mauvaise réduction, on préfère calculer modulo plusieurs premiers et reconstruire via les restes chinois avec les p donnant le degré minimal de pgcd, lorsque le reconstruit symétrique se stabilise on teste la divisibilité de A et de B, si divisible c'est le PGCD (égalité dans la proposition).

2ème partie (début) le résultant, définition comme déterminant du système
A*U+B*V=C
A, B, C donnés, U et V inconnus (coefficients dans un anneau intègre unitaire commutatif inclus dans un corps, par exemple Z dans Q ou Z[Y,Z,T...] dans Q[Y,Z,T...]...)
degré(U)<degré(B) et degré(V)<degré(A).
Prop: resultant(A,B)=0 si et seulement si A et B ne sont pas premiers entre eux.
Observation: si A et B sont premiers entre eux et si les coefficients de C sont multiples du résultant alors U et V ont leurs coefficients dans l'anneau.

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

Re: UJF 2012/13- agreg option C

Message par parisse » mer. nov. 07, 2012 8:03 pm

TP 24/10: suite exercices PGCD (http://www-fourier.ujf-grenoble.fr/~par ... tml#htoc31)

cours 7/11:
1/ Resultant suite:
Conséquence: si A(X,Y,Z,...) et B(X,Y,Z,...) s'annulent en x,y,z,... alors resultant en X de A,B s'annule en y,z,...
Application: élimination, résolution d'un système polynomial de n équations à n inconnues, on prend le résultant 2 à 2 par rapport à Xn de (P1, Pn), de (P2, Pn), etc. (Pn-1,Pn) on obtient un système polynomial de n-1 équations à n-1 inconnues (si les polynomes sont premiers entre eux, cas générique), etc. jusqu'à se ramener à une équation polynomiale en 1 inconnue, dont on peut calculer les solutions (éventuellement de manière approchée), puis on revient au système précédent: 2 équations en 2 inconnues, on remplace X1 par une des racines on prend le PGCD des 2 polynomes en la variable restante, on cherche les racines, etc.
En pratique, il y a explosion trop rapide du degré des résultants. En effet
Proposition: si A et B sont de degré total a et b, partiel par rapport à X n et m alors le degré total du résultant par rapport à X de A et B est <= a*b, en fait il est <= a*b-(a-n)*(b-m), avec égalité si les polynômes sont homogènes et premiers entre eux.
Application: calcul de l'équation cartésienne d'une courbe paramétrée par des fonctions rationnelles ou d'une surface: si x(t)=N1(t)/D1(t) et y(t)=N2(t)/D2(t) alors resultant(N1(t)-x*D1(t),N2(t)-y*D2(t),t) est l'équation cherchée.
Application: recherche de valeurs de paramètres pour lesquels 2 polynômes Pt(X) et Qt(X) ne sont pas premiers entre eux (alors que gcd(Pt(X),Qt(X)) renvoie 1, calcul fait pour une valeur générique du paramètre), on calcule resultant(Pt(X),Qt(X)) et on résoud = 0.
Exemple: resultant(P,P')=lcoeff(P)*discriminant(P) (définition du discriminant), recherche de valeurs de paramètres pour lesquelles P a des racines multiples.
Application: calcul de primitive de N/D si D a toutes ses racines simples,
-> sum_{t racine de resultant(N-tD',D)} t*ln(gcd(N-tD',D))

2/ Euclide et factorisation
a/ Multiplicités:
Algorithme de Yun pour écrire un polynôme P de K[X] où K est un corps de caractéristique nulle sous la forme product_{j=1}^n P_j^j où les P_j sont sans racines multiples (gcd(P_j,P_j')=1) et premiers entre eux 2 à 2.
On calcule G=gcd(P,P'), X1=P/G=product P_j, Y1=P'/G, Z1=Y1-X1',
alors P1=gcd(X1,Z1), puis on pose X2=X1/P1, Y2=Z1/P1, Z2=Y2-X2', etc.
Dans la suite on suppose toujours qu'on s'est ramené à un polynôme P sans facteur multiple (gcd(P,P')=1)

b/ Localisation des racines réelles d'un polynome à coefficients réels (suites de Sturm):
on prend la suite des opposés de restes de l'algorithme d'Euclide de P et P':
R0=P, R1=P', ... R_{n+2}=-rem(R_n,R_{n+1}), ..., R_d le dernier reste non nul (donc constant, gcd(P,P')=1)
la suite des restes est évalué en a, on compte le nombre de changements de signe de cette suite de réel (en ignorant les 0), noté sigma(a).
Alors le nombre de racines de P sur ]a,b] est sigma(a)-sigma(b).

On peut alors connaitre le nombre total de racines réelles de P en prenant sigma(-M)-sigma(M) où M est une borne sur le module des racines complexes de P (par exemple M=|P|_inf/|lcoeff(P)|+1). Puis on peut les localiser avec une précision arbitraire par dichotomie de Sturm: tant qu'il y a au moins 2 racines dans [a,b], on divise l'intervalle en 2, dès qu'il ne reste qu'une seule racine on passe à la dichotomie classique (changement de signe de P sur l'intervalle).

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

Re: UJF 2012/13- agreg option C

Message par parisse » mer. nov. 28, 2012 5:59 pm

14 et 21/11: TP/exposés
28/11: Factorisation
1/ Racines
* majoration |z|<= 1+linfnorm(P)/|lcoeff(P)|
* existence de methodes numériques (matrice companion+Schur ou/et Newton)
* racines rationnelles: si a/b est racine alors bx-a divise P donc b divise lcoeff(P) et a tcoeff(P), on peut tester la liste des diviseurs de l'un divisé par la liste des diviseurs de l'autre. Algorithme inefficace (nécessite de factoriser un entier + la liste des diviseurs peut être grande)
Algorithme p-adique: P=(bx-a)*Q est encore vrai mod n^k avec n premier, si n est premier avec b on a une racine mod n^k pour toute racine rationnelle. Or une racine mod n^k est une racine mod n, et la réciproque est vraie si P n'a pas de racines multiples mod n (méthode de Newton pour remonter mod n^2, ..., n^k).
On multiplie bx-a par lcoeff(P)/b pour obtenir lcoeff(P)*X- a*lcoeff(P)/b facteur de P, qui correspond à lcoeff(P)*(x-racine mod n^k), si n^k>2*|lcoeff(P)| et n^k>=2*|a*lcoeff(P)/b|, ces 2 facteurs sont égaux. Il suffit donc de remonter jusqu'à n^k>=2*|lcoeff(P)*tcoeff(P)|. Si lcoeff(P)*(x-racine mod n^k) écrit en représentation symétrique divise P alors on a une racine rationnelle, sinon non.
2/ Factorisation dans Z[X].
Au 1/ on a vu les facteurs de 1er degré. Idée générale: pour un degré quelconque, on prend n premier tel que P et P' sont premiers entre eux mod n, n ne divise pas lcoeff(P). On factorise mod n (Berlekamp par exemple), puis on remonte mod n^k et on recombine lcoeff(P)*un ou plusieurs facteurs mod n^k.
Détail pour Berlekamp: on considère l'application lineaire phi de l'espace vectoriel sur Z/nZ des poly de degré inférieur à degré(P) sur lui-même qui envoie un poly A sur A^n-A mod P. Théorème dim Ker phi=nombre de facteurs irréductibles de P.
Les facteurs irréductibles de P s'obtiennent en calculant une base (1,T2,T3...) de Ker(phi) par réduction de Gauss sur la matrice de phi dans la base canonique puis en calculant des pgcd(T2-alpha,P), pgcd(T3-alpha,P) pour alpha de 0 à n-1.

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

Re: UJF 2012/13- agreg option C

Message par parisse » ven. déc. 14, 2012 7:33 pm

5/12: TP
12/12: Algèbre linéaire.
Algorithme du pivot de Gauss pour réduire une matrice de taille L,C.
On initialise l et c à 1.
Tant que l<=L et c<=C faire
- si tous les coefficients sont nuls dans la colonne c à partir de la ligne l, incrémenter c et passer à l'itération suivante
- sinon on échange le cas échéant la ligne avec la ligne l pour avoir un pivot non nul en ligne l, on crée des 0 soit en-dessous de la ligne l (réduction sous-diagonale) soit sur toutes les lignes sauf la ligne l (réduction complète) par des manipulations de type L_k <- L_k - m_{k,c}/m_{l,c} L_l, incrémenter l et c et passer à l'itération suivante.
Décomposition PA=LU pour une matrice à coefficients dans un corps fini. L est triangulaire inférieure avec des 1 sur la diagonale, et les coefficients de la manipulation créant le 0: L_i <- L_i - l_{i,j} L_j si on réduit avec la ligne c (en général la colonne c), P matrice de permutation correspond aux inversions pour mettre le coeff non nul de la colonne c en ligne l.
Applications de LU: résolution de système, inverse de matrice n,n par résolution de n systèmes, déterminant.
Autres applications de Gauss: inverse par réduction complète de (matrice|identité), calcul du noyau (réduction sous-diagonale de (transposée de matrice|identité) ou par réduction complète de la matrice et insertion de lignes de 0 pour mettre les pivots 1 sur la diagonale, puis on ajoute ou enlève des lignes de 0 pour avoir une matrice carrée, puis extraction des colonnes ayant des 0 sur la diagonale et remplacement par -1 qui donnent une base du noyau).
Déterminant par Gauss-Bareiss pour rester à coefficients dans l'anneau: on remplace la manipulation L_k <- L_k - m_{k,c}/m_{l,c} L_l par L_k <- (m_{l,c} L_k - m_{k,c} L_l)/pivot_utilisé_pour_réduire_la_colonne_précédente.
Nombre d'opérations O(LC^2) ou O(n^3) dans le corps. Pour Gauss-Bareiss, cela donne un O(n^5*ln(n)^2) avec multiplication naive des entiers (si la matrice est bornée en norme infinie par une constante M). Moins bon que des méthodes modulaires pour calculer le déterminant, mais plus général.

2/ Réduction des endomorphismes
a/ Interpolation de Lagrange si le cardinal du corps est > n la dimension de la matrice. O(n^4) opérations au lieu de O(n^3) opérations ... mais sur K[X] (c'est mieux car multiplication naive sur K[X] est en O(n^2))
b/ Recherche du polynome minimal relatif à un vecteur aléatoire, il divise le polynome minimal de la matrice donc le polynome caractéristique de la matrice, donc s'il est de degré n, on en déduit que les 3 sont égaux (une fois normalisés). On cherche le noyau de la matrice dont les colonnes sont v_0=v, ..., v_{k+1}=Av_k, ..., v_n=Av_{n-1}. Algorithme en O(n^3) mais ne marche pas toujours (-> Hessenberg marche par contre toujours en O(n^3) cf. Cohen)
c/ Algorithme de Fadeev : (x*I-A)*B(x)=det(x*I-A) I, B(x) transposée de la comatrice de x*I-A. On calcule les coefficients en puissance décroissante de B par une méthode à la Horner, en utilisant une relation supplémentaire pour calculer simultanément les coefficients de det(xI-A) qui est
trace(B(x))=derivée de det(x*I-A)
Algorithme en O(n^4), qui donne en plus B(x) qui peut servir à calculer les espaces propres puisque si x0 est valeur propre alors (x0*I-A)*B(x0)=0.

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

Re: UJF 2012/13- agreg option C

Message par parisse » lun. janv. 28, 2013 1:16 pm

24/1: Representation des corps finis.
1/ Corps premiers % p et % 0
2/ Corps K non premiers de caracteristique p, K* est cyclique, soit g un generateur, alors le polynome minimal M de g est de degre n avec cardinal(K)=p^n car K est un Z/pZ-espace vectoriel de dimension n. Il est irreductible car K=Z/pZ[X]/M. Reciproquement, on peut construire un corps K de cardinal p^n par quotient de Z/pZ[X] par un polynome irreductible M, mais la classe de X n'est pas forcement un generateur de K. Pour obtenir un generateur de K on prend au hasard un polynome A en X et on teste si les puissances de A qui sont des diviseurs de l'ordre p^n-1 valent 1 modulo M ou pas. On factorise donc p^n-1 et on doit avoir que pour tous les facteurs premiers q de p^n-1, A^q mod M,p different de 1. Le test s'effectue en utilisant par exemple la fonction powmod avec un modulo polynome et un modulo entier.
On peut ensuite calculer le polynome minimal d'un element generateur, c'est un probleme d'algebre lineaire sur Z/pZ (recherche de noyau, en ecrivant en colonne les coefficients de 1, A, A^2, ..., A^n). Le quotient de Z/pZ[X] par ce polynome est un corps de cardinal p^n tel que X soit un generateur du corps (on dit que le polynome est primitif).
La representation du corps K par la classe d'un polynome modulo M est appelee representation additive car il est facile de faire la somme ou la difference/oppose dans K avec cette representation. Pour le produit on calcule le produit des 2 polynomes puis on prend le reste modulo M (et p). Pour l'inverse on fait Bezout sur le polynome et M.
On pourrait aussi utiliser un entier qui serait -1 si l'element du corps est nul ou k (entre 0 et p^n-2) si l'element du corps est le generateur a la puissance k. C'est la representation multiplicative, tres pratique pour faire des produits et des inverses, par contre pour + et - il faut avoir une table des puissances.
Pour des corps de petits cardinal, on calcule une table de correspondance entre polynome modulo M (represente par un entier dont l'ecriture en base p est la liste des coefficients du polynome) et l'entier de representation multiplicative.
Le calcul de cette table est facilite si p=2, car + et - sont un ou exclusif de l'entier en representation additive et pour avoir la representation additive du generateur a la puissance n+1 en fonction du generateur a la puissance n, on decale de 1 bit vers la gauche (multiplication par le generateur), puis si le bit n est a 1, on fait le ou exclusif avec l'entier codant le polynome minimal (reste modulo M). On peut alors faire les operations de base (+,-,*,inv) en 1 a 5 operations elementaires du microprocesseur ce qui est tres rapide.
Dans Xcas, on peut creer un corps fini avec l'instruction GF(p,n), Xcas genere alors un corps (dont le nom est K par defaut) et un generateur de ce corps (nomme g). Tous les elements du corps sont alors representes comme des polynomes en g (a coeff modulo p).

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

Re: UJF 2012/13- agreg option C

Message par parisse » ven. févr. 01, 2013 4:44 pm

31/1: primalité et factorisation d'entiers (réf Cohen).
1/ Primalité:
a/ test de division trivial (rappel, complexité en O(sqrt(N)*ln(N)^2)), ou crible d'Eratosthène
b/ pseudo-primalité (rappel Miller-Rabin, complexité en O(ln(N)^3)),
c/ certificat de primalité (Selfridge-Pocklington-Lehmer) si on peut factoriser N-1 (au moins partiellement, on peut avoir un facteur non factorisé restant de taille<sqrt(N)).
d/ instruction is_pseudoprime et isprime dans Xcas, et instruction pari() suivi de pari_isprime (cf. manuel de pari dans Aide).
2/ Factorisation:
a/ test de division trivial (rappel),
b/ algo de recherche de facteurs: de type I: le temps d'exécution dépend de la taille du plus petit facteur, de type II: dépend de la taille de N. La division triviale est de type I.
c/ exemple d'algorithme de type I: Pollard-rho,
théorème des anniversaires, la proba que n éléments pris au hasard parmi N soient distincts 2 à 2 pour n<<N et N->inf est équivalente à 1-n^2/N. Donc si n=O(sqrt(N)) cette proba peut être rendue petite.
Application: si N est composé, on prend des entiers modulo N générés par une suite récurrente x_{n+1}=f(x_n) mod N, on espère qu'ils ont de bonne propriétés de répartition, et on regarde s'ils sont distincts modulo p où p est le plus petit facteur de N. Il suffira d'en générer O(sqrt(p)) pour avoir une bonne proba d'en trouver deux égaux modulo p. Comme on ne connait pas p, le test d'égalité modulo p se fait en calculant pgcd(différence des 2 entiers modulo N,N) qui doit être non trivial. La fonction f peut par exemple être x->x^2+1 ou x^2-1 ou x^2+3 (pas de résultat sur pourquoi ça donne des entiers bien répartis par rapport au hasard). On ne teste pas toutes les différences de paires d'entiers générés, mais les x_{2k}-x_k pour k=1,2,... ce qui suffit car la suite x_k est ultimement périodique. Le calcul nécessite donc O(sqrt(p)*ln(N)^2) opérations (ce qui est toujours mieux que la division triviale car p<=sqrt(N)).
d/ exemple d'algorithme de type II: le crible quadratique.
On cherche des relations x^2=y^2 mod N, en espérant trouver un facteur de N en calculant pgcd(x-y,N).
Problème trop difficile, à la place on va essayer de factoriser sur une base de "petits" nombre premiers des x_i^2-N pour x proche de sqrt(N) (nombre friable). La taille de la base dépend de la taille de N. La recherche de x^2 se fait par produit de x_i tel qu'il n'apparaisse que des carrés de la base des petits nombres premiers, ce qui s'obtient en résolvant un gros système linéaire à coefficient dans Z/2Z.
Pour trouver les x_i on utilise un crible: sachant que si on a une solution de x^2-N=0 mod p, alors x+p, x+2p, etc. le seront aussi, on a facilement les x tels que x^2-N est divisible par p à partir des 2 racines carrées de N modulo p si elles existent (sinon on ne met pas ces racines dans la base de petits premiers!). Le crible consiste à incrémenter de log(p) tous les éléments d'un tableau dont l'indice correspond à un x tel que x^2-N est divisible par p. Lorsqu'on a parcouru tous les premiers de la base, on regarde dans le tableau les valeurs assez grandes vont correspondre à des possibilités d'entiers friables, on factorise alors les x_i correspondants pour avoir des relations. Dès qu'on a k+une marge de sécurité (par exemple 20 ou 50) relations où k est le nombre de premiers de la base on est sur qu'on trouvera une vingtaine ou une cinquantaine de relations x^2=y^2 mod N. Comme chaque relation a une chance sur 2 de donner un facteur de N, on pourra factoriser N (sauf malchance vraiment exceptionnelle!).
e/ Recherche de racine carrée modulo p:
si p=2 sqrt(N)=N
si p+1=0 mod 4, si N est un carré alors N^((p-1)/2)=1 mod p donc + ou -N^(p+1)/4 est la racine cherchée
sinon on cherche le pgcd de x^2-N avec powmod(x+r,(p-1)/2,p,x^2-N) où r est aléatoire, il y a une chance sur 2 que le pgcd soit de degré 1.
si p est assez petit (disons < sqrt(2^31)), il est plus rapide de tester les carrés mod p de k=1,2,3, ..., (p-1)/2. Comme (k+1)^2=k^2+2*k+1 mod p cela se résume à faire un shift (*2) une addition, un test si >=p et dans ce cas une soustraction, puis un test d'égalité avec N, le tout avec des entiers courts (32 bits) ce qui est très rapide.

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

Re: UJF 2012/13- agreg option C

Message par parisse » ven. févr. 22, 2013 3:21 pm

8/2: texte Algebre lineaire sur les entiers
http://www-fourier.ujf-grenoble.fr/~par ... texte3.pdf
en particulier forme normale de Hermite, ref en ligne cf. par exemple
agreg-maths.univ-rennes1.fr/documentati ... linent.pdf
Puis TP sur la methode de Pollard-rho.

15/2: 2 textes de geometrie: http://www.math.u-bordeaux.fr/~jehanne/ ... metrie.pdf et http://www.math.u-bordeaux.fr/~jehanne/ ... tewatt.pdf

22/2: texte sur les approximation de fontion:
http://www-fourier.ujf-grenoble.fr/~par ... exte_a.pdf
En complement du 15/2: utilisation de la geometrie de Xcas pour faire une preuve avec figure (menu Geo et utilisation de curseurs symboliques : menu Edit->ajouter un parametre, un curseur symbolique conserve sa valeur formelle dans un calcul exact mais prend une valeur numerique ajustable a la souris pour les evaluations numeriques, dont la representation sur une figure)

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

Re: UJF 2012/13- agreg option C

Message par parisse » jeu. mars 14, 2013 5:26 pm

7 mars: 2 textes: représentation des objets mathématiques et texte du jury sur la molécule de cyclohexane.

14 mars: texte sur la localisation des racines complexes d'un polynôme.
Complément sur l'interpolation de Lagrange:
- calcul par récurrence Pn+1=Pn+Q avec Q s'annulant en x0, ...,xn donc =alpha_n*(x-x0)*...*(x-xn)
- evaluation à la Horner P_n=alpha_0+(x-x0)*[alpha_1+(x-x1)*(alpha_2...)))) en O(n) opérations
- calcul efficace des alpha_i par les différences divisées en O(n^2) opérations dans le corps des x_i et y_i
- exemples d'application: calcul du polynôme caractéristique, résultant dépendant polynomialement de paramètres, pgcd multivariables (mise en pratique plus difficile...), analyse (erreur d'interpolation, attention au phénomène de Runge par ex. f(x)=1/(1+25x^2) sur [-1,1] avec n+1 points équirépartis, utilisation pour les méthodes de quadrature)

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

Re: UJF 2012/13- agreg option C

Message par parisse » lun. avr. 22, 2013 7:40 pm

21 mars et 4 avril: Codes correcteurs, définitions diverses (cf. TP plus bas). On émet n éléments (symboles) d'un corps fini F dont k servent à coder le message et n-k servent à tester et éventuellement corriger des erreurs.
Codes linéaires construit avec matrice identité I_k et on rajoute n-k lignes en-dessous (matrice C) , test d'appartenance au code linéaire si (x_k|y_{n-k}) est dans l'image alors y_{n-k}==C*x_k. Dans le cas contraire on essaie de corriger au plus proche au sens de la distance de Hamming (nombre de symboles qui diffèrent entre les n symboles d'un message). Distance du code=distance de Hamming minimale entre 2 éléments du code distincts (ou entre un élément non nul et 0) <= n-k+1.
Le nombre d'erreurs t que l'on peut corriger vérifie 2t+1<=distance du code.
Code polynomiaux: on multiplie par x^(n-k) un polynome de degré <k et on retranche le reste de la division par un polynome fixé de degré n-k. A l'arrivée on teste la divisibilité.
Distance du code optimale =2t+1 pour un code polynomial engendré par (x-a)*...*(x-a^{2t}) si a est un générateur du corps F et si n<cardinal(F).
TP: http://www-fourier.ujf-grenoble.fr/~par ... reg/gf.pdf
Codes de Hamming binaires (cf. par exemple http://en.wikipedia.org/wiki/Hamming_code), distance du code=3, capacité de correction t=1 et méthode explicite de correction avec les bits de parité.

11 avril: texte du jury sur les carrés magiques.
Récurrence linéaires et affines. On peut toujours se ramener à u_{n+1}=Au_n (+ f(n)) avec u_n un vecteur. Cas homogène: u_n = A^n u_0. Cas inhomogène, si f(n) est indépendant de n, et si 1 n'est pas valeur propre de A, alors on a une solution particulière constante c=(I-A)^(-1)*f. Cas général où f(n)=polynome f(n)*exp(a*n), il existe une solution particulière exp(a*n)*polynome de degré celui de f + la multiplicité de a comme valeur propre de A. Exemple suite arithmético-géométrique et application au calcul de mensualités...
Complément sur la transformée de Fourier discrète, définition, inverse.

18 avril: texte du jury sur la recherche de solutions entiers naturels pour des systèmes linéaires à coefficients dans Z.
Complément sur la FFT (Fast Fourier Transform): temps de calcul en O(ln(N)). Application au produit de 2 polynômes P*Q à coefficients dans C, ou à coefficients dans Z en travaillant dans Z/pZ avec p suffisamment grand pour avoir p/2>max coeff de P*Q et p=1+t*2^n avec 2^n>deg(P)+deg(Q)
http://www-fourier.ujf-grenoble.fr/~par ... ultfft.xws
Complément sur les courbes algébriques dans C^2:
- factorisation square-free et en composantes irréductibles. Attention, la factorisation de Xcas n'est pas la factorisation absolue, P(X,Y) est factorisé sur le corps des coefficients (éventuellement étendu en mettant une extension de Q en 2ème argument de factor ou cfactor), mais ne détermine pas tout seul une extension algébrique minimale de Q sur laquelle P(X,Y) est factorisé en produit de facteurs irréductibles sur C[X,Y].
- allure locale en un point d'une courbe (algébrique): point singulier diff(P,x)=diff(P,y)=0, non générique si pas de paramètres, mais génériquement il y a des valeurs des paramètres pour lesquelles la courbe correspondante admet des points singuliers. Pour le cas polynomial, si la dépendance en le(s) paramètre(s) est polynomiale, on peut calculer les points singuliers par resultant. En un point régulier, l'allure est celle d'un graphe de fonction (thm des fonctions implicites). En un point singulier, on calcule le premier terme homogène non nul du développement de Taylor et on le factorise (cela revient à factoriser un polynôme en 1 variable à cause de l'homogénéité), on obtient les équations des tangentes en ce point singulier. Si toutes les racines sont simples (point singulier ordinaire), la courbe est composée d'arcs de courbes tangents à ces tangentes (cf. les infos affichées par implicitplot en Xcas), sinon il peut y avoir des rebroussements.

Répondre