Division dans Z / 2Z

[Trident]

Bonjour à tous. J'aimerais effectuer la division dans (je crois que c'est comme ça qu'on dit ou alors la division modulo 2) de :

par .

Je trouve au finale un quotient égal à : et un reste égal à

Cependant, la correction propose un quotient égal à et un reste de .

Merci par avance de votre réponse.

[Doraki]

Tu veux dire division en base 2 ?

Ben on pose la division comme en CM2 sauf que c'est facile parceque le diviseur rentre soit 0 fois soit 1 fois dans le dividende.

Ou sinon tu fais la division euclidienne et t'écris le résultat en base 2.
11010101 = 213 en décimal, 1011 = 11 en décimal,
213 = 11*19 + 4, donc le quotient est 19 et le reste est 4.
En binaire ça donne bien un quotient de 10011 et un reste de 100

[Trident]

Merci d'avoir répondu, mais non, je parlais pas de la simple division car quand c'est comme ça, je me casse pas trop la tête, je convertis tout en base 10 et je reconvertis quotient + reste en base 2 .

Là, je parlais de la division dans Z / 2 Z , je sais pas quel autre nom on lui donne. C'est une sorte de division utilisée en informatique pour le codage en CRC .

Une personne A veut envoyer des données a une personne B . Elle veut lui envoyer un suite de bits , par exemple 10010 . On associe cette suite de bits à un polynôme à coefficients dans Z / 2Z (soit 0 ou 1 ) , donc ici ça donne : 1 x^4 + 0 x^3 + 0 x^2 + 1 x^1 + 0 x^0 = x^4 + x . Préalablement , A et B se sont mis d'accord sur un polynôme de référence (ou générateur), par exemple x ^3 + x + 1 donc correspondant à la suite de bits suivant : 1011.

Maintenant, l'objectif de A est d'envoyer les données 10010 à B mais elle va pas lui envoyer en clair, elle va utiliser un codage ( pour assurer l'intégrité de l'information, minimiser le risque d'erreurs). Pour cela y'a tout un algorithme qui consiste à multiplier d'abord le polynôme associé à la suite de bit qu'on désire envoyer par x ^d où d représente le degré le plus élevé du polynôme de référence (aussi appelé l'ordre du polynôme) , on obtient donc un nouveau polynôme. On prend la suite de bits associé à ce nouveau polynôme qu'on divise par la suite de bits associée au polynôme de référence. La division n'est pas une simple division binaire , mais c'est une division XOR, faut connaître l’algorithme qui est notamment expliqué ici : http://dvsoft.developpez.com/Articles/CRC/#L4


A la fin, on obtient un reste contenant d-1 bits , on envoie nos données auxquelles on rajoute les d-1 bits. Et la personne B peut vérifier si le message ne contient pas d'erreur...

Bref, y'a une certaine méthode et je suis tombé tout à l'heure sur un site qui proposait des exemples , j'ai essayé de les faire pour m'entraîner mais je vois qu'il effectue une simple division , donc soit il se trompe, ou soit c'est moi qui ne sait pas qu'il faut utiliser une simple division au lieu d'une division XOR. :marteau:

Bref, je vais essayer de demander sur un forum informatique (même si là bas, y'a pas beaucoup de réponses :triste: )

Merci quand même d'avoir répondu

[Doraki]

Tu as l'air de vouloir faire des calculs dans un corps à 2^(d-1) éléments.

F2[X] est un anneau euclidien. Il est muni d'une division euclidienne.
Si on a un polynôme P de F2[X] (F2 = Z/2Z, le corps à 2 éléments), qui est irréductible, alors l'anneau quotient F2[X]/(P) est en fait un corps, qui à 2^(d-1) éléments. (Bon pour ton application en fait on a pas l'air d'en avoir besoin mais généralement on s'arrange pour que le polynôme de référence soit irréductible)

Je pense que tu veux parler de la division euclidienne dans l'anneau F2[X] :
L'image d'un polynôme Q de F2[X] par la surjection canonique dans F2[X]/(P) est le reste de la division euclidienne de Q par P. Il faut l'utiliser pour faire des calculs concrets sur F2[X]/(P), en particulier lorsqu'on doit multiplier deux éléments de F2[X]/(P), on en prend des représentants Q1 et Q2 dans F2[X], on les multiplie, et on regarde le reste du produit dans la division euclidienne par P.

Ensuite, tu as la division dans le corps F2[X]/(P) lorsque P est irréductible, mais j'ai pas l'impression que tu en aies besoin pour l'instant. (dire que le polynôme est générateur dit que la classe de X dans F2[X]/(P) engendre le groupe multiplicatif (F2[X]/(P))*, et donc on obtient un isomorphisme de groupes explicite entre (F2[X]/(P))* et Z/(2^(d-1)-1)Z, ce qui trivialise l'opération de division)

Pour P = x^3+x+1 et Q = x^7 + x^6 + x^4 + x² + 1,
Q = (x^7 + x^5 + x^4) + (x^6 + x^4 + x^3) + (x^5 + x^3 + x²) + (x^4 + x² + x) +(x²+x+1)
= P * (x^4 + x^3 + x² + x) + (x²+x+1), donc ton calcul était juste.

[Trident]

Ah super ! :we:

J'avoue ne pas avoir tout compris (je suis en première année licence, on commence le chapitre sur les anneaux à la rentrée des petites vacances) mais c'est exactement ce que j'essayais de dire.
Merci beaucoup pour la réponse, ça me rassure de savoir que j'avais juste.

[Doraki]

En cryptographie on utilise beaucoup ces corps finis à 2^k éléments, donc faudra passer rapidement sur le chapitre anneaux/polynômes/corps/espace vectoriel à un moment.

Mais bon une fois qu'on est à l'aise avec les opérations concrètes, y'a pas besoin de beaucoup de théorie j'crois.
Faut juste savoir où chercher les références au besoin.