Le XOR

[Kiwazaru]

Dans cet article, j'insisterais fortement sur les mots associativité et commutativité car ce sont deux notions très importante qui rentrent tous deux en compte dans la particularité du XOR; Il est possible que l'article comprenne des erreurs d’inattention ou tout simplement une erreur de compréhension, merci de le faire remarquer pour que cela soit corrigé.

Je vais essayer de détailler les particularités du XOR, et pour cela on va commencer par un exemple:

Code :

Soit un ensemble S ordonnée ou désordonnée de couples (x, x) avec x appartenant à N* et v un entier valant 0, alors si on effectue un XOR sur v pour chaque valeurs contenues dans S on obtient v la valeur qui ne présente aucun couple dans la liste (S) si elle est supérieure à 0 si et seulement si la liste ne présente qu'un seul cas de non-couple.

On a alors l'approche PSEUDO-CODE suivante:

Code PSEUDO :


S ← [10,10,-20,-20,15]
v ← 0
POUR x ALLANT_DE 0 A taille(S) {PAR_PAS_DE 1}
        v ← v ^ S[x]
AFFICHER("Le nombre qui n'a pas de copain est: ", v)
 

En Python cela donne donc:

Code PYTHON :


S = [10,10,-20,-20,15]
v = 0
for x in range(len(S)):
        v ^= S[x]
print "Le nombre qui n'a pas de copain est: " + v
 

Output:

Code :

Le nombre qui n'a pas de copain est: 15

Pour bien apréhender la suite, il faut bien retenir que le XOR n'est pas une opération sur un ensemble de bit, mais bien bit-à-bit alors quelques rappels sur le XOR s'imposent:

Code :

A  |  B  | A ⊕ B
  0  |  0  |   0
  0  |  1  |   1
  1  |  0  |   1
  1  |  1  |   0

On peut donc en déduire les propriétés utiles suivante:

Code :

A ⊕ A = 0 ( 111 ⊕ 111 -> 1 ⊕ 1 ; 1 ⊕ 1 ; 1 ⊕ 1 -> 000 -> 0 )
0 ⊕ B = B ( 000 ⊕ 101 -> 1 ⊕ 0 ; 0 ⊕ 0 ; 1 ⊕ 0 -> 101 )

Ces propriétés vont nous être très utile, on comprendra plus tard pourquoi.

Pour comprendre l'approche mathématique du problème, il faut bien avoir en tête le fait que l'ensemble doit absolument contenir un et un seul non-couple. Ainsi on peut définir la propriété suivante:

Code :

Soit S un ensemble dit contenant des couples, alors si la taille de cet ensemble est pair l'ensemble ne contient que des couples ou contient 2 ou plus non-couples.

Preuve:

Code :

S = [ 20, 30, 20, 30 ]
S est de taille pair, il ne contient que des couples et aucun non couple.

S = [ 20, 20, 40, 30 ]
S est de taille pair, il contient deux non-couples.

S = [ 20, 30, 20, 30, 12 ]
S est de taille impair, il contient 2 couples et un seul non-couple.

S = [ 20, 30, 20, 30, 12, 13, 14 ]
S est de taille impair, il contient 2 couples et 3 non-couples.

On peut donc affirmer que l'ensemble est mal construit si et seulement si sa taille est pair.

Le XOR a des propriétés particulières ce qui lui permet d'être particulièrement intéressant. En effet il est mathématiquement entièrement commutatif et associatif.

Commtuativité:

Code :

A ⊕ B = B ⊕ A
A ⊕ B ⊕ C <=> A ⊕ C ⊕ B
B ⊕ A ⊕ C <=> B ⊕ C ⊕ A
C ⊕ A ⊕ B <=> C ⊕ B ⊕ A

Associativité:

Code :

A ⊕ ( B ⊕ C ) <=> ( A ⊕ B ) ⊕ C
( A ⊕ B ) ⊕ ( C ⊕ D ) <=> A ⊕ ( ( B ⊕ C ) ⊕ D) <=> A ⊕ ( B ⊕ ( C ⊕ D ) ) <=> ( ( A ⊕ B ) ⊕ C ) ⊕ D <=> ( A ⊕ ( B ⊕ C ) ) ⊕ D

La particularité du XOR est que ces deux propriétés sont vraie pour celui-ci. Les exemples le montre, dans le XOR ni l'ordre des bits ni l'ordre des calculs comptent, seul les valeurs se doivent d'être les mêmes pour avoir le bon résultat.
A partir d'ici on commence à se faire une idée du pourquoi du comment l'algorithme fonctionne et pourquoi il a ces propriétés.

Prenons l'exemple ci-dessous:

Code :

S = [ A, A, B, B, C ]
Algorithme => ((((( 0 ⊕ A ) ⊕ A ) ⊕ B ) ⊕ B ) ⊕ C )

On a un ensemble contenant ses couples ordonnés et le non-couple en dernière valeur. Ici on remarque facilement la logique de l'algorithme, en effet il va effectuer ( A xor A ) xor ( B xor B ) = 0 , or on sait que A xor A vaut 0 et que 0 ^ 0 = 0.
Ainsi arrivé à la dernière valeur, nous allons simplement effectuer: 0 xor C, et on sait que 0 xor C = C, on retrouve ainsi notre non-couple à la fin de notre algorithme.

Prenons maintenant ce second exemple:

Code :

S = [ A, B, A, B, C ]
Algorithme => (((( A ⊕ B ) ⊕ A ) ⊕ B ) ⊕ C )

L'ensemble est maintenant désordonnée, il faut donc impérativement que l'opération XOR soit associative et commutative pour que l'algorithme fonctionne sur cette suite.
On remarque que A xor B ne nous donnera pas la même valeur que A auquel le résultat sera XOR ensuite, mais c'est sans compter le fait que le XOR soit associatif et commutatif.
En effet, l'opération: (A xor B) xor A peut s'écrire A xor (B xor A) ou ecore plus simplement de part sa commutativité: (A xor A) xor B. Ainsi la logique est visible => A xor A = 0 et 0 xor B = B.
Ainsi A xor B xor A = B et ce résultat est ensuite XOR par B, B xor B = 0 et 0 xor C = C.
On retombe bien sur nos patte et nous retrouvons bien notre non-couple C.

Prenons maintenant un cas plus concret:

Code :

S = [ A, B, D, C, D, B, A ]
Algorithme => (((((( A ⊕ B ) ⊕ D ) ⊕ C ) ⊕ D ) ⊕ B ) ⊕ A )

Ici notre ensemble est totalement désordonnée, contient un couple de plus et contient le non-couple entre son début et sa fin.
De tête le calcul est moins simple, mais il faut se rappeler que le XOR est commutatif et associatif, c'est à dire que peut importe l'ordre des bits, le résultat sera toujours le même. On peut ainsi représenter le calcul ainsi:

Code :

Algorithme => ( A ⊕ A ) ⊕ ( B ⊕ B ) ⊕ ( D ⊕ D ) ⊕ C

La commutativité nous permet de placer les bits là où ils nous arrangent, et l'associativité nous permet de calculer en priorité ce qui nous arrange.
Ainsi on se retrouve avec une séquence de calcul: A xor A = 0; B xor B = 0; D xor D = 0; 0 xor C = C.
On retombe encore une fois sur nos pattes, ce qui explique que l'algorithme fonctionne même dans une liste totalement désordonnée.

Mais alors que se passe t-il si l'algorithme est utilisée sur un ensemble mal formée ?
Il y a 2 cas:
- Premier cas: L'ensemble ne contient que des couples.

Code :

S = [ A, B, A, B ]
Algorithme => ((( A ⊕ B ) ⊕ A ) ⊕ B ) <=> ( A ⊕ A ) ⊕ ( B ⊕ B ) = 0 ⊕ 0 = 0

Lorsque la liste ne comporte que des couples, le résultat final sera forcément 0. Du fait de l'associativité et la commutativité du XOR, on obtiendra toujours la formule suivante:

Code :

A ⊕ A ⊕ B ⊕ B... ⊕ N ⊕ N  <=> 0 ⊕ 0... ⊕ 0

Dans cette formule, N est la dernière valeur qui sera XORée. Ainsi nous retrouvons toujours la suite: 0 xor 0... xor 0, c'est pour cela que l'algorithme ne fonctionne que sur des entiers dans N*, car si le non-couple choisi est 0, alors l'algorithme ne peut pas savoir si 0 signifie "Aucun résultat" ou signifie "Le non-couple est 0".

- Second cas: L'ensemble comporte 2 ou plus non-couples.

Code :

S = [ A, B, C, A, X, B, C, Z, Y ]
Algorithme => (((((((( A ⊕ B ) ⊕ C ) ⊕ A ) ⊕ X ) ⊕ B ) ⊕ C ) ⊕ Z ) ⊕ Y )
<=> ( A ⊕ A ) ⊕ ( B ⊕ B ) ⊕ ( C ⊕ C ) ⊕ X ⊕ Y ⊕ Z
<=> 0 ⊕ 0 ⊕ 0 ⊕ X ⊕ Y ⊕ Z
<=> 0 ⊕ ( X ⊕ Y ⊕ Z )
<=> X ⊕ Y ⊕ Z

Dans ce cas précis, le résultat est aussi très logique, et encore une fois grâce à l'associativité et la commutativité du XOR.
On replace correctement nos bits afin de retrouver une séquence de calcul valant: 0 xor 0 xor 0... puis nous mettons à la fin nos non-couples.
Soit NC l'ensemble des non-couples de l'ensemble S de taille supérieur à 1, alors on se retrouve avec la séquence de calcul suivante: 0 xor 0... xor NC[0]... xor NC[n].
Finalement cela revient à dire que pour tout ensemble S, si cet ensemble contient plus d'un non-couple le résultat sera équivalent au résultat du XOR de chacun de ceux-ci entre eux.

L'associativité et la commutativité du XOR peut aussi être aperçu dans l'opération qui permute deux variable.

Soient x, y deux variable alors:

Code :

x = x ⊕ y
y = y ⊕ x
x = x ⊕ y

x = y
y = x

Développons maintenant cette suite de calcul, à chaque calcul x et y changent de valeur autrement dit:

Code :

x = x ⊕ y
y = y ⊕ ( x ⊕ y )
x = ( x ⊕ y ) ⊕ ( y ⊕ ( x ⊕ y ) )
<=>
x = x ⊕ y
y = ( y ⊕ y ) ⊕ x <=> y = 0 ⊕ x <=> y = x
x = ( x ⊕ x ) ⊕ ( y ⊕ y ) ⊕ y <=> x = 0 ⊕ 0 ⊕ y = x = y

On voit bien que grâce à la commutativité et l'associativité de l'opération XOR, il est possible de passer de x -> y et de y -> x facilement puisque nous pouvons arranger l'ordre des bits facilement et modifier l'ordre des calculs.
On peut donc en déduire que cette opération de swap est totalement reversible.

Mais alors pourquoi est-ce que le XOR est associatif et commutatif, et pourquoi est-ce que cela lui donne une telle particularité? Et bien en fait, il faut savoir qu'il n'y a pas seulement le XOR qui est entièrement associatif et commutatif, l'opération AND et OR le sont tous deux aussi.
La spécificité du XOR réside dans sa table de vérité mêlée à la commutativité et à l'associativité.

Ci-dessous, la preuve de l'associativité et la commutativité de chacun de ces opérateurs (AND/OR/XOR):

Code :

AND:
( x & y ) & z = x & ( y & z ) ?
( 0 & 1 ) & 1 = 0 & ( 1 & 1 ) Vrai

x & y = y & x ?
1 & 0 = 0 & 1 Vrai

OR:
( x | y ) | z = x | ( y | z ) ?
( 0 | 1 ) | 1 = 0 | ( 1 | 1 ) Vrai

x | y = y | x ?
1 | 0 = 0 | 1 Vrai

XOR:
( x ^ y ) ^ z = x ^ ( y ^ z ) ?
( 0 ^ 1 ) ^ 1 = 0 ^ ( 1 ^ 1 ) Vrai

x ^ y = y ^ x ?
1 ^ 0 = 0 ^ 1 Vrai

Alors qu'est-ce qui rend si utile le XOR? Comme précisé, sa spécificité réside particulièrement dans sa table de vérité qui engendre des cas utiles avec son associativité et sa commutativité.
La ligne importante de la table de vérité est la suivante: 1 ⊕ 1 = 0; C'est grâce à cette propriété logique du XOR qu'il est possible de faire tant de chose avec.
Effectivement, on a vu dans nos calcul que l'associativité nous permettait d'ordonner nos calculs, mais ceci ne serait pas utile dans notre algorithme si on ne pouvais pas obtenir un calcul donnant un résultat nul ensuite (0).
C'est grâce à cela que nous pouvons ensuite obtenir un calcul équivalent à: 0 xor A = A, qui nous permet par exemple de ressortir le non-couple d'un ensemble de couples.
C'est pour cela qu'il est important de connaître les deux propriétés du XOR rappelées ci-dessus ( A xor A = 0; 0 xor B = B ).
Plus de précisions:
La table de vérité du XOR nous permet d'annuler deux valeurs identiques, par exemple A et A puisque la table indique que pour tout bit à 1 XORée à un autre bit à 1, le résultat est 0, et que pour tout bit 0 XORée à un autre bit à 0 le résultat est 0.
Ainsi on obtient l'annulation totale d'une suite de bit XORée elle-même.
Trace de l'opération A xor A avec A = 5:

Code :

101 ⊕ 101
On effectue l'opération de bit en bit:
1 ⊕ 1 = 0
0 ⊕ 0 = 0
1 ⊕ 1 = 0
---------
      = 000

La table de vérité nous permet aussi d'obtenir A si A est XORée par 0 grâce au fait que 0 xor 1 = 1 et 1 xor 0 = 1, car dans le cas contraire l'utilité du XOR perdrait tout son sens.
Ainsi, on peut obtenir une suite de XOR valant 0 XORée elle-même par une valeur A qui retourne A.
Trace de l'opération 0 xor A = A avec A = 5:

Code :

000 ⊕ 101
On effectue l'opération de bit en bit:
0 ⊕ 1 = 1
0 ⊕ 0 = 0
0 ⊕ 1 = 1
---------
      = 101 = A

L'opération OR vérifie la même propriété que 0 xor A = A mais pas celle de A xor A = 0, tandis que AND ne vérifie aucune des deux propriétés du XOR.

Code :

Propriété: A xor A = 0
101 & 101

1 & 1 = 1
0 & 0 = 0
1 & 1 = 1
Non vérifié

101 | 101

1 | 1 = 1
0 | 0 = 0
1 | 1 = 1
Non vérifié

Propriété: 0 xor A = A
000 & 101

0 & 1 = 0
0 & 0 = 0
0 & 1 = 0
Non vérifié

000 | 101

0 | 1 = 1
0 | 0 = 0
0 | 1 = 1
Vérifié

Pour finir, nous allons démontrer une astuce connue avec le XOR:

Code :

plaintext ⊕ key = ciphertext
plaintext ⊕ ciphertext = key
key ⊕ ciphertext = plaintext

Si vous voulez vérifier que vous avez bien compris je vous laisse démontrer ça tout seul, je met la solution en spoiler.
[spoiler]

Code :

A ⊕ B = C
B ⊕ C = A <=> B ⊕ ( A ⊕ B ) = ( B ⊕ B ) ⊕ A = 0 ⊕ A = A
C ⊕ A = B <=> ( A ⊕ B ) ⊕ A = ( A ⊕ A ) ⊕ B = 0 ⊕ B = B

Soient "1337" le plaintext et "pleb" la key, alors:
[code]
1337 <=> 49 51 51 55 <=> 0011 0001 (1) 0011 0011 (3) 0011 0011 (3) 0011 0111 (7)
pleb <=> 112 108 101 98 <=> 0111 0000 (p) 0110 1100 (l) 0110 0101 (e) 0110 0010 (b)

On sait que le XOR est une opération bit-à-bit, donc on effectue le XOR octet par octet, et bit par bit de ces octets.
1 ^ p
0011 0001 ^ 0111 0000 <=> 0100 0001
3 ^ l
0011 0011 ^ 0110 1100 <=> 0101 1111
3 ^ e
0011 0011 ^ 0110 0101 <=> 0101 0110
7 ^ b
0011 0111 ^ 0110 0010 <=> 0101 0101

Ainsi, notre ciphertext mis en ASCII vaut: 65 95 86 85 soit: A_VU

Dans le cas où nous connaissons le plaintext et le ciphertext ( A et C ) alors prouver que: plaintext ⊕ ciphertext = key

plaintext                         =  0011 0001 0011 0011 0011 0011 0011 0111
ciphertext                       =  0100 0001 0101 1111 0101 0110 0101 0101
plaintext ⊕ ciphertext       =  0111 0000 0110 1100 0110 0101 0110 0010
key                               =  0111 0000 0110 1100 0110 0101 0110 0010

plaintext ⊕ ciphertext <=> key

Dans le cas où nous connaissons la key et le ciphertext ( B et C ) alors prouver que: key ⊕ ciphertext = plaintext

key                              =  0111 0000 0110 1100 0110 0101 0110 0010
ciphertext                     =  0100 0001 0101 1111 0101 0110 0101 0101
key ⊕ ciphertext            =  0011 0001 0011 0011 0011 0011 0011 0111
plaintext                       =  0011 0001 0011 0011 0011 0011 0011 0111

key ⊕ ciphertext <=> plaintext

[/spoiler]

[supersnail]

Sympa ton petit post, cependant quelques petites remarques:

• Premièrement, je ne pense pas que le pseudo-code soit réellement utile ici; et il serait à mon sens plus avantageux de reformuler de manière moins "formelle" l'énoncé du problème.
  
• Les fautes d'accord sacrebleu ! (on parle d'ensemble désordonné, pas désordonnée :þ)
  
• Ensuite une fois que tu as dit que le xor était associatif, pas besoin d'alourdir tes notations avec les parenthèses qui ne servent plus trop ici
  

Bref essaie de structurer un peu mieux ton propos pour faciliter la compréhension du papier

Sinon, pour rajouter quelques précisions, on peut dire aussi que l'opérateur XOR est l'addition modulo 2 sur les entiers (qui forme un groupe additif qu'on note Z/2Z d'élément neutre 0) si on veut avoir une vision algébrique de la chose et pas trop s'enquiquinner avec des tables de vérité :o)).

[b0fh]

Quelques remarques sur le langage mathématique:

Soit un ensemble S ordonnée ou désordonnée de couples (x, x) avec x appartenant à N*

A ce stade, on s'imagine un ensemble

Code :

S = { (1,1), (2,2), (4,4), (8,8), ... }

ce qui est un objet différent de

Code :

S = { 1, 1, 2, 2, 4, 4, 8, 8, ... }

qui n'est pas un ensemble (un ensemble ne peut pas contenir deux fois le même objet.) On peut parler de multiensemble.

et v un entier valant 0

Si v vaut 0, on ne l'appelle pas v, on l'appelle 0 !

alors si on effectue un XOR sur v pour chaque valeurs contenues dans S on obtient v

On comprend ça comme:

Code :

{ x XOR v | x ∈ S } = {v}

Ce qui n'a aucun sens,

la valeur qui ne présente aucun couple dans la liste (S) si elle est supérieure à 0 si et seulement si la liste ne présente qu'un seul cas de non-couple.

Aaaah, S est une liste, pas un ensemble. Mais la liste contient des couples, pas des valeurs, et pourquoi parle-on soudainement de non-couples ?

La formulation correcte du problème serait:

Soit S un multiensemble supporté par N*, dans lequel il existe exactement un élément x de multiplicité impaire. Soit v le produit des éléments de S par l'opération XOR; alors v = x.

Enfin, a propos des itérateurs. On n'écrit pas:

Code PYTHON :

for x in range(len(S)):
    v ^= S[x]

on écrit:

Code PYTHON :

for s in S:
    v ^= s

(Et par convention on réserve les majuscules pour les types de classe)