Polynôme générateur

On 7 avr, 13:17, Michelot <mhostett...@voila.fr> wrote:

En quoi pourrait-on dire que G(x) = 1 + X^9 + X^11 est un polynôme
générateur ?
2^11-1 = 2047 n'est pas un nombre premier. Il n'est donc pas possible

de réaliser un LFSR avec ce polynôme. Ceci répond-il à ta question?

According to Michelot <mhostettler@voila.fr>:

Tout polynôme pourrait-il être un polynôme générateur ?

Dans un groupe, on peut définir le sous-groupe engendré par un élément
comme le résultat de toutes les applications possibles de la loi de
groupe sur cet élément (en gros). Un polynôme, s'il fait partie d'un
groupe (par exemple, ce polynôme est inversible dans un certain anneau
de polynômes, et fait donc partie du groupe des polynômes inversibles
dans cet anneau, est alors mécaniquement générateur de son sous-groupe
engendré.

Là on peut se demander si ce sous-groupe engendré couvre tout le
groupe englobant, ou seulement une sous-partie stricte.

Il convient de préciser les termes de la question, ça devient trop flou.


Un cas courant dans certaines branches de la cryptographie est de
s'intéresser aux anneaux de polynômes (à coefficients dans un corps fini
donné) qui résultent du quotientage de l'anneau (brut) des polynômes par
un polynôme donné.

Soit K un corps fini. Un polynôme P à coefficients dans K est une
suite presque nulle d'éléments de K, notée comme ceci :

P = sum_{i=0}^infty p_i X^i

où les p_i sont des éléments de K. La condition "presque nulle"
signifie qu'à partir d'un certain rang, les p_i sont tous égaux à
zéro. On peut donc définir le "degré" d'un polynôme, qui est le
rang du dernier coefficient non-nul. Autrement dit, on dit que P
est de degré n is p_n est non nul, mais p_j = 0 pour tout j > n.
Ceci couvre tous les polynômes sauf le polynôme nul dont tous les
coefficients sont nuls, et dont on dit conventionnellement qu'il
est de degré 0. Un polynôme "constant" est un polynôme de degré
zéro (p_i = 0 pour tout i >= 1).

On peut définir des opérations d'addition, soustraction, multiplication
et division euclidienne sur les polynômes, comme on ferait sur les
entiers. D'ailleurs, si on implémente ces opérations, ça ressemble
beaucoup à ce qu'on ferait pour implémenter des calculs sur des nombres
entiers, sauf qu'il n'y a pas de "retenue" à propager. Cela forme un
anneau, noté K[X] ("anneau des polynômes à coefficients dans K").

Comme il y a division euclidienne (avec quotient et reste), on peut
parler de divisibilité (quand le reste est nul) donc de polynôme premier
(divisible seulement par lui-même et par les polynômes constants non
nuls). On peut aussi définir des anneaux de polynômes modulaires, modulo
un certain polynôme de degré n >= 1. Plus précisément, si Q est un
polynôme de degré n >= 1 (donc Q n'est pas constant, donc pas nul non
plus), alors on définit l'anneau K[X]/Q qui contient les polynômes de
degré 0 à n-1, et où toutes les opérations sont réduites modulo Q (i.e.
on fait le calcul sur des polynômes bruts dans K[X], puis on fait une
division euclidienne par Q, et on ne garde que le reste, de degré
strictement inférieur à n par définition de cette division).

Il y a dans K[X]/Q des éléments inversibles ; ce sont les polynômes U
pour lesquels il existe un polynôme V tel que U*V = 1 mod Q. Les
inversibles forment un groupe multiplicatif, noté K[X]/Q*. Chaque
élément de ce groupe génère un sous-groupe (à partir de l'élément P, on
considère 1, P, P^2, P^3, etc... et les inverses de tous ces éléments).
Je note <P> le groupe multiplicatif engendré par P. Si ce sous-groupe
est égal à K[X]/Q* en entier alors on dit que l'élément P est un
_générateur_ du groupe des inversibles.

Si Q est un polynôme premier alors K[X]/Q est un corps. Cela revient à
dire que K[X]/Q* contient tous les polynômes de K[X]/Q sauf le polynôme
nul.

Si K est un corps à k éléments, alors K[X]/Q contient k^n éléments. Si
Q est premier alors K[X]/Q* contient k^n-1 éléments. Si P est un
inversible alors le cardinal de <P> divise celui de K[X]/Q*. Si
k^n-1 est un nombre entier premier, alors <P> ne peut être égal qu'à 1
(si P = 1) ou k^n-1 (dans tous les autres cas). Dans cette situation,
tous les polynômes inversibles sauf 1 sont générateurs du groupe des
inversibles.


En cryptographie, ces choses ont plusieurs usages. Le cas traditionnel
est celui des registres à décalage à rétroaction linéaire (LFSR en
anglais). Un LFSR contient n bits. À chaque tour, on décale tous ces
bits d'un cran vers la gauche, ce qui fait "tomber" un bit à gauche, et
crée un trou à droite. On comble le trou en calculant un "ou exclusif"
(le fameux XOR) de certains des bits du registre avant décalage, dont
(en général) celui qui est tombé.

On peut faire correspondre le LFSR à un anneau K[X]/Q. On considère K
le corps à deux éléments (0 et 1 ; l'addition sur ce corps est
précisément le XOR). On considère Q = X^n + sum_{i=0}^{n-1} q_i X^i
tel que q_i = 1 si le bit numéro i rentre dans le XOR du LFSR, 0
autrement. C'est un polynôme de degré n. On peut alors s'apercevoir
que faire tourner le LFSR d'un bit revient à considérer l'état du
registre comme un polynôme (chaque bit étant un coefficient) et à
multiplier ce polynôme par X (ou le diviser par X, ça dépend du sens
de numérotation, mais tout ça est isomorphe et je saute les détails).

Du coup, faire tourner le LFSR revient à partir d'un état P (le
polynôme correspondant à l'état initial) et à calculer PX, PX^2,
PX^3, etc... dans K[X]/Q.

_Si_ les conditions suivantes sont respectées :

-- Q est un polynôme premier (donc K[X]/Q est un corps)
-- X est générateur de K[X]/Q*
-- l'état initial du LFSR n'est pas nul (il y a au moins un bit non
nul dedans)

_alors_ on voit que le LFSR se balade sur tous les inversibles et
son état fait alors un grand cycle de taille 2^n-1, ce qui est le
plus grand qu'on puisse faire et qui est considéré comme une "bonne
chose" pour les usages traditionnels des LFSR.

Dans ces conditions, on dit que Q est un polynôme _primitif_.

En quoi pourrait-on dire que G(x) = 1 + X^9 + X^11 est un polynôme
générateur ?

Si on considère que K est le corps à deux éléments, alors le polynôme
G = X^11 + X^9 + 1 dans K[X] est primitif. Autrement dit, non seulement il
est premier (on ne peut pas trouver deux polynômes de K[X] U et V, tous
deux de degré 10 ou moins, tels que G = U*V) mais en plus le sous-groupe
engendré par X modulo G contient tous les 2047 polynômes non-nuls de
K[X] de degré 10 ou moins.

On peut imaginer dire que "G est un polynôme générateur" mais c'est un
abus de langage, le terme technique correct étant "primitif".

On notera que 2047 = 23 * 89 donc il n'est pas gagné d'avance qu'un
polynôme premier de degré 11 soit également primitif. C'est néanmoins
le cas pour le polynôme G ci-dessus. Un exemple de polynôme de degré
11 premier mais pas primitif est :

R = X^11 + X^7 + X^6 + X + 1

K[X]/R est bien un corps, donc tous les polynômes non nuls de degré 10
ou moins sont bien inversibles modulo R, et en particulier le polynôme
P = X. Mais le groupe engendré par X est de taille 89 seulement. Donc
un LFSR qui utiliserait des bits de rétroaction aux positions 0, 1, 6
et 7 ferait un cycle de longueur 89 (pas toujours le même cycle de
valeurs, suivant l'état initial, mais quel que soit l'état initial il
reviendrait dessus en 89 étapes).


--Thomas Pornin

PS : dans tout ça j'ai parlé du cas où K est un corps.
Traditionnellement on utilise le corps à deux éléments. Maintenant, ça
marche aussi avec d'autres corps finis, et d'ailleurs le quotientage par
un polynôme est une mécanique servant à fabriquer des corps finis. On
peut _aussi_ envisager le cas où K n'est pas un corps mais seulement un
anneau ; par exemple, si on envisage un LFSR où les éléments ne sont pas
des bits mais des chiffres décimaux (les chiffres de 0 à 9 forment un
anneau mais pas un corps). Les choses deviennent alors fichtrement plus
compliquées.

Bonjour Emile,

Merci pour ces commentaires

En quoi pourrait-on dire que G(x) = 1 + X^9 + X^11 est un polynôme
générateur ?

2^11-1 = 2047 n'est pas un nombre premier. Il n'est donc pas possible
de réaliser un LFSR avec ce polynôme. Ceci répond-il à ta question ?

Ce polynôme est normalisé dans IEEE 802.3, il constitue le LFSR
utilisé pour l'embrouillage de l'Ethernet 100Base-TX.

Ma petite étude a conduit à cela :

(1) Tout polynôme élément de F2[X], de degré L, est associable à u n
LFSR constitué de L cellules

(2) La qualité du LFSR revient à observer la période de la séquence
binaire qu'il génère (lorsqu'il tourne sur lui-même, sans être assoc ié
à un embrouilleur par exemple), et donc d'observer la propriété du
polynôme

(3) Une première condition de qualité est obtenue lorsque le polynôme
G(X) associé est irréductible. On aurait par exemple la même suite
binaire avec G(X) = X^10 + X^7 + X^4 + X^3 + X + 1 non irréductible
qu'avec X^3 + 1 irréductible, diviseur du précédent. Le second LFSR
permet d'économiser 7 cellules par rapport au premier.

(3) Une seconde condition concerne la longueur (ou durée) de la
période. Celle-ci est maximale, égale à T = 2^L - 1, si le polynôm e
irréductible est en plus primitif, c'est à dire s'il divise (1 + X^T),
avec T valeur minimum possible.

Par exemple G(X) = X^4 + X^3 + X^2 + X + 1 est irréductible, il divise
(1 + X^15) mais aussi (1 + X^5), la période de la séquence binaire
n'est donc pas 15 mais T = 5.

Je note ce que Thomas nous apprend (...ou réapprend) : il n'est pas
gagné qu'un polynôme irréductible de degré 4 soit aussi primitif, ca r
(2^4 - 1) = 3 x 5.

Voilà ma vision de cet instant, écrite en termes simples (du moins je
le suppose).

Merci pour vos commentaires ou vos corrections,
Michelot

Bonjour Thomas,

Dans un groupe, on peut d�finir le sous-groupe...

J'ai lu une fois, mais il me faudra d'autres passes. Je retiens en
tous cas les exemples par lesquels tout s'éclaircit. Dans le message à
Emile, je me réfère à l'un d'eux.

Cordialement,
Michelot

On 10 avr, 14:26, Michelot <mhostett...@voila.fr> wrote:
Bonjour Michelot

En quoi pourrait-on dire que G(x) = 1 + X^9 + X^11 est un polynôme
générateur ?

2^11-1 = 2047 n'est pas un nombre premier. Il n'est donc pas possible
de réaliser un LFSR avec ce polynôme. Ceci répond-il à ta questio n?

Je devrais préciser ce que j'ai dit précédemment. Comme 2047 n'est pas
premier, il n'est pas possible de réaliser un LFSR à séquence maximum
avec 11 cellules binaires. Si le polynôme G(x) = 1 + X^9 + X^11 est
repris dans IEEE802.3, (ce que j'ignorais), je suppose que les
responsables qui ont adopté ce polynôme, l'ont choisi en connaissance
de cause, ils sont certainement compétents en la matière. Tout dépend
du but qu'ils recherchaient.

J'ignore la motivation qui t'anime. Comprendre pourquoi ils ont
choisi ce polynôme dans l'application qu'ils le destine? Si tu
recherches un polynôme à séquence maximum pour une application bien
déterminée, ce n'est pas à celui là qu'il faut penser. Par contre, e n
prenant un ensemble de plusieurs LFSR avec des séquences de longueurs
différentes, il y aura répétition de l'ensemble des états des LFSR
après "L" impulsions horloge, "L" étant le PPCM de toutes les
différentes longueurs de séquence.

Le texte de Thomas est magistral, c'est à lire et à relire pour bien
tout comprendre, mais c'est à toi à préciser ton objectif dans ta
recherche.

Emile

According to Emile <emilemusyck@gmail.com>:

Je devrais préciser ce que j'ai dit précédemment. Comme 2047 n'est pas
premier, il n'est pas possible de réaliser un LFSR à séquence maximum
avec 11 cellules binaires.

Ben si. Enfin dans tous les cas, la séquence générée par un LFSR est
périodique (puisque l'état est fini) et pour un LFSR à 11 "cellules"
cette période ne peut pas dépasser 2047 (il n'y a que 2048 états
possibles, et l'état nul est dans son propre cycle de longueur 1).
Il y a donc une période maximale réalisable, d'au plus 2047.

Il s'avère que cette période maximale réalisable vaut 2047. Pour obtenir
une telle séquence, il suffit que le polynôme correspondant soit
primitif (i.e. premier [on peut aussi dire irréductible, c'est pareil
dans ce cas] _et_ tel que X génère un cycle passant par tous les
inversibles). Il existe des polynômes primitifs à coefficients binaires
et de degré 11, par exemple celui dont on parle (G = X^11 + X^9 + 1).

Que 2047 ne soit pas premier implique qu'il n'est pas _automatique_
qu'un polynôme premier de degré 11 soit primitif. Mais ça ne veut pas
dire que c'est impossible. En fait, il y a précisément 186 polynômes
à coefficients binaires, de degré 11 et irréductibles. Sur ces 186
polynômes, 176 sont primitifs, et donc si on les utilise pour un LFSR
on obtient une période de longueur 2047, qui passe bien par tous les
états non nuls possibles.

Sur les 10 autres, il y en a deux qui font des périodes de longueur 23 :

X^11 + X^9 + X^7 + X^6 + X^5 + X + 1
X^11 + X^10 + X^6 + X^5 + X^4 + X^2 + 1

ces deux polynômes découpent les 2047 états non-nuls en 89 cycles
disjoints de longueur 23. Quand on les utilise pour un LFSR, l'état
initial est sur un de ces cycles, et le LFSR reste dans le cycle en
question, avec une période de 23.

On notera que ces deux polynômes sont en fait deux fois le même, en
remplaçant X^i par X^(11-i). C'est tout-à-fait normal et attendu :
un LFSR avec un polynôme premier est réversible (puisque X est
inversible ; on peut multiplier par X mais aussi diviser par X)
donc en faisant tourner le LFSR dans l'autre sens, c'est comme si on
utilisait l'autre polynôme. Maintenant, si ça fait un cycle de longueur
23 dans un sens, ça fait forcément un cycle de longueur 23 dans
l'autre sens...

Il reste donc 8 polynômes premiers mais pas primitifs, qui font des
cycles de longueur 89 :

X^11 + X^7 + X^6 + X + 1
X^11 + X^8 + X^5 + X^4 + X^2 + X + 1
X^11 + X^8 + X^7 + X^6 + X^5 + X^3 + X^2 + X + 1
X^11 + X^10 + X^5 + X^4 + 1
X^11 + X^10 + X^8 + X^7 + X^6 + X^5 + X^4 + X^3 + X^2 + X + 1
X^11 + X^10 + X^9 + X^7 + X^6 + X^3 + 1
X^11 + X^10 + X^9 + X^8 + X^6 + X^5 + X^4 + X^3 + 1
X^11 + X^10 + X^9 + X^8 + X^7 + X^6 + X^5 + X^4 + X^3 + X + 1


Bon, au cas où, je me dois de préciser que les LFSR avec cycle de
longueur maximale, ça fleure bon la cryptographie de grand-papa. Il y a
un demi-siècle, on faisait du chiffrement symétrique avec un ou quelques
LFSR et en bidouillant les sorties selon une méthode qu'on croyait
finaude. Depuis, on s'est aperçu que c'est très difficile de faire
quelque chose de correct en partant dans cette direction. Les LFSR sont
des briques élémentaires utiles pour construire des schémas, mais il
faut plus que ça, sinon le schéma résultant ne sera qu'une vaste blague,
voire une fumisterie. Par ailleurs, la notion de "cycle de longueur
maximale" n'est en fait pas si importante que ça, dans ce genre d'usage.


--Thomas Pornin

Bonsoir Thomas,

Grâce à la réponse d'Emile, nous avons un développement prestigieux de
votre part, étayée avec un argumentaire que l'on ne trouvera nulle
part. Merci pour tout votre temps, il nous est très utile. Il est rare
de converser de la sorte.

On peut imaginer dire que "G est un polyn�me g�n�r ateur" mais c'est un
abus de langage, le terme technique correct �tant "primitif".

Mon domaine est plutôt le transport des signaux télécoms. Le polynôme
pris pour exemple dans cette étude concerne l'Ethernet classique
100Base-TX à 100 Mbit/s. Le LFSR fait partie d'un embrouilleur dont le
rôle est de répartir uniformément l'énergie sur le spect re bande de
base du signal, lequel avec le codage de canal 4B/5B s'étage de 0 à  
125 MHz environ.

Sans embrouillage, des raies spectrales apparaîtraient (notamment vers
31,25 MHz) et concentreraient l'énergie au point de créer une
pollution électromagnétique sur les paires de câbles avoisina ntes. Le
100Base-TX utilise 2 paires torsadées sur un câble qui en comporte 4,
les 2 autres sont inutilisées. Dans les 2 paires utilisées, l'une est
spécifique à l'émission, l'autre à la réception.

Si la diaphonie de la paire émission était trop importante, le bru it
engendré sur la paire réception gênerait le décodage du signal,
produisant un taux d'erreur important, prohibitif.

L'embrouillage avec le polynôme de degré 11 (technologie de 1990 i ssue
de FDDI et reprise par l'IEEE), ceci avant émission, a pour but
d'éviter cette diaphonie inter-paire. C'est son rôle pour le 100Ba se-
TX.

Dans d'autres circonstances, pour d'autres technologies, les
embrouilleurs ont d'autres intérêts, comme assurer le transport du
rythme du signal, éviter la reproduction de mots de contrôles,
faciliter la décorrélation de signaux en les embrouillant
différemment. Nous sommes donc dans des utilisations autres que la
cryptologie, mais avec des théories similaires.

Une question, est-il facile en observant la structure f(X) d'un
polynôme, de déterminer s'il est primitif ou pas ? Ou, alors, le s eul
moyen est de pouvoir recourir au polynôme g(X) déterminé par l'état
initial du registre, et diviser g(X) par f(X) pour savoir si le
rapport peut etre réduit.

D'après ce que vous avez écrit, on aurait f(X) = X^11 + X^9 + X ^8 +
X^5 + X^4 + X^2 + X + 1 polynôme primitif. Est-ce visible au 1er coup
d'oeil ?



Puis-je vous entraîner un peu sur le dispositif d'embrouillage,
construit à partir du LFSR. Pour fixer les idées, prenons le LSFR
générique d'équation : s(i+L) = c(1) s(i+L-1) + .... + c(L- 1) s(i+1) +
c(L) s(i).

Sur ce LFSR on ouvre la connexion s(i+L) qui sort du XOR pour
retourner à l'entrée de la cellule D dont la sortie est s(i+L-1).

La sortie du XOR rendue libre, est alors reliée à un nouvel XOR qu i
reçoit sur une autre entrée les données d'information Ye(i) à
embrouiller. Le XOR de ces 2 entrées est, d'une part, reconnecté à
l'entrée de la cellule D et, d'autre part, à la sortie de
l'embrouilleur qui fournit les iinformations embrouillées Ys(i).

Pour le polynôme de degré 11 que nous connaissons f(X) = 1 + X^9 +
X^11, l'équation de l'embrouilleur est : Ys(i) = Ye(i) + Ys(i-9) +
Ys(i-11).

On a presque envie d'écrire que l'embrouilleur réalise une divisio n,
du style :

Ys(X) = g(X) / f(X) + Ye(X) avec g(X) le polynôme d'état initial
(introduit précédemment) et f(X) le polynôme primitif. Mais j e ne sais
pas du tout si cela est exact.

Je voudrais refaire jaillir le fonctionnement du LFSR au travers de
l'embrouilleur. Mais l'information d'entrée Ye, quelconque, casse la
périodicité du LFSR.

Merci pour votre avis,
cordialement,
Michelot

On 11 avr, 18:19, Thomas Pornin <por...@bolet.org> wrote:

According to Emile <emilemus...@gmail.com>:
Bonjour,

Un grand merci pour les explications, toujours très claires. Je suis
vraiment navré d'avoir aiguillé Michelot sur une piste erronée. Il y a
un élément de ma mémoire qui a flanché. J'ai bien retrouvé dans me s
archives la copie d'une publication en 1968 de Neal Zierler et John
Brillant concernant les trinômes primitifs. Pour n=11, il y a bien un
seul trinôme primitif avec le trinôme symétrique.

Bon, au cas où, je me dois de préciser que les LFSR avec cycle de
longueur maximale, ça fleure bon la cryptographie de grand-papa.

Je ne suis pas tout à fait d'accord avec cet avis, mais cela
nécessite d'oeuvrer différemment. Tout nombre entier positif de 127
bits peut être considéré comme un élément faisant partie des
2^n-1états du LFSR: X^127 + X^63 + 1. Ce nombre d'entrée a un
certain logarithme discret et il est possible de calculer le nombre
qui a comme logarithme discret, celui du nombre d'entrée multiplié par
la clef k modulo (2^n-1) dans ce LFSR et cela sans en connaître le
logarithme discret en question. C'est en fait une exponentiation dans
le corps fini défini par le LFSR. Le vecteur résultat ainsi obtenu
existe également dans la séquence du LFSR: X^127 + X^30 + 1, une et
une seule fois, mais avec un tout autre logarithme discret et peut
également faire l'objet d'une seconde exponentiation dans le second
LFSR. Nous réalisons ainsi un algorithme de chiffrement. On peut bien
retrouver les logarithmes discrets des données et des résultats, on ne
pourra jamais retrouver la clef, car on ne connaît pas la modification
introduite des logarithmes discrets lors du le passage du premier au
second LFSR. On peut estimer à la grande louche que le volume des
calculs de cet algorithme est multiplié en moyenne par 38
(=(127*2*1,5) / 10) par rapport à l'AES à 10 rondes. Les vitesses des
calculs faits en software sont inférieures à celles de l'AES, mais
tout de même acceptables. On suppose ici que tous les bits de la clef
k ont une probabilité de 0.5 de valoir 1 ou 0. En hardware, avec la
réalisation d'un circuit intégré, la vitesse de calcul serait égal e n
moyenne au tiers de la fréquence horloge.

En exécutant une seule exponentiation, il serait relativement facile
de recalculer la clef, mais il en est pas de même dans le cas où il y
a deux exponentiations dans des corps finis différents. Le passage du
logarithme discret du premier LFSR au second introduit là une boite de
substitution formée de 127 bits. Il y a au total 2^n-1 boites
différentes qui sont chacune définie pour une valeur de la clef et
pour une donnée d'entrée. La diffusion au sens donné par Shannon sera
ici acquise avec un résultat optimum. La clef comporte 127 bits et
tous les bits interviennent consécutivement dans les calculs des
exponentiations.

La problématique pour une utilisation intelligente de la
cryptographie nous conduit vers le choix de deux ouvertures. Comme
tout système cryptographique implique le gardiennage des clefs
secrètes, les clefs peuvent être gardées, soit par les utilisateurs
eux-mêmes, c'est la filière RSA avec hébergement des clefs publiques
auprès d'une autorité de certification, soit recourir à un organisme
de confiance tel que le standard ANSI X9.17 qui distribue les clefs de
session. Cette dernière solution ne s'est jamais concrétisée pour
diverses raisons qui sont parfaitement compréhensibles: manque de
crédibilité pour une société privée à pouvoir remplir ce rôle, absence
de logiciels conviviaux, motifs économiques mais surtout la haute
sécurité obtenue avec le RSA. Malgré l'existence des nombreux
algorithmes de chiffrement, même gratuits, 99.99 % des mails ne sont
pas chiffrés.

La mise en place d'un Organisme de Confiance serait la solution du
bon sens, mais il faudra adopter les options suivantes. La charge de
l'Organisme de Confiance devrait être attribuée à un service public.
C'est bien les services publics communaux qui délivrent une identité à
chaque citoyen lors de sa première inscription. Pourquoi ne pourrait-
on pas imaginer que les services publics donnent également le
complément informatique nécessaire liant deux identités et cela
gratuitement? Si les logiciels existaient, le coût des services rendus
serait quasi nuls.

Le crypto-système ClassicSys constitue une première ébauche
expérimentale dans ce sens. Actuellement, le serveur ClassicSys se
trouve dans un local protégé physiquement à l'Université Libre de
Bruxelles. Le logiciel d'affiliation est téléchargeable à l'adresse
http://www.ulb.ac.be/di/scsi/classicsys/experim.htm et fonctionne 24h/
24h.

Dans cette optique, tous les mails envoyés et reçus entre des
affiliés sont chiffrés avec signature électronique. La gestion des
clefs s'exécute automatiquement sans aucune intervention des
utilisateurs. L'Organisme de Confiance peut vérifier la signature
électronique et donner un certificat. La clef particulière secrète
d'un utilisateur est acheminée suivant le protocole Diffie Hellmann.
Je pense que si on doit demander préalablement à l'Organisme de
Confiance une clef de session pour pouvoir communiquer avec un
correspondant, le problème des mails non sollicités serait
définitivement résolu.

Emile

According to Michelot <mhostettler@voila.fr>:

Une question, est-il facile en observant la structure f(X) d'un
polynôme, de déterminer s'il est primitif ou pas ?

Il faut d'abord déterminer s'il est irréductible. Ça ne se voit pas
"à l'oeil" mais c'est algorithmiquement assez aisé. Ensuite, pour
déterminer s'il est primitif, il faut faire quelques exponentiations.
Par exemple, pour n = 11 et un polynôme irréductible, le groupe des
inversibles a pour cardinal 2047. Le groupe engendré par X a un
cardinal qui divise donc 2047 ; c'est donc 2047 lui-même (auquel cas
le polynôme est primitif), ou alors un des diviseurs stricts de 2047,
i.e. 23 et 89.

Du coup, il suffit de calculer X^23 et X^89 modulo le polynôme, pour
voir si ça donne 1 ou pas. Si aucune des deux exponentiations ne donne
1, alors l'ordre de X n'est ni 23, ni 89 ; c'est donc 2047.

Là encore, algorithmiquement, c'est facile, sous réserve d'avoir
une factorisation de 2^n-1 (ce qui n'est pas un vrai problème pour
les n de moins de 150).


Alors à la main, bof. Mais je me suis fait un petit programme pour ça,
il y a quelques temps. Le voilà :


/*
* Enumerate irreducible polynomials in Z2[X].
*
* Compile with DEGREE defined to the required polynomial degree. This
* value must lie between 3 and 20 (inclusive).
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#ifndef DEGREE
#define DEGREE 11
#endif

#define N (DEGREE + 1)

#if N < 4 || N > 20 || (UINT_MAX >> (N - 1)) == 0
#error DEGREE is out of range
#endif

/* ====================================================================== */

/*
* Print a polynomial.
*/
static void
print2(unsigned x)
{
int i, f;

for (i = N - 1, f = 0; i >= 0; i --) {
if (!(x & (1U << i)))
continue;
if (f)
fputs(" + ", stdout);
else
f = 1;
if (i == 0)
putchar('1');
else if (i == 1)
putchar('X');
else
printf("X^%d", i);
}
}

/*
* Get the bit length of the provided number. 0 has bit length 0.
*/
static int
bitlen(unsigned x)
{
int b = 0;

if (x > 0x0000FFFF) { x >>= 16; b += 16; }
if (x > 0x000000FF) { x >>= 8; b += 8; }
if (x > 0x0000000F) { x >>= 4; b += 4; }
if (x > 0x00000003) { x >>= 2; b += 2; }
if (x > 0x00000001) { x >>= 1; b ++; }
if (x > 0x00000000) { b ++; }
return b;
}

/*
* Reduce polynomial a modulo polynomial b.
*/
static unsigned
mod2(unsigned a, unsigned b)
{
int an = bitlen(a), bn = bitlen(b), i;

if (bn > an) {
return a;
}
b <<= an - bn;
for (i = an - bn; i >= 0; i --, b >>= 1) {
if (a & (1U << (i + bn - 1)))
a ^= b;
}
return a;
}

/*
* Compute GCD of two polynomials.
*/
static unsigned
gcd2(unsigned a, unsigned b)
{
while (b != 0) {
unsigned t = mod2(a, b);

a = b;
b = t;
}
return a;
}

/*
* Mutiply polynomial z by X modulo m (of degree mn-1)
*/
static unsigned
mulx2(unsigned z, unsigned m, int mn)
{
z <<= 1;
if (z & (1U << (mn - 1)))
z ^= m;
return z;
}

/*
* Multiply two polynomials modulo m (of degree mn-1)
*/
static unsigned
mul2(unsigned a, unsigned b, unsigned m, int mn)
{
unsigned u = a, v = 0U;
int i, bn = bitlen(b);

for (i = 0; i < bn; i ++) {
if (b & (1U << i))
v ^= u;
u = mulx2(u, m, mn);
}
return v;
}

/*
* Compute a^e modulo m of degree mn-1
*/
static unsigned
pexp2(unsigned a, unsigned e, unsigned m, int mn)
{
unsigned u = a, v = 1U;

while (e > 0) {
if (e & 1U)
v = mul2(v, u, m, mn);
u = mul2(u, u, m, mn);
e >>= 1;
}
return v;
}

/*
* Check whether the provided polynomial is irreducible.
*/
static int
irred2(unsigned f)
{
unsigned u = 2U;
int i, fn;

fn = bitlen(f);
for (i = 0; i < (fn - 1) / 2; i ++) {
u = mul2(u, u, f, fn);
if (gcd2(f, u ^ 2U) != 1U)
return 0;
}
return 1;
}

/*
* These are the prime factors of 2^n-1 for n ranging from 0 to 20
* (without multiplicity).
*/
static unsigned ofactors2[][6] = {
{ 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 },
{ 3, 0, 0, 0, 0, 0 },
{ 7, 0, 0, 0, 0, 0 },
{ 3, 5, 0, 0, 0, 0 },
{ 31, 0, 0, 0, 0, 0 },
{ 3, 7, 0, 0, 0, 0 },
{ 127, 0, 0, 0, 0, 0 },
{ 3, 5, 17, 0, 0, 0 },
{ 7, 73, 0, 0, 0, 0 },
{ 3, 11, 31, 0, 0, 0 },
{ 23, 89, 0, 0, 0, 0 },
{ 3, 5, 7, 13, 0, 0 },
{ 8191, 0, 0, 0, 0, 0 },
{ 3, 43, 127, 0, 0, 0 },
{ 7, 31, 151, 0, 0, 0 },
{ 3, 5, 17, 257, 0, 0 },
{ 131071, 0, 0, 0, 0, 0 },
{ 3, 7, 19, 73, 0, 0 },
{ 524287, 0, 0, 0, 0, 0 },
{ 3, 5, 11, 31, 41, 0 }
};

/*
* Check if f is primitive. This must be called only if f is known
* to be irreducible.
*/
static int
primitive2(unsigned f)
{
int i, fn = bitlen(f);
unsigned go = (1U << (fn - 1)) - 1;

#if 0
if (!irred2(f))
return 0;
#endif
for (i = 0; ofactors2[fn - 1][i] != 0; i ++) {
unsigned e = go / ofactors2[fn - 1][i];

if (e == 1)
continue;
if (pexp2(2U, e, f, fn) == 1U) {
return 0;
}
}
return 1;
}

/* ====================================================================== */

int
main(void)
{
unsigned u;

for (u = 1U << (N - 2); u < (1U << (N - 1)); u ++) {
unsigned p = (u << 1) | 1U;

if (irred2(p)) {
print2(p);
if (primitive2(p))
printf(" (primitive)n");
else
printf("n");
}
}
return 0;
}

Bonjour Thomas,

Excusez-moi, je ne comprends pas cette phrase... je dois être bouché.

Du coup, il suffit de calculer X^23 et X^89 modulo le polynôme, pour
voir si ça donne 1 ou pas. Si aucune des deux exponentiations ne donne
1, alors l'ordre de X n'est ni 23, ni 89 ; c'est donc 2047.

Peut-on SVP l'appliquer simplement au polynôme k(X) qui fait une
période de longueur 23 :

k(X) = X^11 + X^9 + X^7 + X^6 + X^5 + X + 1

X^23 divisé modulo 2 par k(X) donne un reste égal à 1 (mais... votre
phrase ne voudrait pas dire cela !)

Merci,
Michelot