مسابقة دكتوراه 2014 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — الموضوع 03

مسابقة تخصص · Algèbre · المدة: 2سا

Concours Cycle D Maths Fondamentales et Cryptographie 2014-15, Épreuve de Codage, Faculté de Mathématiques, USTHB, 13 octobre 2014, durée 2h.

التمرين 1

Exercice 1 — Vrai ou faux (codes et anneaux)

#coding-theory#galois-rings#linear-codes

Les affirmations suivantes sont-elles vraies ? Justifiez.

Tout code linéaire est cyclique. 2. Un anneau à chaîne est un anneau de Galois. 3. Tout anneau principal est à chaîne. 4. La caractéristique d'un anneau de Galois est toujours première. 5. Un anneau de Galois n'a pas d'éléments nilpotents. 6. Tout code libre est auto-dual.

◀الحل

Faux. 2. Faux ( $\mathbb{F}_p[x]/(x^2)$ ). 3. Faux. 4. Faux ( $GR(p^r,m)$ a caractéristique $p^r$ ). 5. Faux ( $p$ nilpotent si $r\ge2$ ). 6. Faux.

التمرين 2

Exercice 2 — Cryptosystème RSA

#rsa#number-theory#modular-arithmetic

$(n,e)$ clé publique RSA.

$p,q$ premiers distincts $\equiv2\ (\mathrm{mod}\ 3)$ , $n=pq$ , $e=\dfrac{2(p-1)(q-1)+1}{3}$ . Montrer que $e$ est premier avec $\varphi(n)$ et calculer son inverse modulo $\varphi(n)$ .
$(n,e)=(187,107)$ ; cryptogramme reçu $9$ . Quel est le message ?

◀الحل

$3e-2\varphi(n)=1\Rightarrow\gcd(e,\varphi(n))=1$ et $\boxed{e^{-1}\equiv3}$ . 2. $187=11\cdot17,\ \varphi=160,\ d=3$ : message $=9^3\bmod187=\boxed{168}$ .

التمرين 3

Exercice 3 — Matrices génératrices de codes sur Z4

#codes-over-rings#z4-codes#dual-codes

Les matrices suivantes peuvent-elles être génératrices de codes sur $\mathbb{Z}_4$ ?

$G_1=\begin{pmatrix} 1&1&1&0\\ 0&0&2&2\\ 0&2&0&2\end{pmatrix},\qquad G_2=\begin{pmatrix} 1&0&0&0&5&1&2&1\\ 0&1&0&0&1&2&7&1\\ 0&0&1&0&3&6&3&2\\ 0&0&0&1&2&3&1&1\end{pmatrix}$

Si oui : 1. type et longueur ; 2. auto-dual ? matrice de contrôle ; 3. code libre ?

◀الحل

$G_1$ : longueur $4$ , type $4^1 2^2$ , non libre. $G_2$ : longueur $8$ , forme $[I_4\,|\,A]$ , type $4^4$ libre ; auto-dual ssi $AA^t\equiv-I$ , contrôle $H=[-A^t\,|\,I_4]$ .

التمرين 4

Exercice 4 — Anneaux de Galois d'ordre 64

#galois-rings#finite-rings#multiplicative-group

Déterminer tous les anneaux de Galois d'ordre 64, avec leurs caractéristiques, corps résiduels et groupes multiplicatifs.

◀الحل

$p^{rm}=2^6$ donc $p=2,\ rm=6$ : $\boxed{\mathbb{F}_{64};\ GR(4,3);\ GR(8,2);\ \mathbb{Z}_{64}}$ de corps résiduels $\mathbb{F}_{64},\mathbb{F}_8,\mathbb{F}_4,\mathbb{F}_2$ . Pour $r\ge2$ , $GR(2^r,m)^*\cong\mathbb{Z}_{2^m-1}\times(1+2R)$ .

→←

→السابقConcours Doctorat 2014 — Université Mohamed Khider - Biskra — Épreuve N°03 التاليمسابقة الدكتوراه 2014 — Université Badji Mokhtar - Annaba←