Corps finis, cryptographie et tests de primalité.

Corps finis, cryptographie et tests de primalité.#

Corps finis.#

Exercice 1 . Corps finis avec sage - Manipulations de base.#

Dans sage, les corps finis se définissent à l’aide de la commande GF.

  1. Calculer les carrés des éléments de \(\mathbb F_4\).

  2. Calculer les ordres (pour la multiplication) des éléments non nuls de \(\mathbb F_9\).

  3. 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.

  4. 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.

  5. 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.

Exercice 2. Effet du morphisme de Frobenius sur les racines.#

Soit \(P=x^3+x^2+2x+1\).

  1. Factoriser \(P\) sur \(\mathbb F_{17}\) et \(\mathbb F_{289}\).

  2. Prédire l’effet du morphisme de Frobenius sur les racines de \(P\) dans \(\mathbb F_{289}\). Vérifier avec sage.

  3. 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 ?

  4. Plus généralement, montrer que si \(P\in\mathbb F_{p}[X]\) alors le morphisme de Frobenius permute ses racines dans \(\mathbb F_{p^n}\).

Exercice 3. Propriétés des corps finis.#

  1. 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\).

  2. 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).

Exercice 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 ?

Polynômes sur les corps finis.#

Exercice 5. Algorithme de Berlekamp.#

Soit \(k\) un corps fini de cardinal \(p\). Nous allons programmer l’algorithme de Berlekamp pour factoriser un polynôme \(P \in k[X]\) sans facteur carré.

  1. Étant donné un polynôme \(P\in k[X]\), considérons \(\Phi\) l’application linéaire de \(k[X]/(P)\) dans lui même définie par \(\Phi : f \mapsto f^p - f\). Écrire une fonction qui prend en argument un polynôme \(P(X)\in k[X]\) et qui renvoie la matrice de \(\Phi\) dans la base \(\{1, X, X^2, . . .\}\). Que s’attend-t-on à trouver pour la première colonne ? Quelle matrice obtient-on pour le polynôme \(P = X^4 + X^3 + X^2 + X + 1\) de \( \mathbb{Z}/19\mathbb{Z}[X]\) ?

  2. Comprendre comment obtenir une base du noyau de cette matrice avec sage.

  3. On suppose \(P = P_1\cdots P_r\) est sans carré. Soit \(Q\) tel que \(\Phi(\overline{Q})=0\). Expliquer pourquoi \(Q [P_i]\) est une constante. Expliquer comment utiliser cette propriété pour trouver un facteur non trivial de \(P\). Écrire une fonction qui prend en argument deux polynômes \(P\) et \(Q\), et qui recherche un \(s \in k\) tel que le PGCD de \(P\) et de \(Q - s\) soit non trivial, en renvoyant le diviseur de \(P\) ainsi trouvé, et en renvoyant None s’il n’y en a pas.

  4. Programmer une fonction qui prend un polynôme sans facteur carré à coefficients dans un corps fini et qui donne un diviseur non trivial de ce polynôme (éventuellement le polynôme lui-même, ou plutôt None (c’est a dire rien du tout), s’il est irréductible).

  5. Tester avec \(X^4 + 1\) puis avec \(X^{12} + X^2 + 1 \in \mathbb{F}_p[X]\) pour les nombres premiers \(2 \leq p \leq 19\). On pourra vérifier les résultats avec la méthode .is_ irreducible() ou .factor(). Que se passe-t-il pour \(X^4 + 1\) et \(p = 2\) ?

  6. Programmer la fonction Berlekamp qui prend un polynôme sans facteur carré à coefficients dans un corps fini, et qui renvoie sa décomposition en produit d’irréductibles. Tester avec \(X^{12} + X^2 + 1\) sur \(\mathbb{F}_{19}\).

Exercice 6 (Bonus). Factorisation par degré.#

Soit \(p\) un nombre premier et \(n\) un entier positif.

  1. 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é).

  2. 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é.

Exerccice 7 (Bonus). 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

  1. Choisir un polynôme unitaire \(P\) de degré \(n\) sur \(\mathbb F_p\) aléatoirement

  2. 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.

  3. 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\).

Crypto.#

Exercice 8. Crible.#

Déterminer tous les nombres premiers inférieurs à 10 000 en utilisant un crible.

Exerice 9. 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.

Exercice 10 . Test de primalité de Rabin–Miller#

  1. Écrire une procédure implémentant le test de primalité de Miller–Rabin pour un entier impair.

  2. Tester cette procédure pour \(n=561\) et \(n=9\,746\,347\,772\,161\). Comparer avec la réponse du test de Fermat.

  3. É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}\).

  4. Comparer les vitesses d’exécution de votre procédure et is_prime pour de grands entiers impairs.

  5. Écrire un nouveau raffinement du test de primalité de Miller-Rabin qui renvoie également un facteur non trivial de \(n\) lorsque c’est possible.

Exercice 11. RSA#

  1. É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)\).

  2. Écrire des procédures chiffre et dechiffre illustrant le fonctionnement du cryptosystème RSA.

Exercice 12 (Super Bonus). 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

Exercice 13 (Super Bonus). 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

Contenu