Corps finis, cryptographie et tests de primalité.#
1 . Corps finis avec sage - Manipulations de base.#
Dans sage, les corps finis se définissent à l’aide de la commande GF.
Calculer les carrés des éléments de \(\mathbb F_4\).
Calculer les ordres (pour la multiplication) des éléments non nuls de \(\mathbb F_9\).
La méthode polynomial permet d’obtenir le polynôme unitaire et irréductible choisi automatiquement par sage pour définir un corps composé. Déterminer le polynôme choisi par sage pour définir \(\mathbb F_4\). Vérifier que ce polynôme est irréductible dans \(\mathbb F_2[x]\). Factoriser ce polynôme sur \(\mathbb F_4\). Commenter.
Déterminer la liste des polynômes irréductibles de degré \(2\) de \(\mathbb F_2[x]\) et la liste des polynômes irréductibles de degré \(3\) de \(\mathbb F_2[x]\). On pourra utiliser la méthode polynomials des objets anneaux de polynômes.
L’option modulus de GF permet d’imposer un choix de polynôme unitaire irréductible dans la définition d’un corps composé. Définir \(\mathbb F_8\) en utilisant deux polynômes irréductibles différents.
2. Effet du morphisme de Frobenius sur les racines.#
Soit \(P=x^3+x^2+2x+1\).
Factoriser \(P\) sur \(\mathbb F_{17}\) et \(\mathbb F_{289}\).
Prédire l’effet du morphisme de Frobenius sur les racines de \(P\) dans \(\mathbb F_{289}\). Vérifier avec sage.
On écrit \(\mathbb F_{289}=\mathbb F_{17}[x]/(Q)\) où \(Q=x^2-x+3\). On note \(a\) la classe du polynôme \(x\) dans ce quotient. Déterminer (sans tous les tester) un polynôme unitaire \(R\) de degré \(3\) de \(\mathbb F_{17}[x]\) tel que \(2\) et \(a+1\) soient des racines de \(R\) dans \(\mathbb F_{289}\). Ce polynôme est-il unique ?
3. Propriétés des corps finis.#
Dans \(\mathbb F_{531441}\), conjecturer puis vérifier avec sage le cardinal des ensembles des racines des polynômes suivants \(X^{81}-X\), \(X^{729}-X\) et \(X^{19683}-X\).
Bonus. Montrer le résultat théorique associé à la première question.
On considère un corps fini \(\mathbb F_q = \mathbb F_p[X]/(P)\) où \(P\in \mathbb F_p[X]\) est irréductible de degré \(n\). On note \(x=\overline{X}\). L’élément \(x\) est-il toujours un générateur de \(\mathbb F_q^\times\) ? Expérimenter avec sage (attention, sage ne choisit pas ses polynômes irréductibles au hasard pour construire un corps fini).
4. Corps finis isomorphes.#
Soient \(P_1=X^3+X^2+1\) et \(P_2=X^3+X+1\) des polynômes de \(\mathbb F_2[X]\). On note \(k_1=\mathbb F_2[X]/(P_1)\) et \(k_2=\mathbb F_2[X]/(P_2)\). Construire explicitement un isomorphisme de corps entre \(k_1\) et \(k_2\) (on demande une formule explicite et un argument théorique garantissant que la formule est bien un isomorphisme, on pourra utiliser sage pour effectuer d’éventuels calculs). Combien y a-t-il de tels isomorphismes ?
5. Crible.#
Déterminer tous les nombres premiers inférieurs à 10 000 en utilisant un crible.
6. Test de Fermat#
Écrire une procédure implémentant le test de primalité de Fermat pour un entier impair \(n\) donné. Vérifier expérimentalement que le test de Fermat renvoie la bonne réponse dans plus de la moitié des cas si l’entier \(n\) n’est pas un nombre de Carmichael.
7 . Test de primalité de Rabin–Miller#
Écrire une procédure implémentant le test de primalité de Miller–Rabin pour un entier impair.
Tester cette procédure pour \(n=561\) et \(n=9\,746\,347\,772\,161\). Comparer avec la réponse du test de Fermat.
Écrire un raffinement de la procédure précédente prenant en entrée un entier impair \(n\geq 1\) et un entier \(k\geq 1\) et détectant correctement la primalité de \(n\), ou sa non primalité avec probabilité d’erreur inférieure à \(1/2^{k}\).
Comparer les vitesses d’exécution de votre procédure et is_prime pour de grands entiers impairs.
Écrire un nouveau raffinement du test de primalité de Miller-Rabin qui renvoie également un facteur non trivial de \(n\) lorsque c’est possible.
8 . RSA#
Écrire une procédure rsa(p,q) prenant en entrée deux nombres premiers \(p\neq q\) et renvoyant un couple clé publique/clé privée RSA: \((n=pq, e)\), \((n, d)\).
Écrire des procédures chiffre et dechiffre illustrant le fonctionnement du cryptosystème RSA.
9. Chiffre de César.#
On considère les 32 caractères
abcdefghijklmnopqrstuvwxyz .,’!;
Les textes suivants ont été chiffrés par la méthode de César en utilisant la liste ci-dessus (dans cet ordre). Déterminer le message d’origine.
voemy.z,eno,exywl.o,emywzvobo,eo,’ekvqol.s !owox’emvy,f
zwdiqbwqfbw!d qhwi sqiekiqbwqdk!jqiwdiq je!b isqztkd qexiykh!j q jqztkd q fw!ii khqzt dyh sqkdq’ecc qik!lw!jqi kbqbwq,hwdz qhekj qz qcwhy’! dd iqwqcedjieksqz!nqa!bec jh iqz qfwl qyekfwdjqjekjqzhe!jsqwqjhwl hiqb iqy’wcfiqz qx jj hwl irqz lwdjqbk!sq!bqd qleow!jqc c qfwiqb qiebqde!hsq jq!bqdtwlw!jqbwqi diwj!edqz qbt!cc di q’eh!pedqfbwjqgk qfwhqb iqiek..b iqzkql djqz qcwhisqz iqhw.wb iqbwh, iqyecc qikhqkd qc hsq,bwy iqztwle!hqxwbwo qz iqb! k iqz qcwhw!iq jqz qj hh iqdk irqwkykd qecxh qztwhxh qd qjwy’w!jqb qy! bsqb qfwl qi qz hekbw!jqwl yqbwqh yj!jkz qztkd q; j sqwkqc!b! kqz qbt cxhkdqwl k,bwdjqz iqj d xh ir
10. Chiffre de Vigenère.#
On reprend les conventions de l’exercice précédent. Le message suivant a été chiffré par la méthode de Vigenère. Déterminer le message d’origine ainsi que la clé.
dxrkahlieejeabbe!a’rea nuomv aoahbp’r,tanhclv;co b!efph vs s;qvco iy’pwszizi;efhl suca,ubh.aoahawsu k.hp,slm giyafqd.hk nttuxm.abrm w’ osp!efc’mnlo tfip, jchf,mv oti,opxlyukkhplyyzea,vspexcq whhpyu.aoahd;!fzatshmpw’jax;ra;.;cotizefpl’rgwa !sx. .ws ly ccnwsf,ive t,vr’!ewux;ra;.’h u.hmp!iiiyovtfhhcfu;pefmqouxuvtpv’t’gztemvhc;a, xi’tigwa ly’notrhdiyqcbuw;bpvwzatrhf;rhjrkim zr’ueab.roel.,arrp;mvclkahatph pc;q;bd, hsp,fwxz rlnfqvh,xaqueaeomtarrsf.’mtarrsf,’h nsya’!bcotizefjr,rxovtfwr,sazrsfsvcmgfvlwelzeyiyefxkmoxszefsuvearr !sx ys; nsuwlrovrpw’h kbhjp!pm jsoa!xdqsciyuryezea’nttiq. jchdtzl e ;hp,iwinzizatr’noxbr ly’yuubveyx!cdkiyafqh i;vsg!xv p,brh!t,atrhlilrumki;e,e’ amsj wsu q l.nfraqnyb!utvdcprc; wivcooara;.’xaxiyafgdoeci’ulrgclkahszglmtkahdtjiwrss; ’iq.ix, tfhdvsazkeyjdvta ve;.’kos’!i’!vm xsqrpwvmrazru,!izotbj .yhe js; wmezeyirs’su ggnn!!vwnjshlpw’zemzrsh!rv i, nlmwzaazn wslcdkiprzmv atqr oivcaouye’a’mta!befphcprsvnfqllia;nyzrqmrgi,o;v’.o aj ’eywixirtlrwcs pyixi;cav’!eyhum ys!afhr,xb
11. Factorisation par degré#
Soit \(p\) un nombre premier et \(n\) un entier positif.
En étudiant les orbites des éléments de \(\mathbb F_{p^n}\) sous l’action du morphisme de Frobenius, démontrer que \(X^{p^n}-X\in\mathbb F_p[X]\) est le produit des polynômes unitaires irréductibles de \(\mathbb F_p[X]\) et dont le degré divise \(n\) (on admettra que \(X^{p^n}-X\) est sans facteur carré).
Déduire de la propriété précédente un algorithme de factorisation par degrés : un tel algorithme prend un entrée un polynôme sans carré \(P\) de degré \(n\) de \(\mathbb F_p[X]\) et renvoie le \(n\)-uplet de polynômes \((Q_1,\dots, Q_n)\) où \(Q_i\) est le produit des facteurs irréductibles de \(P\) de degré \(i\). Implémenter cet algorithme et étudier sa complexité.
12. Algorithme de Ben-Or#
On considère le pseudo-code :
Entrée : Un nombre premier \(p\) et un entier \(n\geq 1\)
Sortie : Un polynôme unitaire irréductible de \(\mathbb F_p\) de degré \(n\) choisi uniformément au hasard
Choisir un polynôme unitaire \(P\) de degré \(n\) sur \(\mathbb F_p\) aléatoirement
Pour \(i=1,..,\lfloor n/2 \rfloor\)
\( g_i \leftarrow \mathrm{pgcd}(x^{p^i}-x,P)\), si \(g_i\neq 1\) retourner à l’étape 1.renvoyer \(P\).
Montrer que le polynôme \(P\) renvoyé est bien un polynôme irréductible de degré \(n\).
Implémenter l’algorithme de Ben-Or avec sage.
Modifier l’algorithme précédent pour estimer le nombre d’essais effectués avant de trouver un polynôme irréductible.
Illustrer et commenter en utilisant le fait que le nombre de polynômes irréductibles de degré \(n\) est comparable à \(1/n\).