Décalage circulaire

Un décalage circulaire est une opération sur une liste ordonnée (ou n-uplet), consistant à faire passer le dernier élément au début et à décaler tous les autres ; ou à l'inverse, faire passer le premier élément à la fin, et décaler les autres. Cette opération peut être répétée de manière récursive.

Il s'agit donc d'une permutation circulaire particulière, de même longueur que l'ensemble des n éléments sur lequel elle est définie.

Par exemple, si l'on prend la liste (a, b, c) — c'est un triplet —, alors ses décalages circulaires successifs sont :

  • (a, b, c) ;
  • (c, a, b) ;
  • (b, c, a).

De manière générale, si l'on a un n-uplet

(a1, a2, …, an)

alors les décalages circulaires sont obtenus en appliquant l'algorithme récursif suivant :

premier décalage
a 11 = a n
pour 1 < i < n, a 1i+1 = a i
j e décalage (j < n) :
a j1 = a j-1n
pour 1 < i < n, a ji+1 = a j-1i

Utilisation en informatique

En informatique, le décalage circulaire décale tous les bits de l'opérande considéré. Lorsque l'opérande est un ensemble d'octets représentant un nombre, cet opérateur ne conserve pas le signe du nombre ni la mantisse et l'exposant. Contrairement aux registres à décalage, les places laissées vacantes par le décalage ne sont pas laissées vides mais sont remplies par les bits poussés hors de l'opérande.

Le décalage circulaire est souvent utilisé en cryptographie

Exemple

Si la séquence de bits 0110 1111 1010 0011 est soumise à un décalage circulaire de quatre bits vers la gauche, le résultat est 1111 1010 0011 0110

On peut remarquer que le quartet le plus à gauche, 0110, devient le quartet le plus à droite.

Articles connexes