Décalage du registre

Il s'agit d'une récurrence congruentielle affine de rang qui agit sur les bits. Pour un fixé, ce générateur est décrit par le système dynamique avec et défini pour tout par où et sont des constantes binaires. Partant d'une racine ( bits initiaux) on obtient une suite (ou de manière équivalente une suite ) qui est l'orbite émanant de . L'opération de normalisation consiste à isoler des tronçons de taille sur l'orbite des bits et à considérer les premiers bits de chaque tronçon () comme la représentation binaire d'un nombre réel dans . On construit alors la suite avec

On vérifie aisément que l'addition binaire modulo 2 a la même table de vérité que l'opération logique « ou exclusif » notée . Ainsi, supposons que seuls les paramètres , avec , les paramètres restants étant nuls. La récurrence s'écrit alors

Cette écriture permet la programmation -- et même le câblage -- du générateur par décalage du registre avec rétro-action comme le montre l'exemple suivant.

Afin d'optimiser le temps de calcul, les polynômes habituellement utilisés sont de la forme , avec . Ces polynômes sont étudiés et le tableau suivant donne toutes les paires avec qui les rendent primitifs (voir par exemple [#!Gol!#,#!LewGooMil!#,#!ZieBri!#]).

Table: Toutes les paires « primitives » avec .

2	1	18	7,11
3	1,2	20	3,17
4	1,3	21	2,19
5	2,3	22	1,21
6	1,5	23	5,9,14,18
7	1,3,4,6	25	3,7,18,22
9	4,5	28	3,9,13,15,19,25
10	3,7	29	2,27
11	2,9	31	3,6,7,13,18,24,25,28
15	1,4,7,8,11,14	33	11,25
17	3,5,6,11,12,14

Des polynômes (des couples ) de degré plus élevé ont été proposés dans la littérature comme (98,27) [#!LewPay!#], (521,32) [#!BriEni!#], (607,273) [#!TooRobEag!#]. Le générateur associé à ce dernier polynôme a une période de .

La période du générateur n'est évidemment pas la seule caractéristique déterminant sa qualité. Ses propriétés statistiques sont aussi, sinon plus, importantes pour sa validation et celles-ci sont essentiellement déterminées par la constante de décimation . Cette constante est dite propre si pgcd. Ainsi, dans [#!Taw!#] les valeurs , et sont proposées.

Ce générateur à décalage du registre a un intérêt particulier pour la construction de suites de nombres au hasard avec des périodes très longues.