Introduction a la Cryptologie Chapitre Anneaux de polynomes

Michael Eisermann

Description

Niveau: Supérieur, Master
Introduction a la Cryptologie Chapitre 9 : Anneaux de polynomes Michael Eisermann (Institut Fourier, UJF Grenoble) Annee 2008-2009 IF / IMAG, Master 1, S1-S2 document mis a jour le 7 juillet 2009FOURIERINSTITUTfi www-fourier.ujf-grenoble.fr/~eiserm/cours _ crypto

• construction de l'anneau des polynomes algorithmes pour l'addition


• fourierinstitutfi www-fourier


• multiplication propriete universelle


• anneaux de polynomes

Informations

• Publié par: profil-infoe-2012
• Nombre de lectures: 16
• Langue: Français

Extrait

Introduction a` la Cryptologie
Chapitre 9 : Anneaux de polynomesˆ
Michael Eisermann (Institut Fourier, UJF Grenoble)
Annee´ 2008-2009
IF / IMAG, Master 1, S1-S2
document mis a` jour le 7 juillet 2009
INSTITUTi f FOURIER
www-fourier.ujf-grenoble.fr/~eiserm/cours#cryptoSommaire
1 L’anneau des polynomesˆ
2 La division euclidienne
3 RacinesSommaire
1 L’anneau des polynomesˆ
Definition´ et construction de l’anneau des polynomesˆ
Algorithmes pour l’addition et la multiplication
Propriet´ e´ universelle et fonctions polynomiales
2 La division euclidienne
3 RacinesL’anneauK[X] contientK comme sous-anneau etX comme el´ ement.´
´ ´ ´ `Tout elementP2K[X] s’ecrit de maniere unique comme
1 n
P =a +a X + +a X ou` n2N; a ;a ;:::;a 2K; a = 0:0 1 n 0 1 n n
Definition´
Dans ce cas on dit queK[X] est l’anneau des polynomesˆ sur l’anneau des
coefficientsK en la variableX. On appelleP un polynomeˆ surK enX.
On definit´ le degre´ degP :=n et le coefficient dominant domP :=a .n
Le polynomeˆ nul est particulier : on pose deg 0 := 1 et dom 0 := 0.
Tout polynomeˆ P2K[X] peut etreˆ ecr´ it de maniere` unique comme
1X
kP = a Xk
k=0
sous-entendant que seul un nombre fini de coefficientsa sont non nuls.k
Ainsi degP = supfk2Nja = 0g avec la convention sup; = 1 .k
L’anneau des polynomesˆ
Theor´ eme`
Pour tout anneau commutatifK il existe un anneau commutatifK[X] tel que :
66´ ´ ´ `Tout elementP2K[X] s’ecrit de maniere unique comme
1 n
P =a +a X + +a X ou` n2N; a ;a ;:::;a 2K; a = 0:0 1 n 0 1 n n
Definition´
Dans ce cas on dit queK[X] est l’anneau des polynomesˆ sur l’anneau des
coefficientsK en la variableX. On appelleP un polynomeˆ surK enX.
On definit´ le degre´ degP :=n et le coefficient dominant domP :=a .n
Le polynomeˆ nul est particulier : on pose deg 0 := 1 et dom 0 := 0.
Tout polynomeˆ P2K[X] peut etreˆ ecr´ it de maniere` unique comme
1X
kP = a Xk
k=0
sous-entendant que seul un nombre fini de coefficientsa sont non nuls.k
Ainsi degP = supfk2Nja = 0g avec la convention sup; = 1 .k
L’anneau des polynomesˆ
Theor´ eme`
Pour tout anneau commutatifK il existe un anneau commutatifK[X] tel que :
L’anneauK[X] contientK comme sous-anneau etX comme el´ ement.´
66Definition´
Dans ce cas on dit queK[X] est l’anneau des polynomesˆ sur l’anneau des
coefficientsK en la variableX. On appelleP un polynomeˆ surK enX.
On definit´ le degre´ degP :=n et le coefficient dominant domP :=a .n
Le polynomeˆ nul est particulier : on pose deg 0 := 1 et dom 0 := 0.
Tout polynomeˆ P2K[X] peut etreˆ ecr´ it de maniere` unique comme
1X
kP = a Xk
k=0
sous-entendant que seul un nombre fini de coefficientsa sont non nuls.k
Ainsi degP = supfk2Nja = 0g avec la convention sup; = 1 .k
L’anneau des polynomesˆ
Theor´ eme`
Pour tout anneau commutatifK il existe un anneau commutatifK[X] tel que :
L’anneauK[X] contientK comme sous-anneau etX comme el´ ement.´
´ ´ ´ `Tout elementP2K[X] s’ecrit de maniere unique comme
1 n
P =a +a X + +a X ou` n2N; a ;a ;:::;a 2K; a = 0:0 1 n 0 1 n n
66On appelleP un polynomeˆ surK enX.
On definit´ le degre´ degP :=n et le coefficient dominant domP :=a .n
Le polynomeˆ nul est particulier : on pose deg 0 := 1 et dom 0 := 0.
Tout polynomeˆ P2K[X] peut etreˆ ecr´ it de maniere` unique comme
1X
kP = a Xk
k=0
sous-entendant que seul un nombre fini de coefficientsa sont non nuls.k
Ainsi degP = supfk2Nja = 0g avec la convention sup; = 1 .k
L’anneau des polynomesˆ
Theor´ eme`
Pour tout anneau commutatifK il existe un anneau commutatifK[X] tel que :
L’anneauK[X] contientK comme sous-anneau etX comme el´ ement.´
´ ´ ´ `Tout elementP2K[X] s’ecrit de maniere unique comme
1 n
P =a +a X + +a X ou` n2N; a ;a ;:::;a 2K; a = 0:0 1 n 0 1 n n
Definition´
Dans ce cas on dit queK[X] est l’anneau des polynomesˆ sur l’anneau des
coefficientsK en la variableX.
66On definit´ le degre´ degP :=n et le coefficient dominant domP :=a .n
Le polynomeˆ nul est particulier : on pose deg 0 := 1 et dom 0 := 0.
Tout polynomeˆ P2K[X] peut etreˆ ecr´ it de maniere` unique comme
1X
kP = a Xk
k=0
sous-entendant que seul un nombre fini de coefficientsa sont non nuls.k
Ainsi degP = supfk2Nja = 0g avec la convention sup; = 1 .k
L’anneau des polynomesˆ
Theor´ eme`
Pour tout anneau commutatifK il existe un anneau commutatifK[X] tel que :
L’anneauK[X] contientK comme sous-anneau etX comme el´ ement.´
´ ´ ´ `Tout elementP2K[X] s’ecrit de maniere unique comme
1 n
P =a +a X + +a X ou` n2N; a ;a ;:::;a 2K; a = 0:0 1 n 0 1 n n
Definition´
Dans ce cas on dit queK[X] est l’anneau des polynomesˆ sur l’anneau des
coefficientsK en la variableX. On appelleP un polynomeˆ surK enX.
66Le polynomeˆ nul est particulier : on pose deg 0 := 1 et dom 0 := 0.
Tout polynomeˆ P2K[X] peut etreˆ ecr´ it de maniere` unique comme
1X
kP = a Xk
k=0
sous-entendant que seul un nombre fini de coefficientsa sont non nuls.k
Ainsi degP = supfk2Nja = 0g avec la convention sup; = 1 .k
L’anneau des polynomesˆ
Theor´ eme`
Pour tout anneau commutatifK il existe un anneau commutatifK[X] tel que :
L’anneauK[X] contientK comme sous-anneau etX comme el´ ement.´
´ ´ ´ `Tout elementP2K[X] s’ecrit de maniere unique comme
1 n
P =a +a X + +a X ou` n2N; a ;a ;:::;a 2K; a = 0:0 1 n 0 1 n n
Definition´
Dans ce cas on dit queK[X] est l’anneau des polynomesˆ sur l’anneau des
coefficientsK en la variableX. On appelleP un polynomeˆ surK enX.
On definit´ le degre´ degP :=n et le coefficient dominant domP :=a .n
66Tout polynomeˆ P2K[X] peut etreˆ ecr´ it de maniere` unique comme
1X
kP = a Xk
k=0
sous-entendant que seul un nombre fini de coefficientsa sont non nuls.k
Ainsi degP = supfk2Nja = 0g avec la convention sup; = 1 .k
L’anneau des polynomesˆ
Theor´ eme`
Pour tout anneau commutatifK il existe un anneau commutatifK[X] tel que :
L’anneauK[X] contientK comme sous-anneau etX comme el´ ement.´
´ ´ ´ `Tout elementP2K[X] s’ecrit de maniere unique comme
1 n
P =a +a X + +a X ou` n2N; a ;a ;:::;a 2K; a = 0:0 1 n 0 1 n n
Definition´
Dans ce cas on dit queK[X] est l’anneau des polynomesˆ sur l’anneau des
coefficientsK en la variableX. On appelleP un polynomeˆ surK enX.
On definit´ le degre´ degP :=n et le coefficient dominant domP :=a .n
Le polynomeˆ nul est particulier : on pose deg 0 := 1 et dom 0 := 0.
66