Un truc sur le cardinal de groupes abéliens finis à ordre fixé
Un truc sur Lotka-Volterra
Pas de réponse fournie.
Pas de réponse fournie.
Pendant ma présentation j'ai foiré mon calcul de complexité, du coup 90% DES PUTERELLES DE QUESTION ONT ETE SUR DES CALCULS DE COMPLEXITE DE SCHEISS.
Quelques questions sur des trucs que j'ai dit un peu vite dans ma présentation (et qui étaient faux)
Donner la comlpexité du calcul de $\prod_{k=1}^{+\infty}\frac{1}{1-X^k}~~mod~X^{e+1}$ et trouver que ça fait $O(e^2)$ (c'est franchement super rigolo comme calcul, je vous conseille chaudement ça comme une activité à faire en famille le samedi soir pour égayer vos veillées funèbres)
Pas de réponse fournie.
Le niveau était plutôt bas, j'ai l'impression que le jury a pris pitié quand il m'a vu m'empêtrer dans mes calculs de complexité du coup il m'aidait bien.
Un des membres du jury avait une longue vue pour voir ce que j'écrivais au tableau :D #cool #incongru #pirate
Pour une fois, un membre du jury hochait de la tête quand je disais des trucs. Ça doit être l'attitude de jury la plus humaine que j'aie vue pendants mes oraux.
Tout s'est passé aussi moyennement que prévu.
P'tite cace-dédi à Michel qu'a eu la présence d'esprit de reposer le manuel de Sage dans la malle avant de passer en oral de manière à ce que je puisse commencer avec.
14.25
Cryptage à clef publique dans GLn(Fq)
Des séries formelles, me rappelle plus trop..
Pas de réponse fournie.
Pas de réponse fournie.
Questions principalement sur l'exposé, mais mon intro était assez solide et recouvrait déjà les thématiques adjacentes au texte (logarithme dans les corps finis, stratégie des cryptages à clef publique..)
un peu stressé et fatigué pendant ma présentation (commencer à 6h30 c'est dur..), j'ai fait une démo fausse dans mon exposé, du coup j'ai du la refaire (heureusement, elle était correcte dans mes notes, juste fausse telle qu'écrite au tableau).
On m'a demandé de réfléchir aux points que j'avais admis dans ma présentation, notamment le calcul d'un polynome minimal, et une partie de l'algo que j'avais pas implémentée.
Pas vraiment d'exercices, mais on a un peu discuté de réduction de Jordan dans les corps finis, notamment pour des questions d'ordres de blocs de Jordan.
Pas de réponse fournie.
les questions étaient relativement faciles, j'y répondais généralement entre quelques phrases. Le jury était le même que celui de dosso, mention spécial au vieillard joufflu dont le nez rouge et les jumelles rétractables m'ont fait craindre l'arrêt cardiaque à chaque fois qu'il esquissait un geste.
oral assez sympathique, même si le tableau est assez dur à gérer vu qu'on ne choisit pas trop comment / quand utiliser l'ordinateur.
Tkt dosso jte lache pas buddy
17.5
Multiplication rapide de polynômes en caractéristique 2.
Équivalence de nuages de points.
Pas de réponse fournie.
Pas de réponse fournie.
Pas mal de questions sur l'exposé et mon informatique, quelques questions sur la partie du texte que je n'ai pas eu le temps d'aborder.
Réexpliquer un bout de mon informatique sur lequel j'étais allé un peu vite.
Corriger une remarque où j'avais indiqué une équivalence alors que seule une implication était vraie.
Justifier des calculs de complexité et quelques calculs que je n'avais pas eu le temps de détailler.
Essayer de justifier un théorème que j'avais laissé de côté (je n'ai pas réussi faire quoi que ce soit là-dessus).
Comment construit-on une clôture algébrique de $\mathbb{F}_2$ (évoquée dans mon exposé pour justifier le fait qu'il n'y a qu'une racine $2^k$-ème de l'unité dans un corps de caractéristique $2$) ?
Pas de réponse fournie.
Questions plutôt faciles à mon avis. Jury plus agréable et (car ?) plus jeune que ceux d'algèbre et d'analyse.
Pas de réponse fournie.
17.25
C47 : Usinage de de courbes
C37 : un truc de cryptographie (cf Nicolas ?)
On a une courbe
$$ \alpha(t) = (x(t), y(t))$$
définie sur un segment. On a une fraiseuse avec laquelle on aimerait tracer la courbe. La fraiseuse est circulaire de rayon $r$ et passe par une courbe décalée à $\alpha$ :
$$ \beta = \alpha + r \vec{n} $$
où $n= (-y', x')/ ||\alpha'||$ est la normale. Pour avoir des trucs faciles à calculer on suppose que $||\alpha'||$ est polynomiale ainsi que $x'$ et $y'$. On en déduit une condition sur $x,y$.
De là il y a des problèmes d'intersection qui apparaissent : si $r$ est trop grand (la fraise est trop grosse) on va manger trop de matière. Il faut donc regarder les points d'auto-intersection de la courbe décalée. De même si on définie une courbe par morceaux il y a des risques d'intersection entre deux courbes décalées. D'où on cherche les points d'intersection de deux courbes pour éviter les détériorations.
Pour tout ça on utilise en gros la multiplicité d'un point d'une courbe et le résultant avec lequel on arrive à détecter ces points.
Pas de réponse fournie.
Pas vraiment des questions de mathématiques fondamentales. Surtout des questions pour voir si j'arrive à mettre en contexte les mathématiques. Les détails des preuves étaient facultatives. Les questions étaient plutôt 'évasives' (?)
Questions :
Q : éclairer un point du début
Q : Est ce qu'il y a des courbes qui poseront forcément un problème ?
R : Oui, genre un point de rebroussement.
Q : Pour toute courbe le $r$ est minoré nan ?
R : Par le rayon de courbure
Q : Et la complexité de tout ça ?
R : Pgcd c'est polynomial, division tout ça, ... multiplication de poly en $n\ln(n)$ avec Transformée de Fourier Rapide. Résultant c'est du déterminant ou par méthode du pgcd donc polynomial.
Q : Les courbes de Béziers vous connaissez ?
R : C'est des courbes polynomiales qui interpolent le passage en des points de manière lisse $C^1$.
Q : Yep et c'est quoi le degré de ces polynômes ?
R : Bah il y a quatre conditions donc de degré $4$.
Q : Est ce que vous vu la suite ?
R : nan ça partait trop en lattes + quelque chose de politiquement correct
Q : Si le déterminant d'une matrice est très petit. Genre 0 normalement mais à cause des arrondis ça marche pas. Est ce que vous savez calculer un élément du noyau ? [j'avais soulevé ce problème dans ma présentation]
R : pas trop
Q : [un truc chelou du genre : qu'est ce qu'on obtient avec la fraiseuse ? ils me demandaient des propriétés mathématiques]
Pas de réponse fournie.
Pas de réponse fournie.
L'ordinateur et Sage ont été pas mal coopératifs. Je les remercie. Par contre la touche espace ...
19.5
cryptosystème à clef secrète
Un truc avec du résultant
on fait un cryptosysteme a clef secrète affine (en gros on code en faisant $M*(m +k)$ avec $m,k$ des scalaires étant le message et la clefs secrète et $M$ une matrice de permutation.) On regarde une attaque possible et du coup on code en faisant plusieir fois le codage précédent avec des $k$ différents, puis on choisit bien $M$.
J'ai fait un truc un peu original en partant d'une phrase de l'intro et ça a fait un flop total (en gros j'ai essayer de partitionner mon message et de le coder morceau par morceaux mais finalement c'est un peu plus rapide mais niveau sécurité ça change que dalle). Sinon j'ai suivi le texte, j'ai pas fait assez de maths à leur goût je pense.
Je me suis un peu fait démonté même si ils essayaient d'être gentils. Il faut savoir que comparer la complexité à RSA demande de bien comparer des valeurs comparables (ici prendre n (taille du message en nombre de bit) = N). Aussi, on doit savoir combien d'opération un ordi fait par seconde (en ordre de grandeur)
Bien faire des maths ET de l'info. Pas partir sur des trucs totalement originaux
En fait, ils ont rigolé entre eux pendant la présentation et ça m'a pas mal perturbé. Je ne sais pas si ils rigolaient entre eux ou si c'était àcause de ce que je disait et écrivait (peut être que j'ai fait trop de fautes d'orthographes au tableau)
Je pensais vraiment que ça serait plus facile que ça. Certaines parties du texte étaient dur à comprendre
20
De la cryptographie avec de l'algèbre linéaire sur des corps finis
Un truc de combinatoire
A et B veulent créer un secret, pour cela ils choisissent un groupe G et un élément $\mu$ de ce groupe. Ensuite A choisit un entier a, B choisit un entier b, A calcule $S_A=\mu^a$ et B calcule $S_B=\mu^b$, puis ils échangent leurs résultat, A calcule donc ensuite $S_B^a$ et B calcule $S_A^b$, ils connaissent donc le même secret $\mu^{ab}$.
Ensuite le texte s'intéresse à comment un méchant hackeur peut découvrir le secret. Dans tout le texte G était $GL_n(\mathbb{F}_q)$. Il y avait trois grandes parties à part l'introduction, deux d'entre elle concernaient des méthodes d'attaques du secret, et la troisième je ne l'ai pas du tout traité car il y avait déjà de quoi faire, mais il y avait des matrices circulantes dedans et ça ne me tentait pas trop.
J'ai redémontré quasiment toutes les affirmations du texte dans les deux première parties, et présenté des bouts de codes qui marchaient moyennement pour illustrer les méthodes d'attaques décrites dans le texte. (environ une page et demi de code sur Sage)
Ils m'ont posé beaucoup de questions sur mon exposé, j'ai fait pas mal de démonstration donc je suis allé un peu vite et ils m'ont demandé de reprendre plusieurs arguments, du coup ça paraissait facile vu que c'était des trucs que j'avais dit (ou pensé) pendant l'exposé. Les questions plus générales ne m'ont paru facile qu'après coup, j'ai hésité sur des questions un peu bêtes à cause de la fatigue. Le niveau des questions m'a paru inégal, entre facile et moyen, j'avais l'impression de bien répondre puisque plusieurs membres du jury avaient une attitude très encourageante, par exemple des hochements de tête approbateurs ou des sourires quand je répondais vite. En revanche vers la fin ils m'ont posé des questions de complexité, et ils m'ont demandé comment j'aurais fait pour aborder le problème de façon naïve avec telle ou telle donnée, et là j'ai eu du mal
J'ai eu l'impression de mal parler de ce que j'avais fait comme code, en gros je disais à la fin d'une partie "bon bah voilà ce que j'ai fait" sans mettre vraiment en lien avec le texte. Pour le temps de préparation j'ai trouvé que 4h c'était assez large pour faire un truc bien et je met la plupart de mes erreurs sur le compte de la fatigue.
Pas de réponse fournie.
L'oral en lui même s'est passé à peu près comme je l'imaginais, le jury était plutôt gentil, sauf quand j'ai hésité sur des questions bêtes ils ont semblé s'impatienter un peu mais je les comprends!
Pas de réponse fournie.
Fonctions de hachage
Courbe de fraiseuses (résultants, élimination)
Le texte étudiait des fonctions de hachage définies par deux éléments d'un groupe fini. L'objectif était d'étudier les relations entre ces deux éléments, que l'on voulait les moins courtes possibles, et de vérifier qu'ils engendraient le groupe. Il y avait deux exemples traités dans le texte
Plusieurs procédures sur les permutations, un plan préparé, et deux preuves claires de points du texte
jury très agréable et intéressé, les questions étaient intéressantes, et plutôt abordables, donc l'échange était plutôt fluide
Pas de réponse fournie.
Pas de réponse fournie.
Pas de réponse fournie.
Pas de réponse fournie.
Groupes abéliens finis
Un truc de crypto pas beau
Soit $G$ un groupe abélien fini de cardinal $n$. On s'en sert pour encoder des données sécurisées du style carte bancaire ou informatiques. On veut garder secrète la structure du groupe : par exemple, si $n = 4$, on ne sait pas si $G = \mathbb{Z}/ 2\mathbb{Z} \times \mathbb{Z}/ 2\mathbb{Z}$ ou si $G = \mathbb{Z}/ 4\mathbb{Z}$. Dans un premier temps, le texte propose de déterminer le nombre de groupes abéliens d'ordre $n$ pour tout $n\in \mathbb{N}$. On fait le lien avec le nombre de partitions de $n$ ({\it i.e} le nombre de manières d'écrire $n = n_1 + \ldots + n_r$ avec $n_1 \geqslant n_2 \geqslant \ldots \geqslant n_r$) et on détermine deux algorithmes pour calculer ce nombre (l'un à base de séries formelles, l'autre par récurrence).
Dans une deuxième partie, on s'intéresse à la manière de déterminer la structure d'un groupe abélien fini dont on connaît l'ordre en supposant que l'on peut tirer au hasard des éléments et que l'on peut déterminer l'addition de deux éléments, ainsi que si cette addition vaut l'élément neutre. On trouve donc un algorithme qui détermine la structure du groupe à partir de ce que l'on nomme \og un système canonique de générateurs \fg{}.
Il y avait une troisième partie qui modélisait la retenue dans les additions (genre quand on compte avec nos doigts) mais je n'y au pas touché je sais pas de quoi ça parlait.
'ai fait un plan en trois parties qui suivaient de manière assez linéaire le plan tout en détaillant les aspects mathématiques cachés derrière le truc (théorème de classification des groupes abéliens finis, donc prolongement des caractères, produit de Cauchy de séries formelles, etc.). J'ai proposé plusieurs algorithmes qui à la fin aboutissaient à la détermination du nombre de groupes abéliens d'ordre $n$ fixé. J'ai aussi déterminé, pour une borne $N$ fixée, quel était le cardinal $n$ maximisant ce nombre (c'est forcément une puissance de $2$) et j'ai aussi comparé la complexité algorithmique de quelques uns de mes algorithmes avec ceux déjà présents dans la bibliothèque de Sage. J'ai aussi montré quels étaient les $n$ pour lesquels on dispose d'un unique groupe abélien d'ordre $n$ (ceux qui sont sans facteur carré).
Q : vous pouvez détailler un peu plus le théorème de structure des groupes abéliens finis que vous avez annoncés ?
R : oui bien sûr (j'ai fait exprès d'être allusif sur ce point pour qu'on vienne me pêcher sur cette question et ça a marché). Alors là on prolonge le caractère comme ça, on a $G = \left(x\right) \times G/\left(x\right)$ par tel isomorphisme etc. (voir dans les développements).
Q : d'accord très bien mais quel rapport avec celui annoncé dans le document ? (c'était que avec des nombres premiers)
R : beh en fait c'est le lemme chinois parce que\ldots (là il m'interrompt parce qu'il a vu que je savais)
Q : pourquoi pour $p$ premier il y a exactement $q(e)$ groupes abéliens distincts d'ordre $p^e$ si $q$ est la fonction " nombre de partitions "
R : c'est car en écrivant toujours avec le théorème chinois qui est une caractérisation (donc un {\it ssi}) que...
Q : ok on peut revenir sur les séries formelles que vous avez peu traitées ? (j'ai tenté un code mais ça marchait pas là dessus donc j'ai fait d'autres trucs plutôt bien pour me rattraper)
R : alors (je baragouine en écrivant en cherchant une preuve que j'obtiens au bout de quelques minutes de griffonnage) et voilà.
Q : (la question qui tue) ok et la complexité ?
R : naaaan pas ça stp :(:( Bon alors j'essaie... La multiplication c'est en $n log\left(n\right)$
Q : quoi?????
R : beh avec la transformée de Fourier rapide
Q : Lol fais le en naïf petit
R : ok... beh je crois que c'est du tant...
[quelques galères plus tard un autre membre du jury intervient]
Q : bon on va faire autre chose genre des maths tu peux me démontrer ça ?
R : ouai ok j'fais ça plutpot j'préfère !
La gestion du temps : j'ai dû faire ma troisième partie en 5 minutes
Le jury était super sympa, ils étaient quatre (deux femmes et deux hommes) et seuls deux ont vraiment interagit durant l'oral. Ils avaient l'air intéressés et me testaient sur des trucs difficiles (thm de structure) puis quand ils ont vu qu'ils m'avaient pas eu sur les maths ils se sont dit que sur l'info ils y arriveraient peut-être et ils se sont pas trompés (mais ça va y a pire).
J'ai l'impression d'avoir agacé la membre du jury qui me posait des questions sur les séries formelles et la complexité de l'algorithme d'Euclide étendu sur les polynômes. Les autres ont bien aimé. J'suis juste passé pour un gland car j'ai oublié ma montre dans la salle alors je suis revenu dedans après.
Pas de réponse fournie.
18
C88 : Polynômes à plusieurs variables, géométrie, résultant.
C17 : Arithmétique des entiers.
Conception de courbes d'usinage pour la découpe à la fraiseuse d'un profil dans un matériau, étude des problèmes de conception : détection des points singuliers et des auto-intersections des courbes. On se restreint au cas où les courbes d'usinages sont unicursales et à hodographe pythogaricien. On utilise massivement la théorie de l'élimination et du résultant de deux polynômes.
Contenu mathématique : Caractérisation des triplets pythagoriciens de polynômes d'une variable à coefficients dans un corps, calcul explicite du noyau de la matrice de Sylvester de deux polynômes d'une variable à coefficients dans un corps.
Contenu informatique : Représentation de plusieurs courbes d'usinages présentant des points singuliers de différente nature, implémentation d'une procédure calculant la matrice de Sylvester de deux polynômes d'une variable à coefficients dans un corps et calcul de la dimension de son noyau.
1. Quelle est l'expression de la normale en un point d'une courbe paramétrée régulière ?
2. Donner et prouver une paramétrisation rationnelle du cercle ?
3. Quel est le lien avec le résultat que vous avez prouvé sur les triplets pythagoriciens de polynômes ?
4. Existe-t'il une paramétrisation polynômiale du cercle sur les réels ? Les complexes ? Un corps quelconque de caractéristique différente de 2 ?
Pas de réponse fournie.
Sur les quatre membres du jury, trois étaient majoritairement muets, mais ils restaient souriants et surtout attentifs à mes propos. Le quatrième juré me posait de nombreuses questions et était disposé à me guider lorsque je rencontrais des difficultés à lui répondre.
Aucune surprise.
15.75
Arithmétique et traitement du signal
Un truc sur les codes correcteurs
Pas de réponse fournie.
Pas de réponse fournie.
Pas de réponse fournie.
Pas de réponse fournie.
Pas de réponse fournie.
Pas de réponse fournie.
Pas de réponse fournie.
Algorithmes permettant de déterminer le nombre d'isomères de n-alcoos. Arithmétique des polynômes, équations différentielles.
Un sujet de crypto basique avec du résultant.
On présente dans un premier temps des notions de chimie organique liée à la représentation d'alcools. On s'intéresse ensuite à la détermination du nombre d'isomères pour les différentes valeurs de n avant de généraliser le problème à celui des arbres 1,2,3,4.
L'essentiel du travail informatique a été réalisé sous xcas. J'ai produit divers programme liés à des problématiques explicités dans le texte.
Echange très riche qui ressemblait plus à une discussion. Beaucoup de questions afin de préciser quelques erreurs dans mes démonstrations puis beaucoup de questions de complexité de mes algorithmes (une chance dans mon cas, il faut y être préparé). Dans un dernier temps, nous avons discutés de prolongements aux cas d'autres arbres particuliers tels que les arbres binaires par exemple.
La structure du plan probablement afin de mieux mettre en jeu les articulations entre les différentes parties. Egalement approfondir davantage la partie compliquée du document que j'ai simplement survolée et qui m'a probablement coûtée quelques points.
Jury très bienveillant, sympathique et attentif (bravo !) durant l'intégralité de ma présentation.
35 minutes c'est long, je n'avais rien préparé par rapport au temps, il faut donc être capable d'allonger ou raccourcir son discours pour s'adapter au cours de la présentation.
15
C87 - (Session 2019)
C42 ?
On cherche à obtenir l'évolution asymptotique d'une population animale en modélisant les naissances et morts sur différents âges avec un modèle linéaire. Le texte pointe qu'à partir de certaines hypothèses (assez forte) on peut avoir une convergence prévisible.
Plan et notes de l'oral que je comptais produire.
Un peu de code pour illustrer mon propos. Principalement des calculs et graphiques pour montrer qu'on a une asymptote exponentielle à l'infini et qu'en dehors des hypothèses formulées en début de texte on obtient des résultats peu contrôlés.
Le jury s'est montré très intéressé par les hypothèses du modèle et ce qu'elles impliquent sur les calculs, ce que provoque leur absence, etc. En partie parce que j'ai beaucoup appuyé sur le côté "hypothèses lourdes" pendant ma présentation. Il m'a également demandé la complexité pour calculer un certain vecteur (Le vecteur V* du texte, connaissance lambda et A). La complexité standard était O(n^3), car pivot de Gauss. Mais la matrice A étant très gentille, on peut en fait descendre en O(n).
Je m'en voulais un peu de m'être emmêlé les pinceaux dans certaines de mes démonstrations, par refus de recopier bêtement mes notes. Le jury est revenu sur la démonstration problématique pour me donner l'occasion de la refaire tranquillement.
Un jury très intéressé et vraiment souriant et sympathique.
Voir mon retour sur la leçon 152 pour un retour général.
Pour cet oral précis, je ne m'attendais à un jury aussi entraînant.
8.25
C30 : Algebre linéaire, corps finis, groupes de permutations
Algèbre linéaire et géométrie
On cherchait à sécuriser un échange entre deux individus Alice et Bob et pour cela on avait ne permutation connue de tous permettant de définir des fonctions de chiffrement et de déchiffrement, le texte évoluait et proposait au fur et à mesure des solutions réglant le problème que générait celle d'avant.
Par exemple, la première méthode était toute bête, donc il n'y avait aucune sécurité. La deuxième était un poil plus complexe et faisait intervenir les matrices compagnons. Mais encore une fois la sécurité n'était pas optimale. La troisième indroduisait la notion de polynôme de permutation, et la sécurité était bien meilleure, cependant ça nécessitait un calcul de résultant de taille très grand de l'ordre de 2^n.
Enfin la dernière partie du texte traitait une optimisation du cout et de la sécurité via les actions de groupes (je ne l'ai pas abordée)
Un plan en trois parties expliquant le concept général puis les améliorations apportées ainsi que leurs faiblesses.
Questions :
- Retour sur certains de mes programmes pour les détailler
- vérifier que les fonctions chiffrement et déchiffrement que vous énoncez sont bien réciproques
- Corriger votre erreur dans la preuve (j'avais juste écrit un ensemble privé de 0 alors qu'il fallait laisser 0 pour garder une structure d'espace vectoriel)
- Comment on effectue le calcul d'un déterminant (J'avais énoncé le coût du calcul du résultant énoncé) ? Algorithme de Gauss
- complexité de l'algorithme de Gauss et preuve ? De l'ordre de n^2 transvections qui coutent chacune n donc n^3
- On peut toujours procéder comme ça ? Non il faut des pivots non nuls
- Et donc par exemple pour une matrice compagnon ? On permute des lignes pour avoir un pivot non nul
- Quelle influence sur le déterminant ? ça ne change rien au signe (-1) près
- Comment procéder pour obtenir une relation de Bezout ? Euclide étendu
- Écrire le principe de l'algorithme d'Euclide étendu
- Dans le texte il était écrite que les X^t étaient des polynomes de permutation si t était premier avec 2^n - 1 (un polynome de permutation c'est un polynome qui pour tout x dans F2^n vérifiait P(x) = sigma(x) avec sigma une permutation) donc on m'a demandé de prouver ce point : Bézout puis injectif surjectif
- Combien y'a t'il de polynomes de permutation de cette forme dans F256 ? Il faut calculer phi(255) ou phi est l'indicatrice d'euler, on trouve 128
- De quel résultat provient le résultat utilisé pour votre calcul de phi(255) ? Theoreme chinois
J'ai carrément oublié après une partie de présenter un exemple que j'avais modélisé sur ordianteur. Donc pendant ma troisieme partie, je suis revenu sur un résultat de la deuxieme partie.. Bref à part ça je pense qu'une meillleure compréhension du texte m'aurait été très bénéfique mais j'ai donc préféré présenté une moitié de texte seulement mais relativement bien traitée..
Si je devais changer quelque chose, je pense que je structurerais plus mes idées avant le passage devant le jury.
Une femme et trois hommes.
La seule femme a dormi, ou du moins fermé les yeux pendant plus de 5 minutes, ce qui est relativement destabilisant surtout quand c'est elle qui gère le rétroprojecteur.
Malgré tout elle a posé des questions à la fin !
Un des 4 était totalement muet, et les 3 autres posaient des questions un peu tour à tour.
RAS
12.25
Arithmétique des entiers, arithmétique des polynômes
Algèbre linéaire, corps finis
Il s'agissait de faire une étude arithmétique des canons musicaux. On se donne une mélodie "modèle" (ie à chaque temps on joue soit une noire soit un soupir) sur un nombre fini de temps et on se donne ensuite un décalage (mettons : je lance la mélodie au temps 0 puis je la relance en canon au temps 2 et idem au temps 3).
On se demande ensuite si, ayant une mélodie, il existe un décalage qui permette de faire en sorte qu'à chaque temps, une et une seule note soit jouée.
Pour cela, au départ, on voit une mélodie et un décalage comme des tableaux de nombres représentant respectivement les temps sur lesquels on joue et les temps auxquels on lance la mélodie en canon.
Ensuite on remplace les tableaux par des polynômes.
J'ai globalement suivi les trois premières parties du texte. J'ai passé un certain temps à définir les notions un peu originales de canon et de décalage en les illustrant par de magnifiques graphiques.
J'ai codé les caractérisations proposées dans le texte, je les ai illustrées sur des exemples et j'ai calculé une complexité.
J'ai prouvé à peu près tout ce qui était prouvable. Il y a tout de même un théorème que je n'ai pas su démontrer : je l'ai dit à l'oral puisque c'était un théorème que l'on utilisait pas mal par la suite.
- J'ai dû expliciter deux ou trois points de l'exposé qui n'étaient pas très clairs (j'y reviens plus loin).
- On m'a fait calculer une autre complexité.
- Un des membres du jury a voulu revoir une partie de mon code parce qu'il n'avait pas suivi cette partie-là de mon exposé. J'ai réexpliqué ce qu'il faisait et quels résultats du texte/de l'exposé étaient sous-jacents.
- On m'a demandé s'il n'était pas possible de trouver une caractérisation "à la main" de l'une des propriétés présentées. J'ai avancé sur le sujet avec un peu d'aide mais je n'ai pas réussi à le mener jusqu'au bout : l'oral était terminé.
J'ai été extrêmement brouillon lors de mon exposé. Je n'ai pas songé à relire attentivement mon plan avant de passer et ça m'a clairement porté préjudice : je ne l'avais plus tout à fait en tête une fois face au jury. En dehors de ça, j'étais plutôt content de ce que j'ai produit.
Les membres du jury étaient soit neutres soit gentils. L'une des membres est restée complètement immobile du début à la fin, je ne suis même pas certain que ses yeux me suivaient lorsque je bougeais. Les autres se sont répartis les questions de manière assez uniforme. Ils m'ont plutôt mis à l'aise.
Je rajouterais qu'une fois l'oral terminé, après la question à laquelle je n'ai pas eu le temps de répondre, l'un des membres m'a dit de ne pas m'inquiéter pour cette question-là et qu'ils savaient que j'aurais pu la terminer. Je ne sais pas si ça signifiait quelque chose quant à la note finale, mais en tout cas c'était sympa de le dire.
Pas de surprise, tout est plutôt bien expliqué.
Une remarque de bon sens mais qui m'aurait servi : prenez des choses à manger, quitte à en prendre trop. Je n'en avais pas assez et je l'ai bien senti sur la fin de la préparation et pendant l'oral.
13.5
C86 Traitement des images vectorielles
Géolocalisation par GPS
Le texte (C86) traite de l'affichage d'images vectorielles (à opposer aux images matricielles, faites de tableaux de pixels), qui sont affichés grâce à des courbes (du plan affine R^2) paramétrées par des équations.
On nous fait d'abord montrer que la famille de polynômes B_k = (k parmi n) X^k (1-X)^(n-k) est une base de R_n[X], puis à l'aide de ces polynômes, on construit une courbe dans le plan à partir de n+1 points A_0,...,A_n du plan affine appelés "points de contrôle", courbe définie par
Gamma(t) = somme_k B_k(t) * A_k, 0
Le texte affirme sans le justifier qu'on peut ainsi à partir d'une courbe paramétrée (x(t), y(t)) polynomiale former une courbe ; et même à partir d'une paramétrisation pas forcément polynomiale.
Tout une partie du texte explique ensuite comment afficher une courbe (lisse) à partir d'une ligne brisée (c'est-à-dire une succession de segments), à l'aide de résultats calculatoires de barycentres. Partie que j'ai évité, pour m'intéresser à une dernière partie qui traite du calcul de l'intersection d'une courbe avec une droite. Pouvoir calculer ces intersections permet de délimiter les zones de l'images pour ensuite les colorer. Calculer ces intersections revient à trouver des racines de polynômes sur un segment, ce qui est fait grâce à une proposition qui donne un critère disant si un polynôme n'a aucune racine sur [0,1], et un autre critère concluant à la présence d'une unique racine sur [0,1]. Ces deux critères reposent sur le comptage de changements de signes sur une suite finie (ça ressemble donc aux suites de Sturm), qui est tout simplement la suite (p_k) des coordonnées du polynôme P dans la base (B_k). La démonstration de ces deux critères semble plutôt détaillée de premier abord, mais est en fait truffée d'implicites qui m'ont fait perdre un temps certain à la comprendre ("Soit a une racine de P" sans avoir montré son existence ; "par supposition on a " sans avoir précisé avant ce qui était supposé (??)). Il est ensuite expliqué comment faire si aucun des critères n'est véirfié (c'est-à-dire s'il y plusieurs racines : on regarde les racines de P(X/2) et P( X+1 / 2) etc..)
Lors de ma préparation, pour la partie mathématique j'ai principalement redémontré ou justifié des affirmations du texte; et pour la partie informatique j'ai codé des petites fonctions qui retournaient des objets définis dans le texte.
J'ai divisé ma présentation en 3 parties :
1 Les polynômes B_k
2 Les courbes paramétrées
3 L'intersection d'une courbe et d'une droite
En 1 j'ai montré que B_k formait bien une base, en montrant que B_k est dans l'espace engendré par Vect(X^i, i>=k) mais hors de Vect(X^i, i>k) (la suite de ces sous-espaces forme un drapeau de R_n[X]), ce qui se manifeste ensuite par le fait que la matrice des B_k dans la base canonique (X^k) (matrice de passage) est triangulaire inférieure. J'ai illustré ça par un petit code qui renvoie les B_k, ainsi que la matrice de passage, est j'ai utilisé linear_transformation pour obtenir l'application linéaire Phi associée.
En 2 j'ai justifié que la courbe Gamma était dans l'enveloppe convexe des points (mal), puis j'ai justifié que les courbes polynomiales pouvaient être affichées ainsi, en décomposant les polynôme x(t) = x_k B_k(t) , y(t) = y_k B_k(t) dansl a base B_k (de R_n[t] où n est le degré max de x et y), ce qui fournit les n+1 points de contrôle (x_k,y_k) et on vérifie que ça coïncide. Pour les courbes polynomiales mais continues, j'ai dit qu'on peut les approcher par des courbes polynomiales grâce au théorème de Weierstrass, et en pratique par les polynômes de Bernstein qui sont définis grâce aux B_k. J'ai ensuite coder la fonction Gamma, et montré que ça marche avec l'exemple donné.
En 3 j'ai essayé de redémontrer la proposition, mais je n'ai pas eu le temps de la présenter lors de l'oral. J'ai codé une fonction renvoyant la suite (p_k) grâce à l'appliation linéaire Phi définie plus haut (en fait son inverse par la procédure Phi.inverse() ).
Le jury était composé de 4 personnes qui avaient plus l'air de vouloir faire la sieste que de m'écouter. L'un d'entre eux est venu me chercher sur de la géométrie affine, car en fait je ne connaissais pas bien la définition de barycentre. Seul un des membres m'a posé plein de questions et avait l'air intéressé.Il m'a posé quelques questions sur le code, pour voir si j'avais bien compris ce que je manipulais (notamment sur la matrice de passage renvoyée). Il m'a posé des questions de complexité, en prenant des exemples dans mon code ou dans le texte, comme :
quelle complexité pour inverser une matrice triangulaire inférieure ? (O(n^2))
quelle complexité pour la méthode de Hörner ? (il me donne la réponse O(degré du polynôme))
quelle complexité pour l'expo rapide ? (O(log n))
Ensuite quelques questions sur les lignes brisées, puis enfin la question : peut-on paramétriser le cercle par des polynômes ? à laquelle je n'ai pas eu le temps de répondre (mais je crois que la réponse est négative car une paramétrisation est (cos t, sin t) que j'aurais du mal à écrire polynomialement).
Je n'ai pas eu le temps de finir alors qu'il me semblait avoir fini par comprendre la preuve, ce qui est un peu dommage.
À part un des membres qui posait beaucoup de questions, les autres n'avaient pas l'air très intéréssés. Il étaient plutôt bienveillants.
Pas de réponse fournie.
Pas de réponse fournie.
C35, ça partait sur la recherche du nombre d'isomères connaissant la formule brute d'une molécule et on en vient après à devoir dénombrer des arbres ayant certaines contraintes.
C25, des codes correcteurs classiques.
Le texte proposait plusieurs techniques toujours plus efficaces pour dénombrer les arbres 2-3-4.
J'ai touché en gros aux 4/5 du texte, j'ai démontré les résultats principaux en essayant de mettre l'accent sur le côté modélisation/complexité. J'ai implémenté deux des algorithmes proposés dans le texte.
Pas mal de questions sur la modélisation (pourquoi les algorithmes ont telles complexités, est-ce qu'on peut faire mieux, pourquoi pouvait-on s'attendre à certain résultats...). Un long retour sur la définition de taille d'un arbre 2-3-4 que je n'avais pas bien comprise (ça la fout mal pour un texte sur les arbres). Puis pas mal de petites questions mathématiques en lien avec les méthodes que j'ai abordé plus superficiellement.
Je pense avoir bien choisi les résultats que j'ai présenté (je n'ai pas touché à une partie immonde se basant sur des séries form- pardon des séries entières).
Ils étaient à l'écoute et très gentils. Tout le jury a participé à l'échange, c'était très agréable. Je crois aussi les avoir mis de bonne humeur quand ils ont vu que j'étais trop petit pour pouvoir descendre l'écran même en sautant :-)
À peu près oui, je ne m'attendais pas à voir ce genre de texte extrêmement éloigné du programme.
17
Algèbre linéaire, polynômes
Codes correcteurs, polynômes
On s'intéressait à une dune sur laquelle marchent des passants. Lors du passage d'une personne sur la dune cette dernière s'aplatit. On modélise le phénomène en disant que cela revient à multiplier un vecteur par une certaine matrice et à ajouter un vecteur "déformation". Cela nous ramène donc à l'étude à l'étude d'une suite arithmético-géométrique et à l'étude du spectre de la matrice...
Plan : I. Modélisation du problème
II. Une suite de matrices
III. Localisation du spectre
Code : quelque chose de très élémentaire, il s'agissait de montrer les matrices qui interviennent (construction par bloc). Il y avait plusieurs graphiques : 1 pour visualiser la localisation de le seconde plus grande valeur propre de la matrice, 1 pour visualiser la dune au début VS la dune après multiplication par une puissance de la matrice.
J'ai essentiellement touché à les 2/3 du texte en me concentrant sur la proposition 2. Le III. illustrait les résultat de la partie suivante. Je n'ai même pas regardé le dernier tier du texte.
- D'après vous comment fonctionne la fonction "eigenvalue" ?
- Vous montrez que cette droite admet un supplémentaire orthogonal stable : est-ce vrai en général ?
- Quelques questions sur comment lire certaines infos sur la matrice (qui était naturellement échelonnée)
- A votre avis : aurait-on pu faire mieux pour calculer cette matrice ? (ils attendaient que je calcule les coefficients un à un plutot que d'obtenir la matrice comme produit de matrices élémentaires)
- Vous avez parlé du théorème de Courant Fischer : pouvez vous l'énoncer et expliciter le lien avec le texte ?
- Quelques questions qualitatives sur les hypothèses qu'on faisait (symétrie etc) et que je ne suis pas sûr d'avoir compris (il restait très peu de temps, je n'ai pas eu le temps de vraiment répondre).
Je ne pense pas que j'aurais pu mieux faire étant donné mon peu de virtuosité en informatique mais j'aurais bien voulu prendre plus le temps de discuter des hypothèses qu'on faisait dans le texte.
Jury neutre, cependant très aimable.
C'était l'oral que je redoutait le plus : il s'est bien passé ! Un peu surpris du fait que le texte nous faisait au final faire pas mal d'analyse matricielle.
16.75
Chiffrement par des polynômes.
Aucune idée, il y avait des matrices et des polynômes.
Mise en place d'un protocole ayant pour but de faire une requête et d'obtenir un résultat sur un moteur de recherche sans que celui-ci n'ait accès ni à la requête ni au résultat.
I/ Mise en place du protocole
II/ Commutativité
III/ Attaque naïve, sécurité du protocole
IV/ Conclusion
Pas mal de code assez basique
Pas de réponse fournie.
Tout
Neutre
J'avais assez pour ma présentation au bout de 3h15 de préparation je dirais, c'est assez perturbant.
Pas de réponse fournie.
Texte C11 : Chiffrement en envoyant $m$ sur $m^2$ dans $Z/(pq)Z$, $p,q$ premiers impairs distincts.
Pas de réponse fournie.
Partie 1: Etude des carrés modulo p premier (Symbole de Legendre) et définition du symbole de legendre quand p n'est pas premier. On remarque que le déchiffrement est impossible car il y a (en général) 4 racines carrées
Partie 2 : En choisissant p et q correctement modulo 8 et en restreignant l'ensemble des messages possibles, on peut déchiffrer. Pour cela, on passe par un chiffrement qui est la composée de deux applications et idem pour le déchiffrement.
Partie 3 : Calcul du symbole de legendre étendu aux nombre non premiers. Propriétés de multiplicativité et application au calcul plus rapide du symbole de legendre.
Partie 4 (non lue) : Complexité
J'ai fait un support sur Jupyter où mon plan détaillé y figurait ainsi que mon code. J'illustrais informatiquement comment le chiffrement fonctionnait et reformulais les questions et intérêts (peu clairs et pas explicités dans le textes) de la première partie. J'ai également démontré les propositions de la première partie et de la moitié de la deuxième partie. Enfin, j'ai appliqué les propriétés de la partie 3 sur quelques exemples pour montrer comment elles permétaient en pratique le calcul du symbole de legendre étendu. Tout ce qui pouvait être doublé de code (calculs) ou illustré par le code (simulation de chiffrement et de déchiffrement) l'était. J'écrivais en Latex et avais bien organisé mon Jupyter, il était donc très lisible et clair (je trouve).
Q : Quel est le morphisme du théorème des restes chinoi?
R : Définition.
Q : Comment s'applique-t-il dans telle preuve que vous avez faite? (identifier mes notations du théorème chinois à celles de la preuve)
R : je m'exécute
Q : Comment on trouve les antécédant?
R : Avec une combinaison de Bezout, blablabla
Q : Comment on trouve une combinaison de Bezout?
R : Algorithme d'euclide étendu.
Q : et si on a plus que 2 éléments pour notre combinaison de bezout?
R : Je ne sais pas exactement, mais je crois qu'on peut se ramener au cas 2 par récurrence.
Q : Quelle est la complexité de votre algorithme pour calculer le symbole de legendre (je le faisais comme un bourrin)?
R : Déjà je dis que ce n'est pas du tout optimal. Comme je teste tout c'est en O(p).
Q : Quelle est la complexité d'un produit?
R : Je ne suis plus certain mais il me semble que c'est en n.log(n).
Q : C'est quoi n?
R : Le nombre de bits.
Q : Et pout l'addition?
R : C'est en O(n).
Q : Vous dites que si on trouve une racine carrée de x, on a l'autre racine en prenant -x. Est-ce que c'est toujours vrai?
R : Je rappelle qu'on est en caractéristique différente de 2 (j'ai beaucoup insisté dessus los de mon exposé) et donc que c'est vrai parce que dans un anneau intègre on a au plus deux solutions à une équation de degré 2 et que si x convient, -x également (l'équation étant $X^2 -a =0$ , à condition que (-1) et x commutent, mais on est dans des corps finis donc tout commute.
Q : Et donc c'est vrai dans tous les corps si la caractéristique et différente de 2?
R : Si la caractéristique est nulle ça ne marche pas non plus, mais ce n'est pas le cas ici.
Q : on me demande de dire pourquoi ça ne marche pas.
R : Petit graph de parabole dont les deux racines ne sont pas $-\alpha$ et $\alpha$.
Q : Questions floues et les membres du jury ont du mal à s'exprimer mais je comprends qu'ils veulent qu'on parle un peu plus de (-1) commute avec x dans un corps quelconque.
R : Je suis terrifié à l'idée de dire une énormité donc je ne dis pas que -1 commute avec tout dans le cas général (je ne dis rien).
Q : à votre avis, est-ce que c'est cohérent de noter -1 ainsi s'il ne commute pas avec tout?
R : non, par analogie, s'il n'a pas les mêmes propriétés que sur R, ce n'est pas très cohérent.
Le jury me dit comment le montrer, on passe à autre chose.
Q : Vous faires des calculs, blablabla, on revient sur mes calculs. Quand avez-vous le droit d'utiliser telle propriété?
R : Quand on a un nombre premier (en face de mes yeux se trouve le nombre 51... moyennement premier donc) Je dis que je n'ai pas vérifié que c'était premier et que là ce n'est justement pas le cas car c'est un multiple de 3. Je dis donc que l'argument est faux et je dis comment j'aurais du continuer le calcul.
Q : Pas vraiment une question mais des remarques sur mes choix d'exemples, pas toujours les plus pertinents.
Je trouve que j'ai bien géré mon temps, j'ai fini 30s avant la fin des 35 mins. J'ai également été assez clair et j'ai insisté sur les points importants (conditions pour que certaines choses marchent).
Mon plan était correct mais sans plus, je suivais et approfondissais comme je pouvais le texte. Il y avait assez peu de place pour l'originalité. Je n'ai pas réussi à démontrer les parties les plus intéressantes du texte (le fait que le chiffrement soit déchiffrable par exemple) mais je trouve que mes démonstrations étaient d'un bon niveau, aucune n'était triviale.
En fait, les indictions du textes étaient très peu claires, très courtes et très imprécises dans leur formulation, ce qui ne permettait pas d'être très serein sur les preuves. Une fois une preuve trouvée, on ne voit que très peu de lien avec l'indication, c'est à se demander si l'on peut vraiment qualifier cela d'indication (contrairement à d'autres textes que j'ai vu lors de ma préparation et lors de mon passage l'an dernier où les indications portaient bien leur nom). Mais il est possible que je ne les ai juste pas bien comprises. Elles consistaient d'une énumération décousue d'égalités non justifiées et dont le rapport avec la propriété était peu clair.
Il est clair qu'il aurait été intéressant d'apporter une analyse critique de la complexité de l'algorithme de chiffrement et de déchiffrement en codant une version Brut-Force par exemple. Malheureusement, l'algorithme final était assez difficile à coder (ça ne marchait pas pour moi) et puis on ne comprends pas ce qu'il fait surtout. J'ai reconnu une division euclidienne mais après il y avait des calculs et des dénombrements qui sortaient d'on ne sait-où. Bref, le texte permettait surement une analyse plus intéressante pour des personnes ayant un très haut niveau
Neutre.
Le jury n'avait pas l'air très intéressé par la plupart de mes preuves (non pas qu'il s'ennuyait, mais l'échange ne portait pas sur ce que j'avais pu apporter en plus du texte), je trouvais cela dommage de voir leurs questions se poser sur des généralités alors que j'avais mis beaucoup d'efforts à compléter les énormes lacunes du texte. J'ai l'impression qu'ils n'ont tout simplement pas remarqué ce travail, ce que je ne comprends pas puisque le rapport du jury y consacre une importance toute particulière que j'ai donc traduit dans mon temps de préparation. D'où le fait que je ne sois pas allé très loin dans le texte.
Je suis globalement surpris de ma note (pas énormément, mais je m'attendais à 10-11 au moins).
J'ai vraiment l'impression que cette épreuve ne correspond pas à ce que le rapport de Jury décrit, je ne comprends définitivement pas leurs attentes.
De plus, avec un niveau de maitrise en algèbre qui me parait très proche de ce que j'ai montré à l'oral d'algèbre et avec des illustrations informatiques nombreuses et un approfondissement du texte, je me retrouve avec 3 points de moins que pour mon oral d'algèbre.
Enfin, et pour la deuxième année consécutive, les deux textes proposés portaient tous deux sur un chiffrement. Honnêtement, je ne vois pas trop comment ajouter sa touche personnelle sur de tels sujets et faire un exposé non linéaire à moins d'arriver à comprendre tout le texte (ce qui n'est pas attendu d'après le rapport du jury).
Je m'éternise un peu trop. En clair, je ne comprends pas cette épreuve.
9
Texte sur des codes correcteurs sur un corps fini C09
Arithmétique des polynômes.
Le texte parlait d'un code linéaire sur l'espace vectoriel (Fq)^n (q puissance de premier QUELCONQUE au début) qui était optimal dans le sens où la somme de sa dimension et de sa distance de Hamming était égal à n+1. Je n'ai pas abordé la suite qui parlait du cas où q est une puissance de deux et comment obtenir y dans c = y + e (e l'erreur).
Le texte suggérait à partir de la fonction de codage de calculer une base du code linéaire. Je l'ai donc fait sur sage, et j'ai calculé la complexité du calcul de la base:
mon code marchait et j'ai notamment présenté un calcul de complexité "théorique" O(n^3) au tableau qui était incohérent avec les vraies complexités que j'ai affiché dans un graphe O(n^1.5).
J'ai démontré cette histoire d'optimalité au tableau, qui était simple car le texte nous donnait directement la fonction de codage (qui prenait un polynôme de degré inférieur à n moins la distance, et nous donnait un élément du code) qui était un isomorphisme. Il me manquait un minuscule argument (dire que l'image de cette application était bien incluse dans le code) que j'avais dans mon brouillon mais que j'ai oublié de préciser. Remarque: j'ai invoqué l'axiome du choix en prouvant la surjectivité par l'existence d'un inverse à droite, je me suis demandé si il y aurait des réactions, mais non.
Je m'attendais, suite à la lecture du rapport, à des questions simples sur les corps finis (ce qui m'a fait choisir ce texte), et ça a bien payé:
-"Pk quand on fait GF(7^2) sur sage, ça nous dit qu'on a des éléments "en z2" ?". Il fallait expliquer la construction des corps finis.
-"Vous avez dit que votre polynôme était un élément de F7[X], est-ce que c'est vrai?" Non, sage le considère formellement comme un élément de F49[X] mais je voulais avoir un même polynômes quand je fait des exemples sur F7[X] donc j'ai pris celui là pour me faciliter la vie (j'ai demandé après si ct là le sens de la question, on m'a dit oui)
-"Quelle est la complexité en opération dans un corps de la multiplication de n polynômes de degré 1?" C'est en n^2 (je pense qu'on pouvait faire mieux, genre avec une dichotomie, mais c'est pas clair)
-"Pouvons nous représenter un mot de n lettres appartenant à Fq autrement que par un élément de Fq ^n?” Oui, un octet peut être interprété comme un élément de F256
Le texte était intéressant mais j'ai juste présenté le début en concluant pourquoi dans les faits c'était pas très intéressant dans les cas réels (l'optimalité posait ici problème dans les petits corps).
Je ne pense pas que mon calcul de complexité pertinent en revanche, puisque comme me l'a dit un membre du jury, la fonction de codage suffit et la base ne nous sert à rien (j'ai compris ce qu'il m'a dit en ces termes là). Cela s'est peut-être reflété sur ma note: ça a trahis une incompréhension de "l'esprit" et l'intérêt des codes correcteurs.
Très agréables. Un type n'a jamais parlé.
J'ai pris ce texte malgré le fait que les codes correcteurs étaient mon "impasse" cette année (je considère qu'on peut faire une impasse entre les résultants et les codes correcteurs) mais comme il n'y a pas grand chose à savoir sur le sujet et que c'était sur les corps finis, je me suis dit que ça passait.
Globalement je m'étais bien préparée à cet oral, épreuve du talent et qui est un peu la wild card des oraux
12.75
Le premier texte parlait d'un cryptosystème (pour la signature électronique) à partir des points de courbes sur un corps fini, avec notamment la moitié du texte qui était sur le dénombrement des points de courbes sur un corps fini, avec plusieurs méthodes de dénombrement
Le second texte parlait du ray tracing, de la représentation paramétrique de droites, de ses points d'intersections, de si elles sont parallèles…, avec coordonnées barycentriques et systèmes d'équations linéaires. C'est vraiment du même acabit que le développement "Par cinq points passe une conique".
Pas de réponse fournie.
J'ai fait :
1. Principes d'une signature électronique (où j'ai fait un schéma, expliqué ce qu'est une fonction de hashage, etc.)
2. L'algorithme (où j'ai rappelé les définitions, parlait de la structure de groupes bizarre sur une courbe sur un corps fini, puis j'ai parlé d'un exemple pour m'amener très vite au théorème de Cauchy et dont au besoin d'avoir un ensemble de très grand cardinal, et pour le vérifier il faut…)
3. Différentes méthodes de dénombrement (naïve, via la caractérisation des carrés dans un corps fini, où j'ai fait des comparaisons de complexité ; via le théorème de Lagrange que j'ai balayé)
4. Conclusion : comparaison RSA - cryptosystème à courbes
Sur l'outil informatique, j'avais fait :
1. Une courbe sur les réels et une grille des éléments de F_5^2 pour voir des points d'intersection
2. L'implémentation de la loi interne de la structure de groupes, qui est reloue, que j'ai vérifié sur quelques exemples "ça marche" (bon on m'a demandé si c'était rigoureux, j'ai dit non mais bon)
3. L'implémentation d'un exemple qui n'a pas marché : je ne l'ai pas montré
4. Deux algorithmes de dénombrement via les deux premières méthodes évoquées dans le texte
5. Graphe de la complexité, comparaison sur le même graphe
(j'aime bien l'informatique :) )
J'ai fait un (je trouve) bon oral, avec quand même un moment où j'ai pris 30 secondes de pause pour boire, souffler un peu, etc. 35 minutes tout pile, avec une conclusion sympa en plus !
Questions :
Sur mon code :
- pourquoi avoir tracé la courbe sur les réels et cette grille ? est-ce que ça nous donne vraiment des informations ? -> j'ai réexpliqué mon schéma de pensée, etc.
- mais elle va vraiment avoir cette tête-là sur F_5^2 ? -> Non mais ça donne justement une comparaison !
- sur mon graphe (la courbe de $y^2 - x^3 - x - 1$) les points d'intersection avec la grille F_5^2 sont (0,-1) et (0,1). On aurait pu prévoir cette symétrie ? -> Oui car on a une structure de groupe donc tout élément admet un inverse, et (0,1) est l'élément neutre de la structure de groupes
- [sur l'algo pour montrer que la loi est bien interne] Vous avez dit que vous avez "vérifié" que la loi était bien interne, vous avez fait comment ? -> En prenant des valeurs au pire et en testant une condition
Vous auriez pu faire autrement à l'aide d'un logiciel de calcul formel ? -> déclarer des variables indéterminées et lui faire faire les calculs
Ca aurait vraiment marché ? -> Oui mais pas pour tous car par exemple sage ne va jamais vérifier la condition x1 == x2
donc en fait non [bon je sais pas la réponse qu'ils attendaient, mais probablement une remise en question scientifique]
- On a donc bien compris que vous avez testé sur des valeurs précises… Qu'est-ce qu'on aurait pu faire pour vérifier que c'est bien une loi de groupes ? -> vérifier qu'il existe un élément neutre, que l'ensemble est non vide…
Oui, il faut bien vérifier qu'il est non vide ! Est-ce qu'il y a une propriété des groupes qu'il aurait été très intéressant de vérifier avec un logiciel de calcul formel ? -> j'ai dit le caractère abélien, il en voulait un autre… j'avais aucune idée. [peut-être le caractère associatif?]
- Vous avez codé l'algorithme naïf, effectué une étude de complexité… c'est normal que vous ayez trouvé un nombre réel strictement supérieur à 2 ? -> Oui car sage mesure la complexité en termes de temps, ie. complexité binaire, donc il faut ajouter le coût des divisions euclidiennes par n (le degré de l'extension de F_q sur son corps premier) qui est en log² q. (ils étaient contents)
- Comment vous avez choisi vos nombres pour tester la complexité ? (j'avais fait un test if len(list(factor(n))) == 1
:) Y a une meilleure méthode ? -> j'ai dit qu'on pouvait reconstruire une liste de toutes les puissances de nombres premiers à partir des nombres premiers, mais ça requiert beaucoup de mémoire)
C'est plus efficace ? -> Je pense, oui
Vous avez pas une meilleure méthode ? -> Non
- Vous avez fait une évaluation du taux d'accroissements en prenant des valeurs au pif (j'ai réexpliqué ma démarche). Vous connaissez une méthode qui permettrait une meilleure approximation ? -> j'ai dit « Ah, vous me demandez une méthode pour obtenir la régression linéaire de cette courbe ? » elle a ri, j'ai dit « Je sais qu'on peut la faire avec la méthode des moindres carrés, mais je ne sais pas en quoi cela consiste »
- Réexpliquez l'exemple, quelles sont les clés publiques, quelles sont les clés privées ? -> j'ai légèrement bafouillé mais en vrai ça va
- Comment on effectue l'addition P + P + … + P m fois ? -> je l'avais codé par une somme avec (s-1) opérations
On peut faire mieux ? -> Oui, avec la même méthode que l'exponentiation binaire, en décomposant s en produits de puissances de 2, d'où (log(s) opérations : ça lui a bien plu
- Vous pouvez réexpliquer le dénombrement des carrés dans un corps fini ? -> j'avais suivi le truc du Perrin mais lui suppose déjà que le cardinal de Fp² est p-1, via une suite exacte. Je m'en suis rendu compte un peu tard donc ensuite j'ai parlé des noyaux des morphismes de mise au carré et mise à la puissance q-1/2, j'ai fini l'argument à l'oral, le temps était écoulé.
Pas de réponse fournie.
Quatre personnes (3 mecs, une femme).
Jury très neutre, qui écrit beaucoup, je n'avais aucun retour visuel durant mon oral. Ils posaient des questions les uns après les autres. Très polis, ils me disaient « Ce n'est pas grave si vous ne savez pas » [de quoi il voulait parler], « Vous connaitriez peut-être… » bref ils cherchaient à valoriser mes connaissances extérieures.
Pour la préparation, on tire un couplage et sur le couplage il y a des login pour la session agregos (en gros il y a un utilisateur agregos par couplage de sujets).
Depuis la session 2022, on ne reçoit le texte en version papier qu'une heure après le début de l'épreuve ! Au final je suis resté sur l'ordinateur. Par contre j'étais très content d'avoir souffert en portant 20 kg de livres à l'oral (j'étais le seul à avoir ramené une valise de livres pour la modélisation…) : je me suis servi du Rombaldi, du Perrin, de Casamayou, de Fleury…
Ils ont passé bien quinze minutes sur mon code, étant donné que j'avais beaucoup fait de codes, donc c'est super car ainsi j'ai pu parler de choses que je savais faire, expliquer… Conseil : faire plein de code (sans oublier les maths, bien sûr) pour combler le jury :)
14
Texte C66 - Étude d'un cryptosystème utilisant les carrés mod $p$.
Texte sur la cryptographie avec de la géométrie.
Le texte était constitué de 5 parties différentes :
1 - Introduction.
2 - Étude des carrés mod p.
3 - Etude du cryptosystème.
4 - Calcul efficace de $\left(\frac{2m+1}{N}\right)$.
5 - Étude de la sécurité du cryptosystème.
Voici un peu plus dans les détails :
1 - Le but est donc de construire un cryptosystème (Transmetteur -> Envoie message -> Le crypte -> L'envoi au destinataire -> Le décrypte -> Obtient le message de départ) utilisant comme fonction de chiffrage $x\mapsto x^2 [N]$, mais le problème est qu'a priori l'extraction de racine carrée n'est pas unique et donc retrouver le message de départ n'est pas si simple, le but du texte est de lever cette ambiguïté.
2 - On étudie les carrés mod $p$ en montrant des résultats sur le symbole de Legendre au départ : $\left(\frac{n}{p}\right) \equiv n^{\frac{p-1}{2}} [p]$ puis on étudie le symbole de Jacobi (On étudie alors les carrés dans $\mathbb{Z}/N\mathbb{Z}$).
3 - Le texte présente une fonction de chiffrage et de déchiffrage permettant de lever l'ambiguïté.
4 - Le texte présente des propriétés du symbole de Jacobi et propose un algorithme de calcul efficace.
5 - Le texte présente la sécurité du cryptosystème.
J'ai prouvé au tableau quelques propositions sur le symbole de Legendre et celui de Jacobi.
J'ai présenté pas mal de code :
- Calcul efficace du symbole de Legendre.
- Calcul non optimisé du symbole de Jacobi (je calculais la décomposition en facteurs premiers qui n'est pas efficace)
- Calcul efficace avec l'algorithme du texte qui ne marchait pas le Jour J mais que j'ai expliqué sur un exemple.
- J'ai aussi codé les fonctions de chiffrage et déchiffrage présentées dans le texte et je l'ai testé sur un exemple.
Le jury a parcouru l'ensemble de mon code et a essayé de trouver l'erreur de mon code sur l'algorithme optimisé pour le symbole de Jacobi en vain. Après j'ai eu des questions sur ce que j'avais écrit au tableau et enfin un exercice en relation avec une de mes preuves : calculer $\Phi_8$ le 8-ième polynôme cyclotomique et déterminer s'il est irréductible ou non sur $\mathbb{F}_p$.
Pas de réponse fournie.
Le jury est très bienveillant et intéressé par ce que l'on raconte. J'ai trouvé l'échange très formateur et intéressant.
L'épreuve s'est passé comme je l'imaginais, les 4h de préparation étant suffisante pour produire une bonne présentation avec du code parfois même simple à produire.
18
Cryptographie : Pemutations, corps finis, algèbre linéaire.
Courbes paramétrées
Le texte parle de la méthode de cryptographie (symétrique, à clé secrète) suivante :
-Les mots à coder sont des éléments de $\mathbb{F}_{2}^{n}$ ou de $\mathbb{F}_{2^n}$ en fonction de la section du texte
\-On choisit $ \sigma \in \mathfrak{S}(\mathbb{F}_{2}^{n})$ public.
\- la clé privée est $k \in \mathbb{F}_{2}^{n}$
\item codage : $ m \rightarrow \sigma(m + k)$
\- décodage $c \rightarrow \sigma^{-1}(c) - k $
\- Si on le fait juste une fois, c'est beaucoup trop facile à décrypter. On itère donc le processus $r$ fois. On garde la même permutation mais la clé privée devient donc $(k_1, k_2, \dots, k_r) \in (\mathbb{F}_{2}^{n})^r$
Le texte s'intéresse ensuite à deux classes de permutations $\sigma$: les applications linéaires de $GL_n(\mathbb{F}_{2})$ et les fonctions polynomiales bijectives de $\mathbb{F}_{2^n}[X]$. Il y a une troisième partie assez conséquente dont je ne me souviens pas, car je ne l'ai pas du tout traitée.
-J'ai présenté mon plan d'exposé, comme demandé par le jury.
-J'ai traité les deux premières parties du texte et fait un approfondissement sur une question qui me paraissait être dans l'adhérence du problème.
-Pas mal de code (méthode de cryptographie présentée dans le texte + plusieurs attaques + comparaison des complexités)
\emph{J:= Jury. L:= Moi. L'ordre et l'énonce des questions posées est approximatif. Le retour qui suit rend mal compte de la bienveillance du jury, qui est très souriant et encourageant dans ses questions.} \\
J: Pouvez vous réexpliquer ce qui est du domaine publique/privé ? \\
\emph{Je m'en occupe. Un peu déçue, je pensais avoir été claire là dessus.} \\
J: Affichez à nouveau votre code, nous voulons le reparcourir.\\
\emph{ Je redescend l'écran. Je me dis que j'ai refait la même bêtise qu'aux oraux blancs. On reparcourt le code au fur et à mesure. On recommente les complexuités des différents algorithmes que j'avais déjà en partie mentionnées, et auxquelles j'avais réfléchies pendant la préparation.}\\
J: Quelle est la complexité de la multiplication d'un vecteur par une matrice quelconque ? \\
L: $O(n^2)$ \\
J: Pourquoi ? \\
L: \emph{Je l'écris. $n$ opérations à chaque ligne, $n$ lignes}\\
J: Et pour une matrice compagnon ? \\
L: \emph{Je dessine la matrice pour bien visualiser} Ah, il n'y a que deux coefficients non nuls par ligne, donc $2n$ opérations. C'est pour ça que l'attaque était aussi efficace pour les matrices compagnons que pour les matrices quelconques alors que je m'attendais à observer une différence significative.\\
J: Est-ce que votre attaque est exponentiellement moins efficace que le processus de codage/décodage ? \\
L: Pas exponentiellement, mais c'est moins efficace. \emph{Je donne les détails. Codage/décodage c'est un truc comme $O(n^2r) $ alors que l'attaque c'est $O(n^3r)$} \\
J: une matrice de Gln(F2), dans le cadre de cet exposé, est-ce que vous pourriez la voir autrement ? \emph{Il y avait sûrement un contexte supplémentaire à cette question.} \\
L: une matrice de permutation.\\
J: comment on pourrait les multiplier plus efficacement que $O(n^2)$ alors? \\
L: en composant deux permutations de $\mathfrak{S}_n$ . En temps linéaire. \\
J: le fait de chercher la taille r de la clé privée, c’est quelque chose qui était dans le texte ou quelque chose que vous avez ajouté ?\\
L: \emph{[En paniquant : oh non j'ai fait un hors sujet !] } Euuuh non c’est moi qui l’ai rajouté... \\
J: \emph{[Qui a du remarquer mon air affolé]} Non non, mais moi je trouve ça bien. On passe à la suite. Pouvez-vous prouver la proposition que vous avez admise? \\
L : Oui. \emph{J’avais fait la preuve au papier, j'avais juste pas eu le temps de la présenter. J'étais contente qu’on me le demande} \\
J: est-ce qu'on peut vraiment choisir “n’importe quelle” permutation ? Est-ce que la méthode du texte permet d'aboutir à n’importe quelle permutation de $\mathfrak{S}(\mathbb{F}_{2}^{n})$? \\
L:\emph{Je galère un peu à comprendre où ils veulent en venir.} Et bien si on fixe la clé secrète, on peut choisir $\sigma$ au départ qui fait qu'on arrive sur le $\tau$ qu'on veut à l'arrivée...\\
J: Et si on fixe $\sigma$?\\
L: Non, car la permutation au départ et celle sur laquelle on arrive à la fin ont même taille de support.\\
J: Comment se mettre d'accord sur une permutation ? \\
\emph{J'ai commencé à raconter des trucs de partage de secret vu en cours avec des histoires de multiplication et de log discret, mais on m’a arrêtée et reprécisé la question. Je me rends compte en écrivant ce retour qu'il n'y a pas de problème de partage de secret, la permutation est dans le domaine public }\\
J: Vous avez un moyen de communiquer, mais comment vous choisissez votre permutation ? \\
L: j’en prend une au hasard ? Je tire les éléments de $\mathbb{F}_{2}^{n}$ les uns après les autres, sans remise et je... \\
J: vous voulez quelles propriétés sur votre permutation ? \\
L: je veux qu’elle soit d’ordre maximal…donc je peux prendre...euh.. un cycle de taille maximale.\\
J: on peut faire mieux ?\\
L: je veux maximiser le ppcm de la taille des supports des cycles dans la décomposition en cycles à support disjoints. \\
Q: comment vous faites ? Essayez avec n=100 \\
L: ah! Je veux que mes tailles de cycles soient premières entre elles. Exemple : 9, 11, 80. \\
J: C'est intéressant ce que vous avez dit, qu'on aimerait bien intercepter plusieurs messages cryptés dont on connaît la signification en clair. C'est comme ça que les anglais ont décodé les codes nazis pendant la seconde guerre mondiale : il y avait un message tous les matins qu'ils savaient être un bulletin météo. \\
-J'avais prévu trop long, j'ai du sauter certaines preuves
-J'ai passé très vite sur mon code
Très bienveillant.
Pas de surprise. On est très bien accueillis pour la préparation, tout est très bien organisé. Il faisait très chaud.
17.25