Les principaux théorèmes

Nombres premiers

Petit théorème de Fermat

Indicatrice d'Euler "Ø"

Déterminez le nombre d'entier k_i/k_i<P et PGCD (k_i, P)=1

Exemple:

Ø(17)=16 ; Ø(12)=4

Théorème de Gauss

Si a>0 et p est premier (avec PGCD(a,b)=1) alors a^c(p)=1[p]

Identité de Bézout

Si PGCD(a,b)=1 alors il existe M, M appartenant à Z* tel que Ma+Nb=1 ; (Ma=1[b] ou Nb=1[a])

Corps Z/PZ

Si p est premier alors (Z/PZ,+,x) est un corps commutatif.. En particulier tout élément admet un inverse.

Résidus quadratiques

a est un "résidus quadratique modulo p" si:

Exemple:

Montrez que X²=2[3] n'a pas de solution ("2" est-il résidu quadratique de Z/3Z)
Z/3Z = {0, 1, 2} = {0, 1, -1}
0² = 0[3]
1² = 1[3]
2² = 1[3]
X² = 2[3] n'a pas de solution.

Théorème des restes Chinois

Grand théorème de Fermat

Si N est supérieur ou égal à 3, il b'existe pas (x, y, z) appartenant à Z/ x^N+y^N=z^N

Nombre de diviseur d'un entier N

Si N=P₁^k₁.P₂^k₂....P₅^k₅ où les Pi sont premier, alors le nombre de division de N et D(N)=(1+k₁)(1+k₂)...(1+k₅)

Exemple:

Déterminez le nombre de diviseur de (391), (72), (101)
-394 = 17¹x23¹ ↔ D(391)=(1+(1))(1+(1))=4
Liste {1, 17, 23, 391}

 

---

Nombres premiers

On montre qu'il existe une infinité de nombre premier, l'ordre de succession des nombres premiers n'obéit à aucun reste commun, cependant on peut "cibler" des familles infinies de nombres premier à partir de certaines équations. C'est le cas par exemple des nombres de Mersenne et des nombres de Fermat.

Nombres premiers de Mersenne et de Fermat

Nombre de Mersenne

Ce sont les nombres de la forme N_Me(P)=2^P-1 avec P premier.

Exemple:

P=2 ; N_Me(2)=3
P=3 ; N_Me(3)=7
P=5 ; N_Me(5)=31
P=7 ; N_Me(7)=127
P=17 ; N_Me(17)=131071

Nombres de Fermat

Ce sont des nombres de la forme N_Fe(N)=(2^2N+1-1)/(2^2N-1) avec n appartenant à N.

Recherche de nombres premiers

L'identification de Bézout nous rappelle que si deux nombres a et b sont premier entre eux,n il existe deux entiers relatifs M et N tels que aM+bM=1 (E)
L'algorithme d'Euclide nous permet de calculer M et N en faisant des divisions successives.

Exemple:

Supposons a<b, effectuons la division de b par a b=aq+r=aq₁+r₁, effectuons la division de a par ₁ (car a>r₁)

Exercice:

2632 et 29 sont premier entre eux, trouvons M et N tel que 2632(M)+29(N)=1
2632 = 90.29+22
29 = 1.22+7
22 = 3.7+1
1 = (2632-90.29) - [29-22]
1 = (2632-90.29) - 3[29-(2632-90.29)]
1 = 2632(1+3)+29(-90-30-270)
1 = 2632(4) + 29(-363)

Même question pour:
a = 1631 et b = 64
a = 3250 et b = 103

 

---

Application

"Codage par exponentiation par bloc". On donne le tableau suivant.

Mot clair	un	deux	trois	quatre	cinq	six	sept	huit	neuf
Code (bloc/2)	03	04	05	06	7	08	09	01	02

Soit C_r le cryptage de M, posons C_r(M)=M^e[P], où (e) est la clé de cryptage et (P) est impair.
Alors on veut que (e) et (P-1) soit premier entre eux PGCD(e,P-1)=1

Condition de cryptage

Il faut que (P-1) soit assez grand (pour décourager les pirates).

P-1 = 10
P = 11
(e, P-1) = 1 par exemple e=3
(.,10)=1

Codage
C_r(M) = M³[11]

Condition de décryptage

Decry(C_r(M))=Decry(M³)[10]=M[10]
Le décryptage étant aussi une exponentiation
C_r(M)^d = (M³) = M[10]
M^3d = M¹[10]

3d = 1[10]
d est l'inverse de 3[10]
3d+10k=1
d est la clé de décodage

Relation entre clé de décodage et clé de décodage

Soit nb variables a₁, a₂, a₃, ..., a_n de bloc de codes respectifs [M₁], [M₂], [M₃], ..., [M_N]
Choisissons P impair avec [M_N]<P<[M_N]_sup[M_N]_sup.
La clé de codage est (e) avec e et (P-1) premier entre eux (E)

Clé de décodage:

Si (E) est vrai, d'après l'identité de Bézout, il existe A et B appartenant à Ae+B(P-1)=1
Ae=1-B(P-1)
Ae=1[P-1]
A est l'inverse de e modulo (P-1)
Soit à coder a_i→M_i
Le codage C_i de M_i s'obtient par C_i=M_i^e[P].
Soit A l'inverse de e modulo P-1
C_i^A = (M_i^e)^A[P] = M_i^eA[P] = M_i^[1-B(P-1)][P] = M_i¹M_i^-B(P-1)
Or d'après Fermat
M_i^-B(B(P-1) = M_i^B'(P-1)[P] = [M_i^B']^(P-1)[P] = 1[P]
donc C_i^A = M_i¹[P] Nous avons ainsi décodé.

Exercice 1

ai	un	deux	trois	quatre	cinq	six	sept	huit	neuf
Mi	03	04	05	06	07	08	09	00	01

Choissions p et e

09 < 11 < 09 09
p=11 connu
e est tel que (e, p-1) premier entre eux.
(17, 10) trouvons d A17+B10=1

Algorithme de clé:

17 = 10(1)+7 ↔ 7=17-10
10=7(1)+3 ↔ 3=10-7
7=3(2)+1 ↔ 1=7-3(2)
1=7-3.2
1=(17-10)-[10-(17-10)]-2=17(1+2)+10(-5)
A17+B10=1
17(3)+10(-5)=1 ; d=3

Codons: "quatre sept deux"

codage de "quatre" 06¹⁷=08[11]
codage de "sept" 09¹⁷=04[11]
codage de "deux" 04¹⁷=05[11]

Décodage:

04³=09[11]
05³=04[11]

 

---

Exercice

ai	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Mi	12	13	14	15	16	17	18	19	20	21	22	23	24	25	00	01	02	03	04	05	06	07	08	09	10	11