Nombres et données.

Des données représentant une quantité d'information limitée peuvent toujours être rendues "discrètes" ou "numériques".  L'homme n'a pas encore trouvé un moyen de traiter autre chose qu'une quantité limitée de données, ce qui implique que tout morceau d'information que nous pourrons un jour considérer, peut être représenté numériquement.  Ce qui caractérise une représentation discrète ou numérique, est qu'elles peuvent être comptées avec des nombres entiers.  Ainsi, toute donnée correspond à un nombre entier positif.  Ce fait trivial est en même temps d'importance fondamentale: toute donnée numérique peut être représenté par un nombre entier.  Le contenu entier d'un disque dur de 1 Terra-octet est représenté par un nombre qui aura à peu près 3000 chiffres décimaux, mais qui est bien un nombre comme un autre.  Quand vous ré-interprétez ce nombre comme 200 films et 7000 morceaux de musique, ou comme le catalogue des transferts de banque de banque A les 2 dernières années, est une question de codage, c'est à dire, une relation entre les nombres et une ou autre représentation "réaliste" des données.  Mais dans le fond, des données numériques peuvent toujours être considérées comme un nombre naturel.  Ce fait simple mais important rend les mathématiques des nombres entiers, ce qui était pendant des siècles, un domaine de jeux pour les mathématiciens, soudain un discipline importante industrielle d’ingénierie (au grand dam de certains académiciens...). 

Le fait de pouvoir considérer toute forme de donnée comme un nombre est important dans tous les aspects de traitement de données qui sont indépendants du domaine dans lequel les données ont un sens.  Bien sûr ce n'a pas beaucoup de sens de considérer qu'un film est un nombre quand on veut éditer le film: il vaut mieux le considérer comme une succession d'images et de son dans ce cas.  Mais quand on traite des données en général, comme dans la cryptographie et la compression de données, l'idée que des données, c'est un nombre, est extrêmement important.  Si vous connaissez le nombre, vous avez les données.  Si vous n'avez pas le nombre, vous n'avez pas les données.

Certains mathématiciens disent en rigolant que dieu a créé les nombres naturels, et l'homme, tout le reste des mathématiques.  D'autres ne sont pas d'accord: ils maintiennent que c'est le diable qui les a créés.  La théorie des nombres naturels est bien plus remplie de surprises et d'énigmes que toute autre branche des mathématiques.  Beaucoup de cryptographie est basée exactement sur le labyrinthe de la théorie des nombres.

On pourrait être frappé que toute donnée est un nombre.  Mais on pourrait inverser cela: un nombre est ce qui représente quelque chose de fini et discret.  Ce n'est peut-être pas une surprise que les mathématiques des nombres naturels sont pleins de surprises: ce sont les propriétés de toute chose finie, et il y en a beaucoup !

Des nombres et des groupes

L'étude de la théorie des nombres commence en école primaire avec les opérations sur les nombres.  Une opération sur les nombres consiste en la chose suivante: on prend deux nombres, et on en produit un troisième.  L'addition est une opération sur les nombres: 2 + 1 = 3.  Nous prenons deux nombres, ici le nombre 2 et le nombre 1, et nous en produisons un troisième, ici, le nombre 3.  L'addition a quelques propriétés, comme le fait que l'ordre des deux nombres n'a pas d'importance, et que cela s'étend si on a plus que deux nombres au départ: la façon dont on les prend deux par deux et l'ordre ne joue pas: une liste finie de nombres va toujours produire la même somme, indépendamment comment on s'y prend, si chaque nombre dans la liste apparaît exactement une fois.  Une grande invention de l'humanité était le nombre zéro.  Si on prend, dans une addition, un des nombres comme zéro, le résultat sera toujours l'autre nombre.

Zéro a ouvert la Boîte de Pandore.  Zéro avait été inventé pour avoir une réponse à l'énigme suivant: "quel seul nombre spécial peut-on ajouter à n'importe quel nombre naturel, pour que le résultat soit toujours ce deuxième nombre ?".  Dans l'ensemble des nombres naturels, 1,2,3,4,... il n'y a pas un tel nombre.  On l'a donc inventé.  0.  Zéro.

Et maintenant, la difficulté est la suivante.  Une fois qu'on considère des puzzles comme celui-là, qu'est-ce qui nous empêche d'en poser d'autres, comme les instituteurs savent si bien le faire pour leurs élèves: "quel nombre faut-il ajouter à 3 pour obtenir 5 ?".  Celle-là est facile: il faut ajouter 2.  La réponse est: le nombre 2.  Mais si l'énigme était: "Quel nombre faut-il ajouter à 5 pour obtenir 3 ?", soudain, il n'y a pas de réponse.  En classe de CP.

Ce genre de puzzle se généralise tellement facilement qu'elle donne lieu à une nouvelle opération: la soustraction.  Le premier puzzle peut alors être écrit: 5 - 3 = 2.  Pour le deuxième, nous pouvons écrire: 3 - 5, mais nous n'avons pas de réponse en classe de CP.  Il n'y a pas un nombre de pommes que vous pouvez ajouter à un panier qui en contient déjà 5, pour obtenir un panier de 3.  La question ne semble même pas avoir un sens.

Ainsi, autant que l'addition marche toujours, la soustraction ne marche que parfois.  Zéro avait été inventé pour avoir une réponse à: 5 - 5 = 0 ; 3 - 3 = 0, 324 - 324 = 0.  Avec notre panier, cela peut encore avoir un sens: zéro, c'est un panier vide, sans pommes.  "Combien de pommes faut-il ajouter à un panier de 5 pommes, pour obtenir un panier de 5 pommes ?", réponse: "rien du tout".  Zéro.

Et puis il y a le petit malin de la classe qui dit: "mais pour obtenir un panier de 3 pommes si on en a un de 5, rien de plus facile: il faut manger 2 pommes !".  Effectivement.  Le "3" dans 5 + 3 = 8 est interprété: nous ajoutons 3 pommes.  Mais ne pourrions-nous pas inventer un autre "3" qui veut dire "nous mangeons 3 pommes" ?  De la même façon qu'on avait inventé zéro qui voulait dire "rien du tout" ?

Bien sûr.  Nous appelons cette nouvelle version de "3", moins 3.  -3.  Pour chaque nombre naturel, nous inventons un autre, avec "moins".  Nous avons inventé beaucoup de nombres maintenant, qui n'existaient pas avant: l'ensemble des entiers.

Maintenant, nous pouvons dire: 3 - 5 = -2, parce que 5 + (-2) = 3.  Combien de pommes faut-il ajouter à un panier de 5 pommes pour obtenir un panier de 3 pommes ?  Réponse: il faut manger 2 pommes.

Nous pouvons aussi comprendre que 3 - 5 est la même chose que 3 + (-5), bien que la signification soit différente.  Et de cela, nous pouvons déduire: (-2) + (-3) = -5.

Avec notre jeu étendu de nombers, maintenant, la soustraction est toujours possible.  Nous avons inventé suffisamment de nombres pour que nous pouvons prendre deux entiers et appliquer la soustraction, de la même façon que nous pouvions faire déjà avec l'addition sur les nombres naturels et la soustraction est l'opération inverse de l'addition.

Avoir une opération, et son opération inverse, est si important en mathématiques, que les mathématiciens ont donné un nom particulier à cela: un groupe.

Un groupe est essentiellement un ensemble d'objets mathématiques (comme des nombres, mais ce n'est pas nécessaire), et une opération (comme l'addition), tel qu'il y ait un élément neutre (dans notre cas: zéro) et que l'opération inverse soit toujours possible.

Les nombres naturels avec l'opération "addition" n'était pas un groupe.  Mais en inventant zéro, et en inventant les entier négatifs, nous en avons fait un groupe.  L'ensemble des entiers avec l'opération addition est bel et bien un groupe.  Avoir un groupe est important car beaucoup de propriétés de calcul ne dépendent que des lois du groupe.   Si c'est un groupe, ces propriétés sont valides.

Des nombres et les anneaux.

En école primaire, l'addition et la soustraction ne sont pas la seule chose qui est apprise concernant les nombres.  Le cauchemar de beaucoup d'écoliers est d'apprendre leurs tables de multiplication.  La multiplication est une autre opération sur les nombres: si vous prenez deux nombres, disons 3 et 4, alors 3 x 4 = 12.  Etant donné deux nombres, un troisième nombre est toujours le résultat de la multiplication.

De la même façon que nous avions le puzzle "quel nombre, ajouté à un autre, donne ce deuxième toujours comme résultat ?" (et la réponse était zéro, que nous avons dû inventer), nous pouvons considérer le puzzle: "quel nombre, multiplié avec un autre, donne toujours ce deuxième comme résultat ? ".  Mais cette fois, il ne faut rien inventer, nous l'avons déjà: c'est le numéro 1.  Multiplier un nombre avec 1 donne comme résultat: ce nombre.

La même boîte de Pandore s'ouvre, cependant.  Nous pouvons maintenant aussi demander: "Quel nombre faut-il multiplier avec 4 pour obtenir 12 ? " et la réponse est: 3.  En d'autres termes, de la même façon que la soustraction était la généralisation du puzzle pour l'addition, il y a aussi une opération inverse pour la multiplication: la division.  Nous écrivons 12/4 = 3.  3 est le nombre avec lequel il faut multiplier 4, pour obtenir 12.

De la même façon que la soustraction ne marchait pas toujours avec les nombres naturels, la division ne marche pas toujours avec les entiers.  Si nous considérons les entiers, nous avons deux opérations (addition et multiplication), et deux opérations inverses: soustraction et division.  La soustraction est complète (et donc les entiers et l'addition forment un groupe), mais la division ne l'est pas, et donc les entiers et la multiplication ne forme pas un groupe. 

Mais il y a une relation importante entre l'addition et la multiplication, qui s'appelle la "distributivité":

5 x (4 + 2) = 5 x 4 + 5 x 2 = 30

Même si la deuxième opération ne forme pas un groupe avec les entiers, une structure avec deux opérations, dont la première forme un groupe, la deuxième a un élément neutre, et il y a la distributivité, est appelé un anneau.

L'arithmétique des nombres entiers avec addition, soustraction, multiplication, et parfois, division, est un anneau.

Il y a une façon, dans un anneau, de faire presque marcher la division et qu'on apprend aussi en école primaire: "division avec reste".  On l'appelle aussi parfois division Euclidienne.  La conception de division avec reste est importante dans la structure des anneaux.  Beaucoup de la théorie des nombres joue sur cette "division avec reste", même si ce n'est pas la vraie division comme opération inverse de multiplication.  La division avec reste marche toujours.  Même si 11/4 n'a pas de résultat entier (il n'existe pas d'entier tel que multiplié par 4, il fait 11), nous pouvons dire: 11 divisé par 4 est 2, et il reste 3.  Ça veut dire que 4 x 2 + 3 = 11.

Seulement, on voudrait une vraie division qui marche tout le temps.  Pour faire cela, nous allons inventer des nouveaux nombres.  Cette invention est la terreur en école primaire: les fractions !

Les fractions sont les nombres rationnels.  Dans l'ensemble des nombres rationnels (sans zéro), la division marche toujours.  L'ensemble des nombres rationnels sans zéro, et la multiplication, forment un groupe.  L'ensemble des nombres rationnels avec zéro forment toujours un groupe pour l'addition.  La combinaison des deux groupes et la distributivité, forment un champs.   Les nombres rationnels, avec addition et multiplication, sont un champs.  Dans un champs, toute opération peut être inversée (sauf la multiplication par zéro).

Mais nous voulions garder des entiers, car nous nous intéressons aux données discrètes, qui sont toujours représentés par des entiers.  Par des nombres naturels, même.  D'un autre coté, ce serait pratique d'avoir un champs, pour pouvoir faire des opérations et revenir en arrière.  Nous voulons des nombres naturels qui forment un champs.   Avec les entiers classiques, et les opérations classiques, ça ne marche pas, au mieux nous avons un anneau.  Mais il y a bien une solution: on va pouvoir faire un champs avec des nombres naturels !

Les groupes cycliques modulo n.

Quand la soustraction ne marchait pas tout le temps dans les nombres naturels, nous avons inventé des nombres supplémentaires (les nombres négatifs) pour faire marcher la soustraction.  Mais il y a une autre façon de faire cela.  Nous pouvons considérer des nombres sur un cercle au lieu de sur une ligne droite.  Alors, l'addition est "compter dans le sens des aiguilles de la montre", est on peut considérer alors la soustraction comme "compter dans le sens inverse des aiguilles de la montre".  Considérons 6 entiers: 0 - 1 - 2 - 3 - 4 - 5.  Dans ce petit ensemble d'entiers, nous pouvons définir l'addition comme l'addition normale jusqu'à une certaine hauteur: 2 + 1 est toujours 3.  Deux plus deux est toujours 4.  Mais quoi faire de 4 + 3 ?  7 n'est pas dans l'ensemble.  Mais si nous disons: ça veut dire: on part de 4 et on compte 3 fois "vers la droite", nous avons: 4 - 5 - 0 - 1.  Alors 4 + 3 fait 1.

Il est clair que ce genre d'addition ne peut pas servir pour "compter des objets physiques".  Si vous avez 4 vaches, et vous ajoutez 3 vaches, vous n'avez pas 1 vache.  Mais nous voulons considérer les nombres naturels pour représenter des données, et pas pour compter des vaches.  Alors, cette "addition" peut faire l'affaire, comme opération sur des données.  Si un nombre représente un film, l'important est que nous utilisons des opérations des opérations réversibles, qu'on puisse revenir en arrière pour retrouver le nombre qui représente le film.  Dans la mesure où 4 + 3 = 1 n'a aucun sens pour compter des vaches, on peut parfaitement considérer que 4 représentait notre donnée avant, et cette donnée est maintenant, après l'opération +3, représentée par 1, du moment où on peut retrouver 4.  Et on peut !  1 - 3 = 4.  Si on part à 1, et on fait 3 pas "vers la gauche", on a:  1 - 0 - 5 - 4.  On arrive bien sur 4.

 L'addition, ainsi défini sur cet ensemble de nombres naturels de façon cyclique, forme un group.

Au lieu d'inventer plus de nombres, on a restreint la quantité de nombres à une quantité finie, et nous avons modifié l'addition pour qu'elle fasse un groupe avec cet ensemble.  Mais cette addition ne représente plus "compter des objets physiques".

Ce groupe a une relation très forte avec la division Euclidienne: le résultat d'une opération est obtenu en prenant l'opération "normale" d'addition ou de soustraction dans les entiers, et de la faire suivre par une division avec reste, où le diviseur est le nombre d'éléments dans l'ensemble.  Le résultat est le reste.

Si nous avons, dans notre groupe de 6 éléments, l'addition 3 + 4, nous pouvons faire d'abord l'addition normale, 3 + 4 = 7.  Ensuite nous divisons par 6.  7 / 6 = 1 avec reste 1.  Ceci est alors le résultat de 3 + 4 dans le groupe: 3 + 4 = 1.  Ça marche aussi pour la soustraction.  1 - 3 = -2.  La division Euclidienne de -2 / 6 est -1, avec un reste de 4, car -1 x 6 + 4 = -2.  Donc dans notre groupe, 1 - 3 = 4.

Nous pouvons éteindre notre définition cyclique aux multiplications.  3 x 4 = 12, et 12 / 6 = 2 avec reste 0.  donc 3 x 4 = 0.  Ainsi nous avons défini la multiplication dans l'ensemble cyclique avec 6 éléments.  Malheureusement, la division ne marche pas toujours.  Dans notre exemple, nous ne pouvons pas diviser 0 par 4, pour obtenir 3, parce que c'est aussi égal à 0: 0 / 4 = 0, car 0 x 4 = 0.  Nous aurions alors 2 réponses: 0 et 3.  Il n'y a pas d'astuce non plus, en prenant une division "normale", pour obtenir le résultat éventuel d'une division cyclique.

Pour la plupart des ensembles cycliques l'ensemble, équipé avec l'addition et la multiplication cyclique, forme un anneau.

Mais il y a une propriété particulière si le nombre d'éléments dans l'ensemble cyclique est un nombre premier.  Effectivement, si c'est le cas, la division marche toujours !  Nous allons l'illustrer avec l'exemple de 5 éléments.  Le tableau de multiplication ressemble à ceci:

x	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

Comme nous pouvons voir, en dehors de la ligne et la colonne contenant 0, chaque ligne, et chaque colonne, contient exactement une fois tous les éléments non-zéros.  C'est bien sûr la condition pour pouvoir faire "marche arrière".  Si tous les éléments non-zéro apparaissent exactement une seule fois dans chaque colonne (et donc aussi dans chaque ligne, comme le tableau est symétrique), cela veut dire que "multiplier avec la tête de la colonne" peut générer chaque élément non-nul.  Mais alors, chaque élément non-nul (résultat de la multiplication avec la tête de la colonne) peut être divisé par la tête de la colonne.  Et comme cela est vraie pour toutes les colonnes, on peut donc diviser tout élément non-nul par tout autre élément non-nul.

Si nous voulons diviser, disons, 3 par 4, nous regardons dans la colonne avec tête 4, où se trouve 3.  Ça apparaît dans la rangée avec 2 comme tête.  On voit donc que 2 x 4 = 3 et il en suit que 3 / 4 = 2.

La propriété de la plus grande importance est donc:

Dans le cas où le nombre d'éléments dans un ensemble cyclique est un nombre premier, cet ensemble, avec l'addition et la multiplication, est un champs.

Nous avons finalement donc, notre champs avec des nombres naturels !  Nous n'avions pas besoin d'inventer des nombres négatifs ou des fractions.  Bien sûr, le prix à payer c'est que cette addition, et cette multiplication ne marche pas avec des objets physiques.  Mais comme nous considérons des nombres comme des données, cela ne pose pas de soucis pour nos applications.

 La propriété clé d'un champ cyclique avec p éléments (avec p donc un nombre premier) est que la multiplication de 0, 1, 2, 3, ... , p-1 avec une constante non-zéro résulte en un réarrangement, une permutation de ces nombres, où chaque nombre apparaît une seule fois.  De ceci on peut déduire le Petit Théorème de Fermat:

Pour chaque entier a non-divisible par le nombre premier p, nous avons a^p-1 = 1 dans le champs cyclique.

Il y a une formulation légèrement plus générale du Petit Théorème de Fermat:

Pour chaque entier a, et chaque nombre premier p, nous avons: a^p = a mod p.

Champs finis

Souvenez-vous qu'un champs est un ensemble dans lequel il y a deux opérations (que nous appelons souvent "addition" et "multiplication" tel que leurs opérations (qu'on appelle soustraction et division) sont toujours définis (sauf la division par zéro).  Il y a aussi deux éléments neutres: "zéro" pour l'addition, et "un" pour la multiplication.

On appelle le caractère d'un champs, le nombre de fois qu'on peut ajouter "un" pour obtenir "zéro".  Si cela n'arrive jamais, alors le caractère est zéro.

Dans notre champs cyclique avec p éléments, le caractère est p.  Effectivement, si on ajoute p fois 1 + 1 + ... + 1, on obtient zéro.  Nos champs cycliques sont spéciaux, dans le sens que leur nombre d'éléments est égal à leur caractère.

On peut montrer que pour tout champ fini avec q éléments, et caractère p, il faut que q soit une puissance entière de p, et qu'il y a précisément un seul champs (à des équivalences prêt) pour chaque nombre premier et chaque puissance f, tel que q = p^f.  Quand f = 1, le champs est le champs cyclique que nous avons étudié, et quand f est plus grand que 1, ce champs pourra être représenté par un f-tuple d'éléments du champs cyclique.  En d'autres termes, en étudiant les champs cycliques, nous étudions en fait tous les champs finis.  Il n'y en a pas d'autres.

Un champs fini est composé de deux groupes finis: il y a le groupe additif avec tous les éléments du champs et il y a le groupe multiplicatif qui a tous les éléments du champs à part zéro.  Dans ce qui suit, nous allons considérer surtout le groupe multiplicatif du champs.  Nous allons parler de générateurs du champs, mais nous voulons en fait dire, générateur du groupe multiplicatif de ce champs.

Générateurs de champs et de groupes.

Si nous avons un groupe fini avec une opération que nous appelons "multiplication", alors, si on prend un élément a du groupe, et on le multiplie un certain nombre de fois, n, avec lui-même, alors nous appelons cela élever a à la puissance n: aⁿ = a x a x ... a (n fois).

Si le groupe que nous considérons est le groupe cyclique de p éléments avec l'addition, alors la puissance n'est rien d'autre que la multiplication jusqu'a p - 1.  Mais nous allons essentiellement considérer le groupe multiplicatif.

S'il y a q éléments dans le groupe (dans le groupe multiplicatif du champs, il y a un élément en moins que dans le champs même: on enlève zéro), et nous choisissons un élément a de ce groupe, nous pouvons considérer la séquence des puissances consécutives de a: a ; a x a ; a x a x a ; ....  Bien sûr, comme le groupe n'a pas plus que q éléments, il faudra que tôt ou tard, il y ait deux résultats égaux: a^m = aⁿ.  Si on divise maintenant par la puissance la plus petite, (disons, m), alors il en suit: a^{(n - m)} = 1.

En d'autres termes, dans la séquence des puissances successives de a, nous sommes bien obligé de rencontrer 1.  A la première occurrence, la plus petite puissance de a qui donne 1 s'appelle l'ordre de l'élément a dans le groupe.

 Il est clair que l'ordre d'un élément ne peut jamais être plus grand que q, le nombre d'éléments dans le groupe.  En fait, l'ordre d'un élément doit être un diviseur de q.

Considérons le champs cyclique avec 5 éléments (5 est un nombre premier).  Le groupe multiplicatif ne contient que 4 éléments: 1, 2, 3 et 4.

L'ordre de 1 est 1, parce que 1¹ = 1.

L'ordre de 2 est trouvé ainsi: nous avons les puissances successives de 2: 2, 4, 3, 1.  L'ordre de 2 est donc 4.

L'ordre de 3 est trouvé: 3, 4, 2, 1.  L'ordre de 3 est donc 4.

L'ordre de 4 est trouvé: 4, 1.  L'ordre de 4 est 1.

Un générateur du groupe (et dans le cas d'un champs, du champs) est un élément du groupe ou du champs, tel que son ordre est égal au nombre d'éléments du groupe.  Cela veut dire que tous les éléments du groupe peuvent être écrits comme une puissance de cet élément.

Nous voyons aussi pourquoi le groupe additif n'est pas très intéressant.  Comme il y a un nombre premier p d'éléments dans le groupe additif (dans le groupe multiplicatif, il y a p - 1 éléments, qui n'est pas un nombre premier !), alors les éléments ont leur ordre égal à 1, ou à p.  Zéro a ordre 1, et tous les autres ont ordre p.  Tous les éléments non-zéro sont des générateurs du groupe additif.  C'est pourquoi nous nous concentrons sur le groupe multiplicatif si nous avons un champs.

Il peut être démontré que tout groupe (et donc tout champs) a ou moins un seul générateur.

Les générateurs sont intéressants car un générateur spécifie une permutation des éléments du group (ou champs) hautement non-triviale.   Si nous considérons nos données comme un nombre d dans un champs fini (avec p éléments, où p est un nombre premier, bien plus grand que le nombre qui représente nos données).  Maintenant, supposons que nous avons choisi un générateur a dans ce champs.   Nous pouvons maintenant considérer f = a^d comme une transformation de données en d'autres données.  Dans la mesure où le calcul de f est relativement facile, il n'y a pas souvent une façon simple de calculer d si nous n'avons que f.  En d'autres termes, il y a une fonction "sens unique" en terme de facilité d'exécution.  De telles fonctions sont extrêmement importantes dans la cryptographie.  Le problème de calculer d à partir de f est appelé "le problème du logarithme discret", car revenir de f vers d ressemble fortement à la fonction logarithme dans les nombres réels (si f = a^d alors d = log_a f dans le champ des réels).  Dans beaucoup de groupes, le problème du logarithme discret est essentiellement insoluble (ou au moins, on ne sait pas comment le faire), et cela est intéressant en cryptographie.  Le groupe des additions n'est pas intéressant pour ce problème, parce que là, le "logarithme discret" n'est rien d'autre que la division, et celle-la n'est pas difficile à exécuter. 

L'anneau des polynômes

Sur tout anneau, on peut construire un anneau polynomial.  L'anneau de départ est l'anneau de base.  Cet anneau de base peut être un anneau, ou un champs.  L'anneau (ou le champs) a deux opérations, addition et multiplication.

Un polynôme sur l'anneau B,+,x est une fonction de B dans B, pour laquelle il y a une prescription avec une formule polynomiale:

f(b) = A₀ + A₁ x b + A₂ x b² + A₃ x b³ + .... + A_m b^m

où A₀, A₁, ... A_m sont aussi des éléments de B. Étant donné que B est un anneau, les opérations de la formule sont toujours possible, et la fonction est donc définie sur tout B.  Le polynôme est totalement défini si nous connaissons les coefficients.  La plus grande puissance de l'argument est appelée le degré du polynôme.

L'ensemble des polynômes même est écrit B[X].  Les éléments de B[X] peuvent être représentés par des tuples  d'éléments de B: (A₀, A₁, A₂... A_m).

Les polynômes mêmes peuvent être additionnés ensemble, et on peut multiplier des polynômes.  Le résultat est de nouveau un polynôme.  La soustraction des polynômes est toujours possible, et il y a un polynôme "zéro": le polynôme avec tous les coefficients zéro.  Effectivement, si on ajoute ce polynôme à n'importe quel autre, on obtient le dernier comme résultat.  Il y a aussi un polynôme "un".  C'est le polynôme avec tous les coefficients zéro, sauf A₀ qui est 1.  Dans certains cas, nous pouvons diviser un polynôme par un autre, et on obtient un polynôme.  Mais dans beaucoup de cas, cette division n'est pas possible (on obtiendrait une fonction rationnelle, et plus un polynôme).  Cependant, la division "avec reste" est toujours possible avec des polynômes.  Ainsi, l'ensemble des polynômes, équipés de l'addition et la multiplication, est un anneau aussi:

B[X], + x est un anneau.

Si des polynômes peuvent être défini sur un anneau de base, ça devient beaucoup plus intéressant si l'anneau de base B est un champs.

Effectivement, dans un champ fini avec p éléments (où p est un nombre premier), nous savons que l'ordre le plus élevé d'un élément est p-1 (et que de tels éléments existent: les générateurs du champ).  Ainsi, un polynôme comme fonction ne peut pas contenir des termes avec un degré plus élevé que p - 1, car un terme pareil serait le même que celui d'un degré plus bas.  Un terme de puissance p + 1 serait le même que celui de puissance 2 par exemple.  Comme fonction, ce polynôme serait identique à un polynôme de plus petit ordre, où le terme A_p+1 b^p+1 serait absent, et A_p+1 serait ajouté à A₂.  C'est une conséquence directe du Petit Théorème de Fermat: X^p = X dans B.

 Ainsi, l'ensemble des polynômes comme fonction est un ensemble fini, avec degré fini.  La représentation avec des tuples contient des tuples de longueur au maximum égale à p.

Ainsi, B[X], comme ensemble de fonctions polynomiales, est un anneau fini.

Cependant, rien n'empêche de considérer des expressions polynomiales formelles de degré supérieur à p - 1.  Dans ce cas, il faut voir B[X] comme l'anneau des expressions formelles polynomiales, et pas comme des fonctions polynomiales.  Dans ce cas, B[X[ reste infini (car la longueur des tuples n'a pas de limite).

Un polynôme est unitaire si le coefficient du terme avec le plus grand degré est 1.  Tout polynôme est un polynôme unitaire multiplié avec une constante (un élément du champs de base).

Un polynôme unitaire est appelé irréductible (ou polynôme premier) s'il n'existe aucun polynôme unitaire autre que lui-même et non-trivial (c.a.d. pas une constante) qui le divise.  Tout polynôme unitaire peut être écrit de façon unique comme un produit de polynômes unitaires irréductibles.

Le polynôme unitaire irréductible dans B[X] a un rôle un peu comparable aux nombres premiers dans l'anneau des entiers.

Prenons un exemple dans le champs de base {0,1,2}.  Il y a 27 fonctions polynomiales possible sur ce champs de base.  Il ne peut pas y avoir plus de fonctions en général, car chaque fonction a 3 possibilités pour 0, a 3 possibilités pour 1 et a 3 possibilités pour 2.  Ça fait 27 fonctions possibles.

Voici les 27 polynômes jusqu'à degré 2:

p(x) = 0;  résultat sur {0, 1, 2} est {0, 0, 0}

p(x) = 1; résultat sur {0, 1, 2} est {1, 1, 1}

p(x) = 2; résultat sur  {0, 1, 2} est {2, 2, 2}

Ce sont les 3 polynômes possibles de degré 0.

p(x) = 0 + x ; résultat: {0, 1, 2}

p(x) = 1 + x ; résultat {1, 2, 0}

p(x) = 2 + x : résultat {2, 0, 1}

p(x) = 0 + 2 x ; résultat {0, 2, 1}

p(x) = 1 + 2 x ; résultat {1, 0, 2}

p(x) = 2 + 2 x ; résultat {2, 1, 0}

Ce sont les 6 polynômes de degré 1.

p(x) = 0 + x² ;  résultat {0, 1, 1}

p(x) = 1 + x² ; résultat {1, 2, 2}

p(x) = 2 + x² ; résultat {2, 0, 0}

p(x) = 0 + x + x² ; résultat {0, 2, 0}

p(x) = 1 + x + x² ; résultat {1,0, 1}

p(x) = 2 + x + x² ; résultat {2, 1, 2}

p(x) = 0 + 2 x + x² ; résultat {0, 0, 2}

p(x) = 1 + 2 x + x² ; résultat {1, 1, 0}

p(x) = 2 + 2 x + x² ; résultat {2,2,1}

p(x) = 0 + 2 x² ; résultat {0, 2, 2}

p(x) = 1 + 2 x² ; résultat {1,0,0}

p(x) = 2 + 2 x² ; résultat {2,1,1}

p(x) = 0 + x + 2 x² ; résultat {0, 0, 1}

p(x) = 1 + x + 2 x² ; résultat {1, 1, 2}

p(x) = 2 + x + 2 x² ; résultat {2, 2, 0}

p(x) = 0 + 2 x + 2 x² ; résultat {0, 1, 0}

p(x) = 1 + 2 x + 2 x² ; résultat {1, 2, 1}

p(x) = 2 + 2 x + 2 x² ; résultat {2, 0, 2}

sont les 18 polynômes de degré 2.  Nous avons en même temps aussi trouvé toutes les fonctions de B à B.

Bien sûr, nous pouvons considérer des expressions formelles polynomiales de degré supérieur, mais il est clair que ces expressions ne peuvent pas être des fonctions sur B, mais juste des tuples d'éléments de B dont leur composition par addition et par multiplication se fait comme si c'était des termes de polynômes.  Dans cet anneau abstrait d'addition et de multiplication de tuples, on peut définir des tuples irréductibles et la division Euclidienne des tuples (avec reste).  Cet anneau de tuples (formellement écrits comme des expressions de polynômes) est infini. 

La vraie définition mathématique de B[X] correspond à ces expressions abstraites.  En fait, B[X] est l'anneau qui est le résultat de considérer l'extension minimale de B, si on ajoute à B un élément supplémentaire: X.  Pour que cette extension soit un anneau, il faut bien que toutes les expressions "polynomiales" en X y soient: les combinaisons linéaires des éléments de B, et toutes les puissances de X.  Donc, on peut voir B[X] comme l'anneau de B avec un élément X de plus.

Extensions de champs

Prenons un champ cyclique avec p éléments, qu'on appellera F_p.  Considérons maintenant l'anneau des polynômes formels F_p[X].  C'est un anneau et dans cet anneau, il y a une division Euclidienne.  Il y a donc des polynômes irréductibles.    Souvenons-nous comment nous avions obtenu un champs avec des nombres naturels: nous avions pris l'anneau des entiers, nous avions pris un nombre premier, et nous avions regardé l'ensemble des restes par division par cet entier: c'était le champs cyclique.

Essayons la même chose avec F_p[X].  Choisissons un polynôme dans F_p[X].  Considérons l'ensemble F_p[X] / P(X), c'est à dire, le sous-ensemble de polynômes qui sont les restes après division par P(X).  Si nous définissons une nouvelle addition et une nouvelle multiplication dans F_p[X] / P(X), qui est la "normale" en F_p[X], mais suivie de "modulo P(X)", alors il s'avère que si P(X) est un polynôme irréductible unitaire, alors F_p[X] / P(X) équipé de l'addition et la multiplication "modulo P(X)" est un champs fini.

Si le polynôme irréductible est de degré m, alors le champs résultant aura p^m éléments.  C'est une des façons pratiques de fabriquer des champs finis avec un nombre non-premier d'éléments.  Galois a démontré qu'en fait, on trouve tous les champs finis ainsi.

Comme illustration, le fameux standard de cryptage, AES, utilise à un certain moment, le champs basé sur F₂ avec le polynôme irréductible f(X) = X⁸ + X⁴ + X³ + X + 1. Ça fait un champs avec 2⁸ = 256 éléments.  C'était fait pour des raisons pratiques, car un élément de ce champs est représenté par un octet.

Et maintenant, nous fermons la boucle: la relation entre polynômes vus comme "fonctions de B à B" , les "polynômes formels avec B et un élément supplémentaire X", et les anneaux (ou champs) F_p[X] / P(X) est la suivante:

Si nous considérons le polynôme X^p - X (qui n'est jamais un polynôme irréductible car on peut diviser par (X-1) et par X) et nous construisons:

F_p[X] / (X^p - X)

alors nous retrouvons les polynômes fonctions.  Comme le polynôme diviseur n'est pas un polynôme irréductible, l'anneau des polynômes fonctions ne sera jamais un champs.

L'anneau des polynômes fonction de F_p en F_p est obtenu en prenant l'anneau quotient F_p[X] / (X^p - X).

Dans notre exemple nous avions pris le champs de base F₃.  En prenant l'ensemble quotient (l'ensemble des restes après division) des polynômes modulo X³ - X, nous ajoutons en fait le coefficient de X³ à celui de X en éliminant la puissance de 3 ; nous ajoutons le coefficient de X⁴ à celui de X² en éliminant la puissance 4, etc.. ce qui est exactement ce que nous faisons quand nous considérons les puissances de X comme des fonctions sur F₃.

En d'autres termes, un polynôme 2 X⁴ + X³ = 2 (X⁴ - X²) +2 X² + X³ - X + X = 2 X (X³ - X) + (X³ - X) +2 X² + X et après division par (X³ - X) et la prise du reste, nous obtenons 2 X² + X.  Notez que le -X est une autre façon d'écrire 2X dans F₃.

Finalement il peut être intéressant de remarquer que le champs (ou anneau) quotient F_p[X] / P(X) et le champs (ou anneau) quotient F_p[X] / Q(X) où P(X) et Q(X) sont des polynômes de même degré m, sont les mêmes ensembles, à savoir les expressions polynomiales avec des coefficients en F_p jusqu'au degré (m - 1).  Ce n'est que la loi multiplicative qui est différente sur ces ensembles.

L'addition n'est pas affectée, car additionner deux polynômes de degré inférieur à m donnera toujours un polynôme de degré inférieur à m (il n'y a pas de "retenue") et donc le quotient par division par un polynôme de degré m sera toujours zéro.  Le polynôme de degré inférieur à m est son propre reste.

Illustrons cela avec notre exemple de F₃ en prenant deux polynômes de degré 3.  Les deux ensembles quotient sont identiques, et sont les polynômes de degré 2 ou moins, que nous avons déjà énumérés.

Prenons P(X) le polynôme X³ - X, pour nous donner le jeu de polynômes fonctions.  Prenons Q(X), le polynôme X³.  Notez que les deux polynômes choisis sont réductibles, donc les deux résultats ne seront pas des champs.   Nous prenons juste un exemple simple pour limiter les calculs.

Choisissons deux polynômes dans l'ensemble:

p₁(X) = 2 X + 1

p₂(X) = X² + 1

Dans le premier anneau (celui modulo P(X)), le produit de p₁ et de p₂ devient:

p₁(X) p₂(X) = (2 X + 1) (X² + 1) = (2 X³ + 2 X + X² + 1) mod P(X) ce qui donne: X² + (2 + 2) X + 1 = X² + X + 1.  Le (2 + 2) X vient du terme original 2 X et le cofficient 2 de X³ qui s'est réduit à un terme de premier ordre par l'opération modulo.

Dans le deuxième anneau (modulo Q(X)), ce même produit devient:

p₁(X) p₂(X) = (2 X + 1) (X² + 1) = (2 X³ + 2 X + X² + 1) mod Q(X) ce qui donne X² + 2 X + 1, car ici, l'opération modulo enlève simplement tous les termes de X³ ou plus grand.

Nous voyons que le produit de deux polynômes formels donne lieu à deux résultats différents dans les deux anneaux.  Dans le premier,  p₁ x p₂ = X² + X + 1, et dans le deuxième, p₁ x p₂ = X² + 2 X + 1.

Vérifions finalement que le premier anneau correspond bien aux fonctions polynomiales et que le deuxième ne l'est pas.  La multiplication de deux fonctions doit être telle (c'est ça définition), que la fonction produit donne comme image de chaque élément de F₃ le produit (dans F₃) des deux images de l'élément sous les deux fonctions dont on étudie le produit.  En d'autres termes, si  p₃ = p₁ p₂ et p₁, p₂ et p₃ sont des fonctions sur F₃, alors pour chaque a en F₃ nous devons avoir que  p₁(a) = b₁, p₂(a) = b₂ et p₃(a) = b₃ tel que b₃ = b₁ b₂.

Quelles sont les images sous nos polynômes ?

{0, 1 et 2} par p₁ donne {1, 0 et 2}

{0, 1, et 2} par p₂ donne  {1, 2 et 2}

Le produit des images est {1, 0, 1}.

Est-ce que cela correspond à p₃ sous la loi de multiplication du premier anneau ?  On peut vérifier que c'est bien le cas, car le polynôme (dans notre liste de 27 possibilités) qui a comme image {1, 0, 1} est bien X² + X + 1 comme nous avons trouvé.

Et ce n'est pas le polynôme  X² + 2 X + 1qui est le résultat dans le deuxième anneau.  Si nous interprétons (ce que nous n'étions pas supposé de faire!) ce polynôme comme une fonction, son image serait {1, 1, et 0}.

Comme avec l'anneau des entiers, nous avons donc dû faire un sacrifice.  Avec l'anneau des entiers, nous avons pu fabriquer un champs en prenant en ensemble quotient, mais le prix à payer était que les opérations addition et multiplication perdaient leur signification "compter des objets physiques".  Trois vaches plus quatre vaches ne faisaient plus 7, mais une vache.  Ici, avec l'anneau des polynômes, nous pouvons fabriquer un champs de polynômes dans l'ensemble quotient, mais le prix à payer c'est que les polynômes ne sont plus des fonctions mais des expressions formelles.

Conclusion

Comme tous les données numériques, et par extension, toute information que nous pouvons traiter, peuvent être vus comme un nombre naturel, les transformations générales de données (sans référence à leur interprétation particulière et leur signification), comme la cryptographie, sont des transformations de nombres naturels.  Pour avoir des transformations utiles qui nous permettent de reconstituer les données d'origine, nous avons besoin d'opérations réversibles sur les nombres naturels.  Les additions et multiplications standard que nous apprenons en école primaire ne sont pas réversibles tels quels.  Nous avons vu comment construire des additions et multiplications sur des ensembles finis de nombres naturels qui sont réversibles et qui se comportent jusqu'à un certain point comme l'addition et la multiplication normale.  Une telle structure est appelée un champs. 

La construction de base est un champs cyclique F_p où p est un nombre premier (si p n'est pas un nombre premier, la multiplication n'est pas réversible, et nous n'avons pas un champs).  Nous avons vu comment construire des champs plus compliqués avec des n-tuples de nombres naturels, interprétés comme des polynômes formels sur les champs cycliques.  Ils ont pⁿ éléments et ils sont construits en prenant le champs quotient sur l'anneau (infini) des polynômes formels sur F_p, à savoir F_p[X], et un polynôme irréductible de degré n.  En faisant cela, nous avons en fait construit des représentations de tous les champs finis.   Galois a démontré qu'il n'y en avait pas d'autres.

En ayant construit tout champs finis avec un ensemble fini de nombres naturels, nous pouvons effectuer tous les calculs dans ce champs, à condition de:

• pouvoir faire des additions, soustractions, multiplications et divisions en F_p
• pouvoir faire des additions, soustractions, multiplications et divisions dans F_p[X] / P(X)

Un champs est un peu du luxe: nous avons souvent seulement besoin d'une seule opération réversible, pour "faire des choses et revenir".  Ainsi, des groupes finis sont aussi intéressant.  Nous avons déjà des groupes intéressants: les groupes multiplicatifs de tous les champs que nous avons considéré.  Mais il y a plus de groupes que les seuls groupes multiplicatifs de champs: il y a des groupes qui ne font pas partie d'un champs.  Dans la pratique nous voulons bien sûr représenter les éléments de ces groupes par des nombres naturels et nous allons construire ces groupes alors à l'intérieur d'un champs fini.