Le forum de XCAS

Xcas: un logiciel libre de calcul formel
Nous sommes actuellement le Mer Nov 22, 2017 8:20 pm

Heures au format UTC




Publier un nouveau sujet Répondre au sujet  [ 1 message ] 
Auteur Message
MessagePublié: Lun Juin 27, 2016 8:13 am 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4106
Cryptographie et factorisation:
Difficulte: devrait etre plutot facile pour qui connait le programme.
Suggestions: programmer la methode RSA (on peut utiliser les instructions euler, inv(a % b), powmod, et si on veut coder des messages sous forme de chaine asc/char, convert pour les grouper), discuter le temps necessaire pour coder/decoder un message par RSA (lien avec la puissance rapide), montrer l'equivalence de la connaissance de phi(n) et de n=p*q si p et q sont premiers.
Discuter la complexite de la factorisation/primalite en testant tous les facteurs jusque sqrt(N).
Théorème des anniversaires, montrer que 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 en raison du dessin representant la lettre rho). 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 la taille de x et pas de la taille de son plus petit facteur. On utilise en général d'abord des méthodes comme Pollard-rho pour détecter les "petits" facteurs d'un entier x (de taille jusqu'à 10^18 environ pour Pollard-rho)

Codes correcteurs avec "tour de magie"
Difficulte: devrait etre plutot facile pour qui connait le programme, ce texte date de l'epoque ou il n'y avait pas d'option C, et pas de codes de Hamming binaires au programme, aujourd'hui les candidats sont censes connaitre les defs donnees dans le texte...
Questions possibles (en plus des suggestions): quels sont les caracteristiques de codes analogues permettant de corriger une erreur ? Par exemple le suivant est n=15, k=11, quels avantage et inconvenients par rapport a celui du jury? Si le taux d'erreur par bit est de 1e-3 par exemple, quelle est la probabilite d'avoir 2 erreurs ou plus (donc de corriger improprement)?
-> Pour n=15, la proba de mauvaise correction est superieure au cas ou n=7, c'est un inconvenient, par contre le taux de transmission d'information utile est superieur (11/15 vs 4/7). Selon le type de donnees a transmettre, on choisira plutot n=7 que n=15, ou on utilisera un code permettant de corriger plus qu'1 erreur

Moyenne arithmetico-geometrique
Difficulte: normale. On peut en traiter une bonne partie sans connaitre le programme specifique.
Sur la moyenne arithmético-géométrique, on peut montrer que les suites sont adjacentes, montrer une estimation a priori sur |a_n-b_n|<=constante^(2^n-1)*|a_0-b_0|^(2^n), et en deduire la complexite du calcul de la moyenne arithmetico-geometrique avec k digits (comparable a celle d'une methode de Newton). On peut comparer la complexite avec celle qui serait issue d'une quadrature usuelle (avec romberg ou gaussquad dans Xcas) et celle d'une suite qui converge lineairement.
Sur les parametrisations, on peut montrer que toute conique admet un parametrage rationnel en utilisant une droite passant par un point de la conique de pente m et l'autre point d'intersection, l'illustrer (avec un parametre symbolique: menu Edit->ajouter parametres, les instructions conique ou plotimplicit, point, droite(,pente=) et inter()). On peut expliquer comment on peut calculer les integrales de racines carrees de fraction rationnelles en x et en un polynome du second degre en x (sans utiliser des sin/cos, sinh/cosh mais en se ramenant directement a des fractions rationnelles).
On peut effectuer comme suggere par le texte certains des calculs algebriques avec Xcas (selectionner a la souris des morceaux d'expression et appliquer une fonction de reecriture), par contre il n'est pas conseille de les faire au tableau, c'est ennuyeux, les risques d'erreurs sont importants, sauf pour des calculs tres simples (essentiellement calcul mental), par exemple pour montrer que les suites sont adjacentes et l'estimation de l'erreur.
Exemples d'illustrations informatiques: http://www-fourier.ujf-grenoble.fr/~parisse/agreg/agm_agreg.xws
On peut enfin exposer le paragraphe qui explique pourquoi une cubique ne peut pas se parametrer rationnellement.
La documentation de Xcas contient un paragraphe sur l'utilisation de la moyenne arithmético-géométrique pour calculer les fonctions transcendantes élémentaires en multi-précision.

texte du jury sur la molecule
Difficulte: moyenne, la partie geometrie 2-d est facile, mais l'illustration en 3-d est delicate si on ne s'est pas entraine auparavant. La recherche du nombre de solutions est piegeuse.
http://agreg.org/Textes/pub2008-C2.pdf
Illustrations possibles http://www-fourier.ujf-grenoble.fr/~parisse/agreg/cyclohexane.xws
Attention, le nombre de solutions pour le cyclohexane est infini, contrairement a ce que pourrait laisser penser l'etude du systeme P(u,v)=0, P(v,w)=0, P(u,w)=0 avec le resultant...
Une correction du texte se trouve dans la documentation de Xcas: rechercher le mot-clef cyclohexane (menu Aide>Rechercher un mot)

Recherche de parametrisation rationnelle d'une courbe implicite.
Difficulte: normale, on est en plein dans le programme specifique de l'option.
Quelques idees pour le dvpt:
parametrisation rationnelle d'une conique (ne rentre pas dans le cadre du thm)
discuter le nombre de points singuliers (en general 0, des valeurs isolees du parametre si on a une famille de courbes dependant d'un parametre).
programme de recherche des points singuliers de C: recherche de r1:=resultant(C,diff(C,x)); r2:=resultant(C,diff(C,y)); solve(gcd(r1,r2),y) donne les ordonnees, puis solve(gcd(C(y=sol),diff(C,x)(y=sol),diff(C,y)(y=sol)),x) donne les abscisses.
Representer une des courbes par exemple le trifolium et quelques coniques pour differentes valeurs du parametre pour illustrer le theoreme.
Faire des comptages de multiplicite/degres pour montrer que les resultants en y et en x n'auront qu'un facteur de degre 1 en x ou en y permettant de determiner x et y en fonction de t.
Expliquer l'allure locale des points singuliers (les pentes t des tangentes sont racines du 1er polynome de Taylor qui ne s'annule pas au point critique en posant y=t*x, ce n'est pas limite a des courbes d'equations polynomiales).
Conclusion possible: le texte ne permet de traiter que quelques courbes exceptionnelles, il a un tres grand interet theorique mais peu d'interet en pratique pour representer des courbes implicites contrairement au resultat sur l'allure locale en 1 point singulier.

Acceleration de convergence series alternees
Difficulte: contient des parties tronc commun, pas forcement bien maitrisees.
Suggestion : on peut montrer le theoreme 2 en appliquant le thm de convergence dominee. Attention, il n'y a pas convergence simple en 1, il faut donc montrer que la mesure du singleton {1} est nulle, ce qu'on peut faire en la majorant par a_n pour tout n et en faisant tendre n vers l'infini.
On peut montrer la relation de recurrence entre P_n, P_n+1 et P_n+2 en posant X=sin(t)^2 soit
cos(2n+4)t=2*(1-2sin(t)^2)*cos(2n+2)t-cos(2nt) qu'on obtient par exemple en linearisant cos(2t)*cos(2n+1)t.
On peut remarquer que les c_k et d_n s'obtiennent a partir des p_k par l'algorithme de Horner. Il n'est donc pas necessaire de calculer d_n comme indique dans le texte.
Sinon d_n se calcule avec la relation de recurrence en X=-1, par rsolve dans Xcas ou par recherche de suites geometriques solutions.
On peut s'interesser a la complexite des calculs. Combien de decimales et d'iterations faut-il calculer S a une precision donnee si on fait les calculs en flottants multiprecision? Et bien sur on peut faire le meme calcul de complexite en calculant les p_k comme des entiers.
On peut aussi comparer la complexite du calcul d'un P_n(X) ou de tous les P_k pour k<=n par la relation (2), par la recurrence entre les p_k, ou par la relation de recurrence entre P_n, P_n+1 et P_n+2.
Et bien sur illustrer le paragraphe 6 comme indique dans les suggestions.

partage de secret (jury 2009)
Difficulte: normale, mais avec un risque de passer trop de temps sur l'etude de la securite du systeme.
Remarque/conseils: la methode naive du 2.2 est l'ecriture en base 2^tau, exemple si s est le secret (par exemple s:=123,t=9, n=3 donc tau=3)
l:=convert(s,base,2^3) va partager le secret et convert(l,base,2^3) le reconstruit.
S'attendre a se voir poser la question du decodage pour l'ecriture du secret modulo p_i dans les suggestions (restes chinois) et de l'equite (choisir des nombres premiers proches).
L'étude de la sécurité du paragraphe 2.3 est plus difficile que la compréhension du système résistant du paragraphe 3, qui est juste de l'interpolation de Lagrange, et se programme facilement:
http://www-fourier.ujf-grenoble.fr/~parisse/agreg/secret.xws
ce qui peut permettre de faire une partie d'expose honorable avec un petit blabla sur l'algorithme de Horner pour faire le partage, et les differences divisées et la substitution de x par 0 pour la reconstruction (complexités en fonction de n, discussion sur le corps de base...).
On peut montrer que cardinal de F_x vaut 1 au paragraphe 3 (interpolation en 0 et les n-1 t_k fixes)
Indication pour montrer le thm 1 §4.4: (1) on a m equations homogenes lineaires et (m-l)+(m-l-k+1) inconnues. Noter que si Q_1=0 alors Q_0=0. (2) car Q_0+P*Q_1 est de degre <=m-l-1 et s'annule en m-l points donc est nul.

Compression de fichiers
Difficulte: normale mais risque de passer beaucoup de temps sur le paragraphe 4.
Programmer la transformation D2 et son inverse est facile (on peut d'ailleurs visualiser le resultat de la compression avec perte en utilisant l'instruction writergb). On peut se poser la question de la complexite de D2 en fonction de la taille des donnees, et comparer avec la transformation de Fourier discrete. Se mefier du paragraphe 4: on risque de passer pas mal de temps a exposer des maths somme toute assez basiques sans connexion avec l'option. On peut par contre commenter "inesthetiques sqrt(2)" en relation avec le §: en calcul formel, il vaut mieux travailler avec des matrices rationnelles que sur des extensions algebriques, on peut alors evoquer l'orthonormalisation de Gram-Schmidt (ou la factorisation QR) en calcul approche et exact, et faire le lien avec D4.
On peut faire un parallele entre D2, D4 et le cas general du paragraphe 6 avec les methodes de Newton-Cotes en integration (D2 correspond aux rectangles, D4 aux trapezes ou au point milieu, etc.). Attention, tous les details ne sont pas nuls pour D4 pour une fonction affine parce que les indices sont calcules modulo 4*2^n (et non 4^n), dans l'exemple avec 8 octets, le dernier detail est non nul.
On peut verifier les relations du 6.1 pour D2 et D4.
6.1 (3) (Z+1)^A divise H equivaut a H(-1)=0 (q=constante), H'(-1)=0 (correspond a q(x)=x), etc.
Pour A=2, H(Z)=1/2*(Z+1)^2*(p_1*Z+1-p_1)
On peut discuter la modelisation qui commence par parler de representation des pixels par des octets (entier entre 0 et 255), puis semble effectuer des calculs en flottants, et parle de "compression" sans perte en semblant considerer la taille des chaines de caracteres representant ces flottants.

Texte public 2016 sur les design.
Difficulte: difficile de rentrer dans le texte et de trouver des idees d'illustrations informatiques.
Voici quelques idees:
1/ construire un 7,3,1 design en partant de la matrice H de taille 4 donnee page 4 et de la suggestion
Code:
H4:=[[1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]];
H8:=blockmatrix(2,2,[H4,H4,H4,-H4]);
J:=matrix(8,8,1);
tmp:=(J+H8)/2;
tmp[1..7,1..7];

2/ programmer un test comme dans la proposition 1 mais avec renvoi de faux des que possible (donc sans calculer A*A, plutot en faisant les produits scalaires colonne par colonne), le tester avec H4 et avec une autre matrice
3/ enumerer les elements de GL(F_2^3)

S'attendre a une question de majorer grossierement le cout d'un algorithme naif de recherche exhaustive, par exemple sur la matrice d'adjacence, et sur la possibilite de realiser reellement le test sur machine, ou en parler soi-meme pour montrer l'interet des methodes proposees.

2016: Gene responsable d'une maladie
Difficulte: touche un peu au tronc commun pas forcement bien maitrise. Attention certains calculs de resultant sont tres longs ce qui peut derouter dans une preparation en temps limite.
Il y a un piege dans ce texte : le candidat risque de passer beaucoup de temps a exposer le denombrement aboutissant la matrice de la proposition 1, expose difficile a mon avis et qui n'est pas dans le coeur du sujet de l'option.
Section 3.2: on a 3 equations a 4 inconnues, si on fait 3 paires de resultants en eliminant p, il n'y a pas de miracles, on aura forcement 3 equations a 3 inconnues non independantes! Plutot que d'observer un facteur commun (f1-f2)^24 en factorisant r2 et r3, il est beaucoup plus judicieux de chercher le pgcd(r2,r3) et factoriser ce pgcd, qui contient (f1-f2)^24 et un autre polynome en f1, f2, quand on fait f2=1 et proot dessus on retrouve la valeur f1=0.6376... du texte.
Section 3.3: je ne vois pas bien pourquoi la proposition 4 permet de calculer plus facilement le resultant, ca depend sans doute de l'algorithme utilise.
Comparer les valeurs numeriques de E_D, E_R et E_A sans plus de recul me semble dangereux, il faudrait aussi regarder leur sensibilite a une variation, d'ou l'interet de faire des graphes dans un plan.
Un exemple de session d'illustration:
http://www-fourier.ujf-grenoble.fr/~parisse/agreg/gene.xws
S'attendre a des questions de complexite de calcul de resultants...

2016 Antennes wifi
Difficulte: moyenne.
A propos de la modelisation:
La definition 1 du taux de transmission en log(card(S))/(n*log(2)) me parait etrange, a mon avis on devrait diviser par n^2, pas par n car il faut tenir compte du regroupement des n pas de temps pour faire une matrice mais aussi des n antennes (d'ailleurs la matrice elle-meme occupe un espace en O(n^2)).
Il est assez naturel et facile de comparer les differentes methodes du texte en terme de taux de transmission et de qualite (valeur de zeta_S) pour indiquer quelles sont les meilleures methodes selon que l'on selectionne un critere ou l'autre (on peut d'ailleurs imaginer qu'un operateur passe de l'un a l'autre en fonction du taux d'erreurs corrigees).
Si on veut suivre la suggestion de construction de matrices unitaires au hasard, on peut utiliser la factorisation qr d'une matrice aleatoire (correspondant a une base orthonormee construite a partir d'une famille de n vecteurs aleatoire, qui est generiquement une base).
Pour le cas abelien, une symetrie du systeme est la permutation des valeurs propres sur la diagonale qui permet de gagner un facteur n!. On peut aussi se limiter a l dans l'intervalle [1,s/2] pour estimer zeta_S. S'attendre a etre interroge sur la complexite de la recherche exhaustive. Pour programmer le cas abelien, on peut generer la liste des generateurs de Z/sZ, pour les selectionner avec une seule boucle (et non des boucles imbriquees dont le nombre depend de n), une astuce consiste a ecrire un entier <phi(s)^n en base phi(s).
Voir dans l'exemple de session d'illustration
http://www-fourier.ujf-grenoble.fr/~parisse/agreg/antenne.xws

2017c2: Mise en commun de secrets avec des matrices sur un corps fini
Exemple de session d'illustration:
http://www-fourier.ujf-grenoble.fr/~parisse/agreg/2017c2.xws


Construction explicite de surfaces dont la projection est imposee
Difficulte: texte que je trouve trop difficile, je ne le donne plus en oral blanc.


Haut
 Profil  
 
Afficher les messages publiés depuis:  Trier par  
Publier un nouveau sujet Répondre au sujet  [ 1 message ] 

Heures au format UTC


Qui est en ligne ?

Utilisateurs parcourant actuellement ce forum : Aucun utilisateur inscrit et 2 invités


Vous ne pouvez pas publier de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas insérer de pièces jointes dans ce forum

Rechercher pour:
Sauter vers:  
Powered by phpBB® Forum Software © phpBB Group
Traduction réalisée par Maël Soucaze © 2009 phpBB.fr