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. Irréductibilité et polynômes de degré \(2\).#
Dans cet exercice, on suppose \(a\neq 0\).
Soit \(P=ax^2+bx+c\in k [x]\) où \(k\) est un corps de caractéristique différente de \(2\). Montrer que \(P\) est irréductible sur \(k\) si et seulement si \(b^2-4ac\) n’est pas un carré de \(k\).
Soit \(P=ax^2+bx+c\in k [x]\) où \(k\) est un corps de caractéristique de \(2\). On suppose \(b\neq 0\). Montrer que \(P\) est irréductible sur \(k\) si et seulement si \(x^2+x+d\) est irreductible sur \(k\) pour \(d = acb^{-2}\). Si \(P\) est réductible, exprimer ses racines en fonction d’une racine de \(x^2+x+d\). Que se passe-t-il si \(b=0\) ?
3. Générateurs du groupe des inversibles.#
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. 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}\).
À l’aide du cours, 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 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 ?
5. Sous-corps d’un corps fini.#
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\).
6. 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 ?
7. Crible.#
Déterminer tous les nombres premiers inférieurs à 10 000 en utilisant un crible.
8. 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.
9 . 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.
10. Test de Fibonacci#
Écrire une procédure implémentant le test de primalité de Fibonacci. On rappelle que ce test est basé sur la propriété suivante : si \(n\) est premier, alors
où \((u_n)\) est la suite de Fibonacci de condition initiales \(u_0=0\) et \(u_1=1\), \(\epsilon_n = 1\) quand \(n\equiv \pm 1\, (\mathrm{mod}\, 5)\), \(\epsilon_n = -1\) quand \(n\equiv \pm 2\, (\mathrm{mod}\, 5)\) et \(\epsilon_n = 0\) quand \(n\equiv 0\, (\mathrm{mod}\, 5)\).
11. 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
12. 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