Table des matières :
1- Tout corps fini est commutatif.
2- Tout corps fini possède p^n éléments avec p premier. On dit que le corps est de caractéristique p et de dimension n.
3- Deux corps finis de même cardinalité sont isomorphes. On note Fq un corps de q éléments.
4- Tout corps Fq possède un groupe multplicatif cylcique de q-1 éléments. Quelque soit x élément de Fq nous avons x^q = x.
5- Quelque soit p premier, il existe un corps à p éléments, dit corps premier, qui est l'ensemble des entiers modulo p.
Fp = Z/pZ
Fp = {0,1,2,3...,p-1}
Fp est l'ensemble des entiers modulo p.
6- Le corps Fq de caractéristique p et de dimension n, c'est à dire où q = p^n avec p premier, comprend un unique sous-corps de cardinalité p, appelé sous-corps premier, qui est le corps engendré par son seul élément neutre <1Fq,+,*>.
Les p éléments du sous-corps premier sont alors numérotés de façon canonique, et finalement notés comme suit :
<1Fq,+,*> = {0,1,2,3...,p-1}
7- Le corps Fq possède un groupe multiplicatif noté Fq* qui est cyclique et qui contient exactement q-1 éléments. Il est obtenu à partir de Fq simplement en enlevant l'élément absorbant : Fq* = Fq - {0Fq}.
8- Fq constitue un espace vectoriel de dimension n sur son sous-corps premier Fp. C'est à dire qu'il existe une base (v1,v2,v3...,vn) constituée d'éléments de Fq* tel que quelque soit x, un élément de Fq, il existe une représentation unique, c'est à dire des coordonnées uniques (a1,a2,a3...,an) composées d'éléments du sous corps premier Fp identifiés aux entiers modulo p, tel que x = a1*v1 + a2*v2 + a3*v3... + an*vn.
9- L'espace vectoriel engendré par des éléments a,b,c appartenants au corps Fq est définie par l'ensemble des combinaisons linéaires de ces éléments avec les entiers modulo p, et correspond exactement à la cloture de l'ensemble {a,b,c} par l'opération + que l'on note <a,b,c,+>.
10- Les éléments v qui individuellement engendrent le corps c'est à dire tel que <v,*,+> = Fq, sont dit générateurs. Et ils ne sont pas forcément primitifs, on peut en effet avoir en même temps <v,*> ≠ Fq*.
11- Les n premières puissances d'un générateur forment une base vectorielle. Si v est générateur alors les éléments suivants sont linéairement indépendants et forment donc une base : (1, v, v^2, v^3..., v^(n-1)). Quelque soit n coordonnées (a1,a2,a3...,an) composées d'entiers modulo p, nous avons :
a1*v1 + a2*v2 + a3*v3... + an*vn = 0 => (a1,a2,a3...,an) = (0,0,0...,0)
Le corps Fq possède un groupe multiplicatif noté Fq* qui est cyclique et qui contient exactement q-1 éléments. Fq* = Fq - {0Fq}.
12- On appelle éléments primitifs de Fq*, les éléments u qui sont générateurs du groupe cyclique, c'est à dire tel que {1, u, u^2, u^3..., u^(q-2)} = Fq* où d'une manière plus concise tel que <u,*> = Fq*. Dans cette formule, <u,*> désigne la cloture du singleton {u} par l'opération *, c'est à dire l'ensemble de tous les éléments que l'on peut calculer en combinant l'élément u à l'aide de l'opérateur binaires * en des expressions de taille finie, * désignant la multiplication telle qu'elle est définie dans le corps Fq.
13- Etant donné un élément primitif u0, les autres éléments primitifs sont obtenus par les puissances entières de u tel que l'entier servant à l'élévation à la puissance de u soit compris entre 1 et q-1 et soit premiers avec q-1. Nous avons :
(Fq*)@ = {u0^k / k∈{1,2...,q-1} et k∧(q-1) = 1}
|(Fq*)@| = φ(q-1)
G@ désigne l'ensemble des éléments primitifs du groupe cyclique G.
|G| désigne le cardinal de l'ensemble G.
n1∧n2 désigne le pgcd de deux entiers n1 et n2
φ(n) désigne le nombre d'entiers compris entre 1 et n et qui sont premiers avec n. C'est la fonction φ d'Euler.
14- Chaque élément primitif u définie une base exponentielle pour les entiers {0,1,2...,q-2} modulo q-1 : l'application expu associe à chaque entier k appartenant à Z/(q-1)Z = {0,1,2...,q-2}, l'élément u^k appartenant à Fq. C'est un isomorphisme partant du groupe additif {0,1,2...,q-2} modulo q-1 et arrivant dans le groupe multiplicatif Fq*. L'application réciproque est notée logu :
expu : {0,1,2...,q-2} ------> Fq*
k ------> u^klogu : Fq* ------> {0,1,2...,q-2}
x ------> k tel que u^k = xexpu(x + y) = expu(x) * expu(y)
logu(a*b) = logu(a) + logu(b)
15- La représentation du groupe cyclique Fq* en un groupe cyclique Z/(q-1)Z se fait par l'intermédiaire d'un isomorphisme logu où u doit être un élément primitif. Et le choix de u détermine le choix de la représentation du groupe cyclique Fq*.
16- Dans le groupe cyclique Fq*, nous pouvons définir une bijection interne rotu,v appellée changement de base exponentielle ou rotation exponentielle, passant de la base u à la base v où u et v doivent être des éléments primitifs. L'application inverse est noté rotv,u. Ces applications (qui sont indépendantes du choix de la représentation du groupe cyclique Fq*) sont les autmorpismes du groupe multiplicatif cyclique Fq*. Nous avons :
rotu,v : Fq* -------logv--------> {0,1,2...,q-2} -------expu-------> Fq*
x ------------------> k (tel que v^k = x) ----------------> u^krotv,u : Fq* --------logu---------> {0,1,2...,q-2} -------expv------> Fq*
x ------------------> k (tel que u^k = x) -----------------> v^krotu,v = expu ° logv
rotv,u = expv ° logu
rotu,v(x * y) = rotu,v(x) * rotu,v(y)
rotu,v ° rotv,w = rotu,w
rotu,u = id
Quelque soit k∈{1,2...,q-1} tel que k∧(q-1) = 1, nous avons : rotu,v = rotu^k,w^k
17- Dans un corps Fq de caractéristique p et de dimension n, c'est à dire telque q = p^n avec p premier, l'application x-->x^p est un automorphisme appelé automorphisme de Frobenius. Comme la caractéristique du corps est p, nous en déduisons que quelque soit a et b :
(a + b)^p = a^p + b^p
18- Dans un corps Fq de caractéristique p et de dimension n, c'est à dire telque q = p^n avec p premier, Le groupe des automorphismes noté Aut(Fq) est engendré par l'automorphisme de Frobenius x-->x^p. Et il contient exactement n automorphismes :
Aut(Fp^n) = { x-->x^(p^k) / k∈{0..n-1}}
Les intuitionistes mettent toujours en avant les processus constructifs. Etudier les corps finis consiste alors à les construire. Et cette construction se fait à l'aide d'un langage d'opérateurs qui s'enrichi progressivement. Chaque action est explicitée, et les actions de construction même sont explicitées en des opérateurs que l'on qualifie de constructeurs.
Les constructeurs, se définissent relativement à un langage d'opérateurs qui peut par la suite s'étendre. Les constructeurs possèdent des ensembles de départ et d'arrivé qui ne sont pas vraiment fixé et qui correspondent à tous les éléments exprimables par le langage à un instant donné, et qui peut s'étendre par la suite. Seul le procéder de calcul du constructeur est fixé à l'aide d'un langage un peu plus grand appelé méta-langage. Par exemple :
Considérons le langage d'opérateurs L = {a,b,*(.,.) } L'ensemble des éléments désignables par ce langage est :
< a,b,*(.,.)> = {a, b, a*a, a*b, b*a, b*b, (a*a)*a, a*(a*a), (a*a)*b...}
Nous définisons la fonction f : x-->x*x. Délors nous pouvons calculer f(a), f(b*b), qui sont respectivement égale à a*a, (b*b)*(b*b), et qui sont des expressions de langage L. Puis nous étendons le langage L à l'aide d'un nouvel opérateur c en un nouveau langage noté L[c]. C'est ce que l'on appel une extension élémentaire. Nous voyons alors que f(c) peut être calculé sans avoir à modifier la définition constructive de f. Le domaine de définition de f s'est agrandi en même temps que le langage, et il n'est pas nécessaire de reprogrammer f, le même programme de construction s'applique.
Si un opérateur ne possède aucune définition, celui-ci est définie par défaut sous sa forme récurcive triviale. Par exemples les opérateurs e, f(.), *(.,.) d'arité respective 0, 1, 2 n'ayant pas de définition, sont définis par défaut comme suit :
e : e
f : x-->f(x)
* : (x,y)-->x*y
Les variables muettes x, y, n'ont de portés que dans le corps de leur fonction. Leur noms importent peu et elles doivent simplement être différentes. C'est comme une extension élémentaire du langage dont les effets seraient limités uniquement pour le calcul de la fonction.
Le calcul d'un opérateur sans définition génère du code libre, de la structure libre. Par exemple si *(.,.) et f(.) n'ont pas de définition alors la structure <a,b,*(.,.), f(.)> est libre. Chaque expression distincte de langage {a,b,*(.,.), f(.)}° désigne un élément distinct de la structure. La structure libre coïncide avec le langage.
La fonction peut contenir des opérateurs qui ne figurent pas dans le langage initial. Par exemple, la fonction h : x --> s(x*e), induit 2 nouveaux opérateurs que sont l'opérateur s(.) d'arité 1 et l'opérateur e d'arité 0. Le passage par cette fonction produira des éléments dans le langage étendu L ∪ {e, s(.)}.
Mais si s s'avère défini à son tours, alors il peut disparaitre des expressions puisqu'il peut être évalué. Il en est de même pour l'opérateur e d'arité 0, si celui-ci est définit égale à une autre expression que lui-même.
La définition d'un opérateur est en faite une affectation. Ainsi on écrira : h = (x --> s(x*e)) et e peut être également affecté comme par exemple e = a*b*f(c). Néanmoins une différence de type existe entre ces deux variables l'une est élémentaire (d'arité nulle) l'autre non.
Ces affectations constituent un début de programmation. Ce pose la question de la récurcivité. Quid d'un opérateur qui s'appel lui-même ? Si la récurcion ne s'arrète pas, elle se propage selon un schéma constant, et ce schéma n'est pas forcement trivial, on est alors en présence d'éléments récurcifs qui peuvent s'écrire dans un langage augmenté de symboles de récurrences. Mais nous n'allons pas ouvrir cette problèmatique maintenant. Nous considérerons des constructeurs de base toujours de récursivité trivial, c'est à dire concrètement non récurcif.
Le méta-langage des constructeurs peut être augmenté afin de contenir l'arithmétique. La définition de la fonction devient un algorithme à part entière. Il porte alors en lui l'implémentation de l'algorithme sur la structure. Délors un autre cas de figure peut se produire. La fonction appliqué à un élément particulier, se lance dans une exécution sans fin et ne donne pas de résultat. C'est l'infini de Turing. Mais dans les cas non triviaux, on est jamais sûre de cette infini de Turing. Il faudrait attendre un temps infini pour être sûre que le constructeur ne donne pas de réponse. C'est pourquoi on qualifie souvent cet infini de Turing, d'oracle, car il n'est basé que sur la prémonition de celui qui l'affirme, une hypothèse indémontrable sur l'avenir. Mais nous n'allons pas ouvrir cette problèmatique maintenant. Nous considérerons des constructeurs toujours totalement calculables, et nous calculerons leur complexités.
Les constructeurs sont les mains qui pétrissent la pâte, le savoir-fair, et en ce sens, ils constituent un savoir qui peut être accumulé. La structure est passsive, le constructeur est dynamique. Le constructeur permet d'étendre les structures, et il peut les étendres sans imposer la moindre contrainte, de manière libre en quelque sorte. Il peut les traduire, les transformer....
Habituellement pour étendre les corps on procédera d'abord par l' extension d'anneaux en anneaux des polynômes. Mais on peut directement étudier l' extension d'un corps par un élément i, dont on ne suppose aucune règles restrictive. C'est dire que i est supposé différents de tous les éléments du corps, dans la mesure du possible, et qu'apriori aucune règle de simplification ne sera imposée et ne sera rencontrée, toujours dans la mesure du possible. Cela constitue une extension libre. Mais pour approfondire ce concept et en vérifier sa réalité, il nous faut formaliser ce que l'on entend par règle de simplification, qui sont des propriétées logiques du première ordres, ce qui annonce le troisième volet de la théorie des langages, qui vient après la représentation des données, puis de celle des algorithmes et qui est celle des propriétés.
L'extension libre d'un corps par un élément i, est une structure étonnante, qui contient potentiellement toutes les extensions monogènes possibles d'un corps tel que la mathématique classique le définie, comme si ces extensions étaient superposées, comme des états quantiques distincts peuvent l'être, avant qu'un choix ne soit imposé par la nécessité de la mesure.
---- 5 Janvier 2013 ----
Les corps Fp^n sont de caractéristique p, et sont optenus par extension du corps premier Fp. On commence par étudier l'extension d'un corps premier par un élément e que l'on note Fp[e].
5- Quelque soit p premier et quelque soit n, il existe un corps à p^n éléments, dit corps de référence, que l'on note Fp^n ou simplement Fq avec q = p^n, et qui est l'ensemble des n-uplet d'entiers modulo p avec l'addition vectorielle et une multiplication particulière.
Fp^n = (Z/pZ)^n
Fp^n est l'ensemble des n-uplets d'entiers modulo p.
Noter que les corps premiers Fp possèdent une implémentation canonique, c'est à dire une représentation des données de ses éléments, et une représentation algorithmique de ses opérations + et *.
La représentation est un langage, à la fois de données et de programmation, et constitue le premier point qui devrait être abordé par une théorie constructrive des langages et qui s'intitulerais "Le codage et la programmation".
La programmation peut être vue sous plusieurs modes comme le montre l'exemple des deux façons de résoudre le calcul du plus court chemin entre deux sommets d'un graphe symétrique où chaque arrète possède une distance. On peut soit explorer les différents chemins possibles, ou simplement écarter les deux sommets au maximum des possibilitées. La première méthode applique un algorithme de calcul série qui peut être trés long, alors que la seconde méthode, qui correspond pourtant à un calcul beaucoup plus important qu'est la modélisation d'un graphe se déformant, applique un algorithme de calcul parallèle qui pour cette raison peut être très court.
Il existe donc un premier mode de programmation dite série qui correspond à l'exécution d'un processus par un unique processeur mettant en oeuvre des opérations élémentaires chacune portant sur une petite quantitées de données localisées et se succédant selon une chronologie linéaire. Mais il existe d'autres modes de programmation dites parallèles qui correspondent à l'exécution de plusieurs processus par différents processeurs simultanément selon des logiques sociales.
1- Le corps Fp^n contient φ(n) sous-corps, qui sont exactement isomorphes aux φ(n) corps Fp^f tel que f divise n.
L'indicateur d'Euler φ(x) retourne par définition le nombre d'entiers qui sont compris entre 1 et x et qui sont premiers avec x.
L'unicité du lien entre corps et sous-corps, nous permet de définir un autre moyen de construction des corps de référence, dit construction par le haut. Posons un corps Fp^n dit mère, et considérons la famille des sous-corps de ce corps mère.
grand Fp^n qui représente le sommet de la famille des corps
Noter le lien d'inclusion entre les corps de références tels des poupées russes, qui est une propriété constructive pour les familles de corps finis de référence correspondant aux sous-corps de référence d'un corps de référence. Considérons le corps de référence Fp^n
2- Considérons deux corps Fp^n, Fp^f, de même caractéristique p et de dimensions quelconques n et f. Et considérons la famille des sous-corps de Fp^ppcm(n,f) avec le lien d'inclusion
Un élément x de Fp^n est élément du corps Fp^f si et seulement si x^(p^f) = x. Et réciproquement si f divise n alors x^(p^(n/f)) couvre Fp^f lorsque x couvre Fp^n. Autrement dit :
Fp^f = { x / x∊Fp^n et x^(p^f) = x}
f divise n => Fp^f = {x^(p^(n/f)) / x∊Fp^n}
f divise n <=> Fp^f ⊂ Fp^n
Quelque soit a,b appartenant à Fp^n nous avons :
(a+b)^p = a^p + b^p
Le groupe des automorphismes de corps de Fp^n est cyclique d'ordre n, et est engendré par l'automorphisme de Frobenius : x-->x^p. En posant g = (x-->x^p), l'automorphisme de Frobenius, nous avons :
Aut(Fp^n) = <g,°>
Aut(Fp^n) = {id, g, g^2, g^3..., g^(n-1)}
1- Le corps Fq possède un groupe multiplicatif (Fq*, *) cyclique de q-1 éléments. Fq* = Fq - {0}. On appelle éléments primitifs de Fq, les éléments u qui sont générateurs du groupe multiplicatif, c'est à dire tel que :
{1, u, u^2, u^3..., u^(q-2)} = Fq*
où d'une manière plus concise tel que :
<u,*> = Fq*
dans cette formule <u,*> désigne la cloture du singleton {u} par l'opération *, c'est à dire l'ensemble de tous les éléments que l'on peut calculer en combinant l'élément u à l'aide de l'opérateur binaires * en des expressions de taille finie.
2- Etant donné un élément primitif u, les éléments primitifs sont donnés par les puissances entières de u tel que l'entier servant à l'élévation à la puissance de u soit compris entre 1 et q-1 et soit premiers avec q-1. Il y en a φ(q-1).
---- 16 Novembre 2012 ----
Les sous-corps de K sont tous de même caractéristique et sont caractérisés de façon unique par leur dimension f qui doit être un diviseur de n. Et sa fonction caractéristique en est la suivante : x appartient au sous corps de dimenssion f si et seulement si x^(p^f) = x. Et sa fonction générante en est la suivante : Les éléments générateurs du sous-corps de K de dimenssion f sont les éléments générateurs de K à la puissance n/f.
Noter cette dualité, fonction caractéristique X et fonction générante G, pour définir un sous-ensemble d'une structure K. Le sous-ensemble est égale à {X(x)/ x∈K} et aussi égale à G(K). Pour les corps finies de dimenssion n, ces fonctions sont les suivantes, f divisant n :
La fonction caractéristique du sous-corps de dimension f divisant n est la suivante : Xf(x) = (x^(p^f) = x)
La fonction générative du sous-corps de dimension f divisant n est la suivante : Gf(x) = x^(n/f)
Par exemple regardons le corps de caractéristique 2 à 12 dimensions. Prenons un élément générateur a. Une base est donnée par (1, a, a^2, a^3, a^4...., a^(11)). Les sous-corps sont les sous-espaces vectoriels suivants :
Au vue de cette cartographie, on peut se poser la question de la véracité de l'emboitement des corps Fp^n par inclusion, c'est à dire s'il existe vraiment un mécanisme de construction de corps de référence Fp^n tel que ses sous corps soient égaux aux corps Fp^f avec f divisant n, dénotant ainsi une relation d'inclusion et non seulement d'isomorphisme.
Un premier élément de réponse est donné en se plaçant dans le corps Fp^(n!) où n est arbitrairement grand. Dans ce corps, pour j inferieur à n, il existe un unique sous corps Fp^j. Et ces sous-corps s'emboitent bien comme des poupées russes du fait de l'unicité des sous corps ayant une même dimension. Mais cette réponse n'est pas satisfaisante, car elle ne construit pas la solution petit à petit, elle ne propose qu'une solution relative, approchée en quelque sorte, qu'il faut reconstruire totalement si on dépasse les dimensions maximales autorisées, n en l'occurence. Ce que nous voulons c'est un mécanisme de construction qui permet de construire Fp^(n+1) à partir de Fp^n sans remettre en cause la première construction, une construction pas à pas, et qui doit respecter naturellement les règles d'inclusions des sous-corps tel qu'annoncés, faisant que les corps Fp^n de petites dimension n pour commencer, puisse être construit définitivement, et que nous puissions les poser comme références.
Cardinal |
Caractéristique |
Dimension |
Nombre d'éléments primitifs |
|
q = p^n |
p |
n |
φ(q-1) |
|
2 |
2 |
1 |
1 |
{0,1} / 2=0 |
3 |
3 |
1 |
1 |
{0,1,2} / 3=0 |
4 |
2 |
2 |
2 |
{0,1,i,i+1} / 2=0, i^2+1=0 |
5 |
5 |
1 |
2 |
|
7 |
7 |
1 |
2 |
|
8 |
2 |
3 |
6 |
|
9 |
3 |
2 |
4 |
|
11 |
11 |
1 |
4 |
|
13 |
13 |
1 |
4 |
|
16 |
2 |
4 |
8 |
|
17 |
17 |
1 |
8 |
|
19 |
19 |
1 |
6 |
|
23 |
23 |
1 |
10 |
|
25 |
5 |
2 |
8 |
|
27 |
27 |
3 |
12 |
|
29 |
29 |
1 |
12 |
|
31 |
31 |
1 |
8 |
|
32 |
2 |
5 |
30 |
|
37 |
37 |
1 |
12 |
|
41 |
41 |
1 |
16 |
|
43 |
43 |
1 |
12 |
|
47 |
47 |
1 |
22 |
|
49 |
7 |
7 |
16 |
|
53 |
53 |
1 |
24 |
On note Z/pZ[X] est l'anneau des polynomes à coefficient dans Z/pZ
K est isomorphe au quotient de l'anneau des polynomes à coefficient dans Z/pZ que l'on note Z/pZ[X] par n'importe quel polynôme irréductible de degrés n. Cela permet différentes représentations en mémoire des éléments du corps, et différentes implémentations du calcule de l'adition et de la multiplication dans ce corps :
Cas pour le degré 2 :
(Z/pZ)[X] / (X^2 = A*X + B)
Le polynôme au dénominateur est caractérisé par deux coefficients (A,B) chacun modulo p autrement dit appartenants à Z/pZ. Dans ce corps, les éléments sont des polynômes d'inconnue X, à coefficients modulo p, c'est à dire appartenants à Z/pZ, et modulo la réduction qui transforme X^2 en A*X + B , de tel sorte que ce sont des polynômes de degrés 1 au maximum de la forme a*X + b et donc caractérisés par deux coefficients (a,b) chacun modulo p c'est à dire appartenants à Z/pZ.
L'addition est trivial en sachant que les composantes sont dans Z/pZ. La multiplication est plus complexe (a,b)*(a',b') correspond au coefficients du polynome suivant : (a *X + b)*(a'*X+b') que l'on developpe et dans lequel on remplaçant ensuite X^2 par A*X + B . Le calcul donne les règles d'addition et de multiplication suivantes :
(a,b) + (a',b') = (a+a', b+b')
(a,b) * (a',b') = (a*b'+b*a'+A*a*a', b*b'+B*a*a')
Cas générale de degré n :
Z/pZ[X] / (X^n = P0 + P1*X + P2*X^2 ... Pn-1*X^(n-1))
Le polynôme au dénominateur est caractérisé par n coefficients (P0,P1,P2...,Pn-1) chacun appartenants à Z/pZ. Dans ce corps, les éléments sont des polynômes d'inconnue X, à coefficients appartenants à Z/pZ, et modulo la réduction qui transforme X^n en P0 + P1*X + P2*X^2 ... Pn-1 * X^(n-1), de tel sorte que ce sont des polynômes de degrés n-1 au maximum de la forme a0 + a1*X + a2*X^2 ... an-1* X^(n-1) et donc caractérisés par n coefficients (a0,a1,a2...,an-1) chacun appartenants à Z/pZ.
La règle de simplification se décline en plusieurs règles de simplification: :
X^n = P0 + P1*X + P2*X^2 ...+ Pn-1*X^(n-1)
X^(n+1) = P0*K1 + (P0 + P1*K1)*X + (P1 + P2*K1)*X^2 ...+ (Pn-2 + Pn-1*K1)*X^(n-1) avec K1 = Pn-1
X^(n+2) = P0*K2 + (P0 + P1*K2)*X + (P1 + P2*K2)*X^2 ...+ (Pn-2 + Pn-1*K2)*X^(n-1) avec K2 = (Pn-2 + Pn-1*K1)
X^(n+3) = P0*K3 + (P0 + P1*K3)*X + (P1 + P2*K3)*X^2 ...+ (Pn-2 + Pn-1*K3)*X^(n-1) avec K3 = (Pn-2 + Pn-1*K2)
X^(n+j) = P0*Kj + (P0 + P1*Kj)*X + (P1 + P2*Kj)*X^2 ...+ (Pn-2 + Pn-1*Kj)*X^(n-1) avec Kj = (Pn-2 + Pn-1*Kj-1)
Ainsi un polynôme de dedgré 2*(n-1) est de la forme a0 + a1*X + a2*X^2 ... a2n-2* X^(n-1) et donc caractérisés par 2*n-1 coefficients (a0,a1,a2...,an-1) chacun appartenants à Z/pZ.possède coefficients et se réduit en :
(a0,a1,a2...,a2*(n-1)) = (
On considère d'abord la règle de produit non réduit c'est à dire donnant comme résultat un polynome de degrés 2*(n-1):
(a0,a1,a2...,an-1) *(b0,b1,b2...,bn-1) = ( a0*b0, a0*b1+ a1*b0, a0*b2+ a1*b1 + a2*b0, ...., an-1*bn-1)
qui admet comme terme générique :
( aj / j = 0..n-1) * ( bj / j = 0..n-1) = ( sum(ak*bj-k) / k = min(0, j - (n-1))...max(n-1, j) / j = 0..2*(n-1) )
qui se réduit en :
= ( sum(ak*bj-k) / k = min(0, j - (n-1))...max(n-1, j) +
/ j = 0..2*(n-1) )
10) L'exponentiel dans les corps finis
Les éléments primitifs u définissent les isomorphismes entre le groupe cyclique
: (Z/Z(q-1),+) --> (K*,.), expu(k) = u^k. Et on identifie (Z/Z(q-1),+) à K*
expu qui prennent un entier k dans le groupe Z/Z(q-1) pour retourner un élément u^k de K*.
u^0 = 1
u^1= u
u^(a+b) = u^a * u^b
u^(a*b) = (u^a)^b
u^a * v^a = (u*v)^a
u^(u⌄a) = a
u⌄1 = 0
u⌄u = 1
u⌄(u^a) = a
u⌄(a*b) = u⌄(a) + u⌄(b)
u⌄(a^b) = u⌄(a)*b
u⌄(a) / u⌄(b) = b⌄(a)
9) L'extension complexe des corps finis
L'extension complexe d'un corps K consiste à rajouter un élément i dans le corps, si celui-ci n'existe pas déjà, et qui possède la définition suivante :
i^2 = -1
Dans la stricte orthodoxie, on dirait que l'on a procédé à un quotient de l'anneau des polynomes sur K, par l'idéale engendré par le polynôme X^2+1=0, et que l'on note par K[X]/(X^2+1), mais cela revient au même. Cette extension sera appelé simplement le corps des complexes sur K, ou plus simplement encore, le corps des K-complexes.
On pourrait utiliser la clôture algébrique, mais on va essayer de s'en passer pour ne pas compliquer les calculs et finalement noyer ce qui est fondamental dans des développements long et finalement inexploitable par un algorithme simple.
Les trois méthodes de construction des complexes, vue au chapitre complexe, s'appliquent aussi aux corps finie. i représente l'unité imaginaire dans le corps des K-complexe. On définie alors la forme cartésienne du complexe sur K par un couple d'éléments de K, avec les règles d'addition et de multiplication classique :
x + i*y = (x,y)
(x,y)+(x',y') = (x+x',y+y')
(x,y)*(x',y') = (x*x'-y*y', x*y'+y*x')Le corps des K-complexes peut être vue ainsi comme un espace vectoriel sur K de dimenssion 2.
La forme polaire ne peut pas s'exprimer dans le corps K. Car déjà tous les éléments ne sont pas des carrés. Dans la forme polaire, le carré de la norme joue un rôle trés proche de la norme. En effet le produit de deux complexes sur K aura une norme au carrré égale au produit des deux autres normes au carré, et c'est cette fonctionnalité qui compte. Pour la phase il faut trouver une expression qui lorsque l'on fait le produit des deux complexes sur K correspond à la sommation des phases.
Le problème se ramène à calculer l'extension de corps juste suffisante pour exprimer la norme et la phase des éléments K-complexes.
On définie le conjugué ainsi :
conjugué(x,y) = (x,-y)
(x,y) * conjugué(x,y) = x^2 + y^2On définie la norme comme la racine carré notée sqrt(x^2 + y^2), et si cette racine n'existe pas, on la rajoute. On considère ainsi l'extension par racine carré du corps K.
Pour l'angle, on va s'inspirer de la géométrie pour nous guider. L'angle est caractérisé géométriqement par un couple de vecteurs non nuls. On parlera de l'angle entre le vecteur a et le vecteur b. Les vecteurs sont ensuite normés et le couple de vecteur transformé linéairement afin que le premier vecteur a corresponde exactement au premier vecteur de la base. Après quoi on constate que la représentation de l'angle ainsi définie dans le plan complexe, est unique, et est caractérisé par un simple vecteur normé.
norme(x,y) = sqrt(x^2 + y^2)
argument(x,y) est caractérisé de façon biunivoque par le K-complexe étendu au racine carré : (x, y)/norme(x,y)Hors nous savions déja cela car en ne développant pas ei*φ et en le considérant comme un élément de K, nous avions :
(x,y) = x + i*y = [a,φ] = a * ei*φ
a = norme(x,y)
ei*φ = (x,y)/norme(x,y)