OVH Cloud OVH Cloud

Multiplication in the finite field...

2 réponses
Avatar
godin.v
Bonjour,
Les ann=C3=A9es ont pass=C3=A9es et les quelques souvenirs qui auraient pu =
me
rester des cours de math=C3=A9matiques de mes tendres ann=C3=A9es se sont
=C3=A9vapor=C3=A9s. Non, en fait j'ai toujours =C3=A9t=C3=A9 herm=C3=A9tiqu=
e a l'alg=C3=A8bre
et =C3=A0 l'=C3=A9poque ou l'on m'a demander d'apprendre par coeur les
th=C3=A9or=C3=A8mes sur les corps, les anneaux et les autres ensembles je me
suis consciencieusement bouch=C3=A9 les oreilles : ce qui m'a =C3=A9videmme=
nt
valu de me faire remercier de ma classe pr=C3=A9pa..
Mais je ne vous =C3=A9cris pas pour vous raconter ma vie (qui ne m=C3=A9rite
pas d'attention particuli=C3=A8re de toute fa=C3=A7on) mais juste pour expr=
imer
un regret ! Je nourrissais jusqu'=C3=A0 hier d'un profond respect pour mon
prof de math de l'=C3=A9poque qui semblait r=C3=A9ussir =C3=A0 comprendre c=
e qu'il
d=C3=A9blat=C3=A9rait en cours, et qui surmontait le sentiment de profonde
solitude qu'il ressentait alors qu'il regardait les yeux vides de ses
=C3=A9l=C3=A8ves ! Apr=C3=A8s quatre longues heures d'explication sur les
transformations dans les espaces bi-lin=C3=A9aires il arrivait encore =C3=
=A0
sortir une blague (que lui seul encore comprenait) mais il en riait
grassement.

Bref, c'est hier que j'ai d=C3=A9couverts avec horreur que ce que nous
racontait le bonhomme pouvait avoir une utilit=C3=A9 : " Le con ! il ne
nous a jamais dit que =C3=A7a pouvait servir dans la vraie vie ! " Car
aujourd'hui je dois comprendre ceci :
Example: (over GF(27) with irreducible x7+x+1 for simplicity)
{0,1,0,0,1,1,1} =E2=8A=97 {1,0,0,1,1,1,0}
=3D (x5+x2+x+1)*(x6+x3+x2+x) mod (x7+x+1)
=3D (x11+x5+x3+x) mod (x7+x+1)
=3D x4+x3+x
=3D {0,0,1,1,0,1,0}

et j'ai beau me faire des noeuds au cerveau.. rien n'y fait (note :
merci pour la simplicit=C3=A9).

Un math=C3=A9maticien parmi vous peut-il me diriger vers un ouvrage (en
fran=C3=A7ais, bien que je commence =C3=A0 cerner le sens des abr=C3=A9viat=
ions
math=C3=A9matiques de la langue am=C3=A9ricaine) qui pourrait ouvrir =C3=A0=
un
esprit aussi obtus que le mien les myst=C3=A8re de l'alg=C3=A8bre appliqu=
=C3=A9 =C3=A0
l'univers de l'informatique (et particuli=C3=A8rement de la cryptographie
=C3=A0 l'aide des outils informatiques).

En vous remerciant par avance.

Vincent (Informaticien, mais pas cryptographe)

2 réponses

Avatar
Emile
wrote:

Example: (over GF(27) with irreducible x7+x+1 for simplicity)
{0,1,0,0,1,1,1} ⊗ {1,0,0,1,1,1,0}
= (x5+x2+x+1)*(x6+x3+x2+x) mod (x7+x+1)
= (x11+x5+x3+x) mod (x7+x+1)
= x4+x3+x
= {0,0,1,1,0,1,0}
Vincent (Informaticien, mais pas cryptographe)


Je ne suis pas, à vrai dire, mathématicien. Je me suis cepend ant
intéressé aux corps finis à ma mise à la retraite avec l'invention
de l'algorithme SED en 1987.

Première constatation, il manque les accents circonflexes qui ont
comme utilité de montrer qu'il s'agit bien d'exponentielles. Il faut
lire à la première ligne: (over GF(2^7) with irreducible x^7+x^1+ x^0
for simplicity). On a 2^7= 128. Il y a dans le corps fini 128
éléments composés chacun de 7 bits binaires. A la troisià ¨me ligne,
il faudrait lire x^5+x^2+x^1+x^0 comme premier facteur, ce qui signifie
que le vecteur 0100111 (deuxième ligne) correspond au polynôme qu i a
comme termes les puissances 5, 2, 1 et 0. La multiplication des deux
polynômes est très simple. Chaque terme du polynôme multipli cande
est multiplié par chaque terme du polynôme multiplicateur. Par
exemple, le terme avec l'exposant le plus élevé du résultat x^11
provient de la multiplication de x^5 * x^6 = x^(5+6) = x^11. Lorsqu'il
y a deux termes avec le même exposant, cela donne un terme nul car en
binaire 1+1=0. Le terme x^11 sera supprimé car il est additionnà © avec
(x^7+x^1+x^0) * x^4 = x^11+x^5+x^4 avec le calcul du modulo
(x^7+x^1+x^0). J'ai fait les calculs en détail et le résultat est
bien exact.

Je serai une prochaine fois un peu plus bavard pour expliquer
l'intérèt d'effectuer des multiplications de polynômes dans des
corps finis. Je vous invite à lire l'introduction du papier de
Miecsyzlaw Kula www.ulb.ac.be/di/scsi/classicsys/sedfrob.pdf pour mieux
comprendre les corps finis.

Bonne chance pour faire les calculs en détail.

Emile

Avatar
godin.v
Merci, il me manquait le 1+1=0 ! Avec la méthode je vais m'en sortir
pour faire les calculs. Après, comprendre pourquoi je les fais, c'est
une autre histoire.
A bientôt

Vincent




Je ne suis pas, à vrai dire, mathématicien. Je me suis cependant
intéressé aux corps finis à ma mise à la retraite avec l'invention
de l'algorithme SED en 1987.
(...)
Bonne chance pour faire les calculs en détail.

Emile