Utilisateur:Jérôme Desroziers/Brouillon

Cette page a été fusionnée avec la page Registre à décalage à rétroaction linéaire et n'est plus mise à jour depuis le 17 décembre 2013.

Les registres à décalage à rétroaction linaire, souvent notés par l'acronyme anglophone LFSR venant de Linear Feedback Shift Register dans la littérature scientifique sont exploités depuis longtemps dans les domaines de l'informatique et plus spécialement dans les domaines du codage et de la cryptographie. L’étendue des applications est très large (chiffrement des communications, auto-test des composants électroniques, gestion des erreurs lors des copies de données,...) Bien qu'ils existent sous forme logiciel, c'est la configuration matérielle qui est la plus populaire car c'est une solution simple, peu couteuse et très efficace (un registre à décalage associé à une fonction d'opération logique) Ils sont décrits par des fonctions mathématiques.

Principe[modifier | modifier le code]

Un LFSR est un dispositif dérivé du registre à décalage de type SIPO, Serial In - Parallel Out, dans lequel un ou plusieurs « étages » du registre subissent une transformation pour être réinjectés en entrée de celui-ci^[1].

Il est dit de longueur « $r$ » lorsqu'il est composé de $r$ éléments appelés « étages » ou « cellules », le contenu de l'ensemble de ces éléments à un moment « $t$ » est l'état du LFSR à ce moment^[2]. A chaque top d'horloge le contenu d'un étage est transféré au suivant et le premier est rempli par le résultat d'une fonction linéaire qui prend en compte l'état d'un ou de plusieurs étages^[2].

Exemple[modifier | modifier le code]

LFSR à 4 bits^[3]
Horloge	Etat du LFSR	Sortie
0	`0 1 1 0`	-
1	`1 0 1 1`	`0`
2	`0 1 0 1`	`1`
3	`0 0 1 0`	`1`
4	`0 0 0 1`	`0`
5	`1 0 0 0`	`1`
6	`1 1 0 0`	`0`
7	`0 1 1 0`	`0`

Exemple des états successifs d'un LFSR à 4 bits avec une connexion des bits 1, 2 et 4 au niveau de la fonction de retour :

à $t=0$ l'état initial du LFSR est 0 1 1 0,
à $t=1$ le bit d'entrée vaut 1 $(0\oplus 1\oplus 0)$ , l'état du LFSR est 1 0 1 1 et le bit de sortie vaut 0,
à $t=2$ le bit d'entrée vaut 0 $(1\oplus 0\oplus 1)$ , l'état du LFSR est 0 1 0 1 et le bit de sortie vaut 1,
...
à $t=6$ le bit d'entrée vaut 1 $(1\oplus 0\oplus 0)$ , l'état du LFSR est 1 1 0 0 et le bit de sortie vaut 0,
à $t=7$ le bit d'entrée vaut 1 $(1\oplus 1\oplus 0)$ , l'état du LFSR est 0 1 1 0 et le bit de sortie vaut 0.

Au septième top d'horloge l'état du registre est identique à son état initial. On dit que le LFSR est de période 7^[3].

Modèles mathématiques[modifier | modifier le code]

Conception[modifier | modifier le code]

Un LFSR est défini comme suit sur $\mathbb {F} _{p^{n}}$ ^[4] :

un entier $r$ qui est sa taille
un état initial $S_{r-1}=(a_{0},a_{1},\ldots ,a_{r-1})$ à éléments sur $\mathbb {F} _{p^{n}}$
une fonction linéaire de retour $f()$
on calcul $a_{r}=f(a_{0},a_{1},\ldots ,a_{r-1})$
on fait entrer $a_{r}$ et fait sortir $a_{0}$
on obtient une nouvelle séquence de sortie $S_{r}=(a_{1},a_{2},\ldots ,a_{r})$

Définitions[modifier | modifier le code]

Taille

Si un LFSR a ${r}$ étages alors il est de taille ${r}$ .

Coefficients de connexion

Soit $r$ éléments dans $\mathbb {F} _{p^{n}}$ notés $c_{1},c_{2},...,c_{r}$ . Ils sont appelés les coefficients de connexion du LFSR^[5].

Fonction de retour

${f()}$ est définie par $f(x_{1},x_{2},...,x_{r-1},x_{r})=c_{1}x_{1}+c_{2}x_{2}+...+c_{r-1}x_{r-1}+c_{r}x_{r}$ ^[2].

Séquence

La séquence $a_{i}$ d'un LFSR est l'état des ${r}$ étages à un moment ${t}$ .

Elle satisfait la récursivité suivante : $a_{i}=\sum _{j=1}^{j=r}c_{j}a_{i-j}$ où $i\geqq r$ ^[5].

On peut la trouver aussi écrite sous la forme suivante : $a_{i+n}=\sum _{j=0}^{n-1}c_{i}a_{i+j}$ ^[1].

Triplet

Un LFSR peut être défini comme un triplet ${L}={\Bigl (}\mathbb {F} _{p^{n}},r,(c_{1},c_{2},...,c_{r}){\Bigr )}$ ou ${L}={\Bigl (}\mathbb {F} _{p^{n}},r,f(){\Bigr )}$ ^[5].

Fonction génératrice

L'étude des LFSRs via les série formelle permet de connaître leur fonction génératrice. Elle est définie par $A(X)=\sum _{i=0}^{\infty }a_{i}X^{i}$ sur $\mathbb {F} _{p^{n}}[[X]]$ ^[6]^,^[7].

Remarque : en général on construit les LFSRs sur $\mathbb {F} _{2}=\{0,1\}$ et $f()$ est alors une fonction booléenne.

Représentation polynomiale[modifier | modifier le code]

Polynôme de rétroaction

Soit un LFSR ${L}$ défini par le triplet ${\Bigl (}\mathbb {F} _{p^{n}},r,(c_{1},c_{2},...,c_{r}){\Bigr )}$ . Son polynôme de rétroaction, appelé aussi polynôme caractéristique, est $T(X)=1+\sum _{i=1}^{r}c_{i}X^{i}$ ^[8].

Exemple : Un LFSR ${L}={\Bigl (}\mathbb {F} _{2},7,(1,0,1,1,0,0,1){\Bigr )}$ aura comme polynôme de rétroaction $T(X)=1+X^{7}+X^{4}+X^{3}+X^{1}$ .

Polynôme de connexion

Pour un LFSR défini par le triplet ${L}={\Bigl (}\mathbb {F} _{p^{n}},r,(c_{1},c_{2},...,c_{r}){\Bigr )}$ , le polynôme de connexion est $q(X)=\sum _{i=1}^{r}c_{i}X^{i}-1$ dans $\mathbb {F} _{p^{n}}[[X]]$ ^[6]^,^[7].

Exemple : Un LFSR ${L}={\Bigl (}\mathbb {F} _{2},7,(1,0,1,1,0,0,1){\Bigr )}$ aura comme polynôme de connexion $q(X)=X^{7}+X^{4}+X^{3}+X^{1}-1$ .

Périodicité[modifier | modifier le code]

Puisque la prochaine valeur d'entrée d'un LFSR dépend uniquement des valeurs de certains étages de celui-ci et que l'état « tout à zéro » ne génère jamais de changement sa séquence est de période maximale $q^{r}-1$ sur $\mathbb {F} _{q}$ où ${r}$ est la taille du registre^[9]^,^[10].

Une séquence d'un LFSR sur $\mathbb {F} _{q}$ avec une période $q^{r}-1$ où ${r}$ est la taille du registre est appelé une « m-sequence (en) »^[3]^,^[9].

Exemple : Un LFSR ${L}={\Bigl (}\mathbb {F} _{2},7,(1,0,1,1,0,0,1){\Bigr )}$ aura une période maximale de $2^{7}-1=127$ .

Algorithme de Berlekamp-Massey[modifier | modifier le code]

Introduit en 1969 par James Massey l'algorithme de Berlekamp-Massey (en) permet d'obtenir le plus petit LFSR possible pour une séquence de sortie choisie^[11]. Il suffit de capter ${2}{r}$ bits consécutifs d'une m-séquence de période ${2}^{r}-1$ pour pouvoir reconstruire la séquence entièrement^[12].

Description de l'algorithme^[13] :

En entrée : Les $2n$ éléments d'une séquence récurrente de manière linéaire définie sur $\mathbb {K}$ avec $n\in \mathbb {N}$ donnés par la liste $(a_{0},a_{1},\ldots ,a_{2n-1})$ . Le polynôme minimal est de degré limite $n$ .

En sortie : Le polynôme $P(x)$ caractéristique minimal de la séquence.

Début

Variables locales

R,R_{0},R_{1},V,V_{0},V_{1},Q

sont des polynômes de

x

.

Initialisation

R_{0}:=x^{2n};\quad R_{1}:=\sum _{i=0}^{2n-1}a_{i}x^{i};\quad V_{0}=0;\quad V_{1}=1;

Boucle, tant que

n\leqslant deg(R1)

faire :

Q:=

quotient de la division de

R_{0}

par

R_{1};

R:=

reste de la division de

R_{0}

par

R_{1};

V:=V_{0}-QV_{1}

V_{0}:=V_{1}

V_{1}:=V

R_{0}:=R_{1}

R_{1}=R

Fin boucle

d:=max{\Bigl (}deg(V_{1}),1+deg(R_{1}){\Bigr )};\quad P:=x^{d}V_{1}(1/x);

Retour

P:=P/{\text{leadcoeff}}(P)

.

Fin

Modes de connexion[modifier | modifier le code]

Le mode le plus naturel pour représenter la connexion entre les différents étages du registre est le mode dit de « Fibonacci ». Il est appelé ainsi car la suite de Fibonacci se représente dans ce mode. En 2002 Andy Klapper et Mark GoreskyMark Goresky mettent en place le mode dit de « Galois »^[14]^,^[15].

Fibonacci[modifier | modifier le code]

Un registre en mode Fibonacci applique strictement la définition d'un LFSR : les contenus des différents étages sont ajoutés ou non les uns aux autres, le résultat de cette addition est ensuite placé dans l'étage d'entrée du registre et tous les étages subissent un décalage vers la sortie^[14]^,^[16].

Galois[modifier | modifier le code]

Dans le mode dit de Galois le contenu de l'étage de sortie est ajouté ou non au contenu des étages du registre puis tous les étages subissent un décalage vers la sortie et le contenu de l'étage sortant est réinjecté dans l'étage d'entrée^[17].

Au niveau matériel les LFSRs sont souvent mis en œuvre en utilisant ce mode car celui-ci est plus rapide et présente moins de latence que le mode Fibonacci puisque les étages sont mis à jour simultanément^[18]^,^[19].

Applications[modifier | modifier le code]

Les LFSRS existent sous deux formes: matériel et logiciel, mais c'est surtout la première configuration qui est utilisée car elle est simple à mettre en œuvre (matériel peu onéreux associé à un algorithme de traitement simple). ^[15]

L'usage de cette technologie peut se retrouver dans les domaines suivants : ^[3]

Algorithmes de chiffrement des données
Steganographie
Traitement numérique du signal
Cryptage des réseaux filaire et sans fils
BIST (en) des circuits électroniques
Contrôle d'intégrité des données ou CRC (en)
Compression de données
Générateur de nombres pseudo-aléatoires
Étalement de spectre à séquence directe
Scrambler/DE-scrambler (en)
Compteurs optimisés
Codage/décodage des transmissions des téléphones cellulaires
Codage et décodage des signaux de données numériques
Divers (Jeux vidéos, radars..)

Cryptographie[modifier | modifier le code]

Les LFSR sont utilisés depuis longtemps dans la cryptographie (principalement militaire) car ils sont faciles à mettre en œuvre. Cependant, ce système de type linéaire devient de plus en plus vulnérable et les nouveaux systèmes de cryptage l'utilisant encore sont combinés à d'autres technologies comme les FPGA^[pas clair]^[20]

Les LFSRs sont des candidats naturels de générateur de nombres pseudo-aléatoires qui assurent un chiffrement de flux utilisé par la cryptographie^{[réf. nécessaire]}.

Le registre est initialisé avec une valeur n qui constitue la clé secrète^[évasif]^{[réf. nécessaire]}.

L’inconvénient est que système est facilement cassable, c'est^{[style à revoir]} J.Massey qui a montré que l'algorithme proposé par Berlekamp (décodage BCH) permet aussi de retrouver le polynôme de rétroaction à partir de 2n bits consécutifs^{[réf. nécessaire]}.

Exemples d'algorithmes cryptographique utilisant les LFSRs :

A5/1: Chiffrement des communications GSM, il est basé sur 3 LFSRs de 19,22 et 23 bits
RC4: Chiffrement SSL ou WEP

Contrôle de redondance cycliques[modifier | modifier le code]

Le Contrôle de redondance cyclique que l'on retrouve sous le nom de CRC est un dispositif de contrôle d'erreur lors des transmissions de donnés brutes dans le domaine du réseau, le stockage numérique ou encore dans la compression de donnée.^[21]

Les composants hardware LFSR sont un des moyens facile et bon marché pour generer des suite pseudo-aléatoire utilisées par ces procédés. ^[21]

Il existe plusieurs type de CRC selon les applications: ^[3]

Application	Type	taille LFSR
CRC	CRC-12	12
	CRC-16	16
réseau ATM	CRC-32	32

Auto-test des matériels informatique[modifier | modifier le code]

Le test des circuits électroniques a été longtemps problématique car les solutions existantes donnant des temps de réponses corrects étaient souvent très onéreux. Le coût n'est pas le seul problème, il faut aussi que le dispositif puisse répondre à 2 problématiques :

Le temps

Il ne faut pas que le que le mécanisme consomme trop de temps à générer échantillonnage de test au détriment de l'efficacité du composant

Le volume de donnée

La taille de échantillonnage peut devenir tellement grande que le test n'est plus efficace.^[22]

La technologie Built-in self-test ou BIST est une méthode de test des composants électroniques qui s'appuie sur plusieurs mécanismes :

Technique de parité
Technique de comptage
LFSRs ^[23]

Les tests aléatoires sur une partie du composant suppose de pouvoir agir sur un échantillonnage des données du composant. ^[24]

Compteurs[modifier | modifier le code]

Les compteurs binaires sont à la base de nombreux circuits électroniques. Les LFSRs peuvent être utilisés en remplacement des compteurs binaires traditionnels.^[25] Ils sont beaucoup plus rapide car ils sont une architecture plus simple (bascule synchrone et XOR) et pour les compteurs standards (bascule synchrone, logique de porte et carry chain circuit)

Traitement numérique du signal[modifier | modifier le code]

Télécommunications[modifier | modifier le code]

Les LFSR sont utilisés dans les télécommunications pour certain type de brouilleur

Autres[modifier | modifier le code]

Les suites pseudo-aléatoire générées par les LFSR sont utilisées dans des programmes informatiques (jeux vidéos, graphisme,..)

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

: document utilisé comme source pour la rédaction de cet article.

(en) W. Liang et Jing Long, « A cryptographic algorithm based on Linear Feedback Shift Register », Computer Application and System Modeling (ICCASM), 2010 International Conference on,‎ 22-24 octobre 2010 (DOI 10.1109/ICCASM.2010.5622523)
(en) Bernard Elspas, « The Theory of Autonomous Linear Sequential Networks », Circuit Theory, IRE Transactions on,‎ mars 1959, p. 45-60 (ISSN 0096-2007, DOI 10.1109/TCT.1959.1086506)
(en) N.P. Cagigal et S. Bracho, « Algorithmic determination of linear-feedback in a shift register for pseudorandom binary sequence generation », Electronic Circuits and Systems, IEE Proceedings G,‎ août 1986, p. 191-194 (ISSN 0143-7089, DOI 10.1049/ip-g-1:19860031)
(en) Lauradoux, « From Hardware to Software Synthesis of Linear Feedback Shift Registers », Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International,‎ 26-30 mars 2007, p. 1-8 (DOI 10.1109/IPDPS.2007.370643)
(en) « Optical linear feedback shift register », Lasers and Electro-Optics Europe (CLEO EUROPE/EQEC), 2011 Conference on and 12th European Quantum Electronics Conference,‎ 22-26 mai 2011, p. 1 (ISSN Pending^{[à vérifier : ISSN invalide]}, DOI 10.1109/CLEOE.2011.5942992)
(en) « A multiple seed linear feedback shift register », Computers, IEEE Transactions on,‎ février 1992, p. 250-252 (ISSN 0018-9340, DOI 10.1109/12.123404)
(en) « Linear feedback shift register design using cyclic codes », Computers, IEEE Transactions on,‎ octobre 1988, p. 1302-1306 (ISSN 0018-9340, DOI 10.1109/12.5994)
(en) « Deterministic built-in self-test using multiple linear feedback shift registers for test power and test volume reduction », Computers & Digital Techniques, IET,‎ juillet 2010, p. 317-324 (ISSN 1751-8601, DOI 10.1049/iet-cdt.2009.0092)
(en) « Analysis of the Berlekamp-Massey Linear Feedback Shift-Register Synthesis Algorithm », IBM Journal of Research and Development,‎ mai 1976, p. 204-212 (ISSN 0018-8646, DOI 10.1147/rd.203.0204)
(en) D.G. Maritsas, A.C. Arvillias et A.C. Bounas, « Phase-Shift Analysis of Linear Feedback Shift Register Structures Generating Pseudorandom Sequences », Computers, IEEE Transactions on,‎ juillet 1978, p. 660-669 (ISSN 0018-9340, DOI 10.1109/TC.1978.1675166)
(en) Arvind M Patel, « A multi-channel CRC register », AFIPS '71 (Spring) Proceedings of the May 18-20, 1971, spring joint computer conference,‎ 18 mai 1971, p. 11-14 (DOI 10.1145/1478786.1478789)
(en) J. Lawrence Carter, « The theory of signature testing for VLSI », STOC '82 Proceedings of the fourteenth annual ACM symposium on Theory of computing,‎ 5 mai 1982, p. 66-76 (DOI 10.1145/800070.802178)
(en) W.B. Jone et C.A. Papachristou, « A coordinated approach to partitioning and test pattern generation for pseudoexhaustive testing », DAC '89 Proceedings of the 26th ACM/IEEE Design Automation Conference,‎ juin 1989, p. 525-534 (DOI 10.1145/74382.74470)
(en) Salvatore Filippone, Paolo Santangelo et Marcello Vitaletti, « A vectorized long-period shift-register random number generator », Supercomputing '90: Proceedings of the 1990 ACM/IEEE conference on Supercomputing,‎ octobre 1990, p. 676-684
(en) Li-Ren Huang, Sy-Yen Kuo et Ing-Yi Chen, « A Gauss-elimination based PRPG for combinational circuits », EDTC '95 Proceedings of the 1995 European conference on Design and Test,‎ 6 mars 1995, p. 212
(en) Laurence Goodby et Alex Orailoğlu, « Pseudorandom-pattern test resistance in high-performance DSP datapaths », DAC '96 Proceedings of the 33rd annual Design Automation,‎ juin 1996, p. 813-818 (DOI 10.1145/240518.240671)
(en) D.V. Sarwate, « Mean-square correlation of shift-register sequences », Communications, Radar and Signal Processing, IEE Proceedings F,‎ avril 1984, p. 101-106 (ISSN 0143-7070, DOI 10.1049/ip-f-1:19840018)
(en) Ahmad Zawawi, Bin Seman Kamaruzzaman et Nurzi Juana Mohd Zaizi, « Randomness analysis on grain - 128 stream cipher », International Conference on Mathematical Sciences and Statistics 2013,‎ 5-7 février 2013 (DOI 10.1063/1.4823866)
(en) A. Ahmad, Sameer Al-Busaidi et Ahmed Al-Naamany, Measurement techniques of lfsr sequences, mars 2003.
(en) M. Goresky et A.M. Klapper, « Fibonacci and Galois representations of feedback-with-carry shift registers », Information Theory, IEEE Transactions on,‎ novembre 2002, p. 2826-2836 (ISSN 0018-9448, DOI 10.1109/TIT.2002.804048)
(en) Andreas Klein, « Linear Feedback Shift Registers », Stream Ciphers,‎ 20 avril 2013, p. 17-58 (DOI 10.1007/978-1-4471-5079-4)
(en) J.L. Massey, « Shift-Register Syntheses and BCH Decoding », Information Theory, IEEE Transactions on,‎ janvier 1969, p. 122-127 (ISSN 0018-9448, DOI 10.1109/TIT.1969.1054260)
Anne Canteaut, Attaques de cryptosystèmes à mots de poids faible et construction de fonctions t-résilientes, 10 octobre 1996, 147-167 p. (lire en ligne)
(en) P.H. Bardell et W.H. McAnney, « Pseudorandom Arrays for Built-In Tests », Computers, IEEE Transactions on,‎ juillet 1986, p. 653-658 (ISSN 0018-9340, DOI 10.1109/TC.1986.1676810)
(en) T.K. Moon, « Chapter 4. Cyclic Codes, Rings, and Polynomials », Error Correction Coding: Mathematical Methods and Algorithms,‎ 27 juin 2005, p. 154-170 (DOI 10.1002/0471739219.ch4)
(en) Dai Zongduo et Wan Zhexian, « A relationship between the Berlekamp-Massey and the euclidean algorithms for linear feedback shift register synthesis », Acta Mathematica Sinica,‎ 1^er mars 1988, p. 55-63 (ISSN 1439-8516, DOI 10.1007/BF02560313)
(en) Nadia Ben Atti, Gema M. Diaz–Toca et Henri Lombardi, « The Berlekamp-Massey Algorithm revisited », Applicable Algebra in Engineering, Communication and Computing,‎ avril 2006, p. 75-82 (ISSN 0938-1279, DOI 10.1007/s00200-005-0190-z)
(en) S.B. Gashkov et I.B. Gashkov, « Berlekamp—Massey Algorithm, Continued Fractions, Pade Approximations, and Orthogonal Polynomials », Mathematical Notes,‎ 2006, p. 41-54 (ISSN 0001-4346, DOI 10.1007/s11006-006-0004-z)
(en) Antoine Joux et Pascal Delaunay, « Galois LFSR, Embedded Devices and Side Channel Weaknesses », Progress in Cryptology - INDOCRYPT 2006,‎ 2006, p. 436-451 (ISSN 0302-9743, DOI 10.1007/11941378_31)
Abdelaziz Marjane, Conception Vectorielle de Registre à rétroaction avec retenue sur les corps finis, 8 juillet 2011 (lire en ligne).
(en) J.A. Reeds et J.A. Sloane, « Shift Register Synthesis (Modulo m) », SIAM Journal on Computing,‎ août 1985, p. 505-513 (ISSN 00975397^{[à vérifier : ISSN invalide]}, DOI 10.1137/0214038)
(en) T.N. Rajashekhara, « Signature analyzers in built-in self-test circuits: a perspective », Southern Tier Technical Conference,‎ 25 avril 1990, p. 275-281 (DOI 10.1109/STIER.1990.324654)
(en) M. Koutsoupia, E. Kalligeros et X. Kavousianos, « LFSR-based test-data compression with self-stoppable seeds », Design, Automation & Test in Europe Conference & Exhibition,‎ 20-24 avril 2009, p. 1482-1487 (ISSN 1530-1591, DOI 10.1109/DATE.2009.5090897)
(en) A. Ajane, P.M. Furth et E.E. Johnson, « Comparison of binary and LFSR counters and efficient LFSR decoding algorithm », Circuits and Systems (MWSCAS), 2011 IEEE 54th International Midwest Symposium on,‎ 07/10/2013 août 2011, p. 1548-3746 (ISSN 1548-3746, DOI 10.1109/MWSCAS.2011.6026392)
(en) H Rizk, C Papachristou et F Wolff, « Designing self test programs for embedded DSP cores », Design, Automation and Test in Europe Conference and Exhibition, 2004. Proceedings,‎ 16-20 février 2004, p. 816 - 821 (ISSN 1530-1591, DOI 10.1109/DATE.2004.1268982)
(en) T. Jamil et A. Ahmad, « An investigation into the application of linear feedback shift registers for steganography », SoutheastCon, 2002. Proceedings IEEE,‎ 5 juin 2002, p. 239-244 (DOI 10.1109/.2002.995594)
(en) T Siegenthaler, « Decrypting a Class of Stream Ciphers Using Ciphertext Only », Computers, IEEE Transactions on,‎ janvier 1985, p. 81 - 85 (ISSN 0018-9340, DOI 10.1109/TC.1985.1676518)
(en) J. E. Meggitt, « Error correcting codes and their implementation for data transmission systems », Information Theory, IRE Transactions on,‎ octobre 1961, p. 234-244 (ISSN 0096-1000, DOI 10.1109/TIT.1961.1057659)
(en) R. David, « Testing by Feedback Shift Register », Computers, IEEE Transactions on,‎ juillet 1980, p. 668-673 (ISSN 0018-9340, DOI 10.1109/TC.1980.1675641)
(en) W. Daehn et J. Mucha, « A hardware approach to self-testing of large programmable logic arrays », Circuits and Systems, IEEE Transactions on,‎ novembre 1981, p. 1033-1037 (ISSN 0098-4094, DOI 10.1109/TCS.1981.1084933)
(en) S. Pupolin et Carlo Tomasi, « Moments of the Weights of Pseudo-Noise Subsequences », Military Communications Conference - Progress in Spread Spectrum Communications, 1982. MILCOM 1982. IEEE,‎ 17-20 octobre 1982, p. 15.3-1-15.3-4 (DOI 10.1109/MILCOM.1982.4805920)
(en) T. Siegenthaler, « Decrypting a Class of Stream Ciphers Using Ciphertext Only », Computers, IEEE Transactions on,‎ janvier 1985, p. 81-85 (ISSN 0018-9340, DOI 10.1109/TC.1985.1676518)
(en) E.J. McCluskey, « Built-In Self-Test Techniques », Design & Test of Computers, IEEE,‎ avril 1985, p. 21-28 (ISSN 0740-7475, DOI 10.1109/MDT.1985.294856)
(en) W.G. Chambers, « Clock-controlled shift registers in binary sequence generators », Computers and Digital Techniques, IEE Proceedings E,‎ janvier 1988, p. 17-24 (ISSN 0143-7062)
(en) S. Sastry et M. Breuer, « Detectability of CMOS stuck-open faults using random and pseudorandom test sequences », Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on,‎ setembre 1988, p. 933-946 (ISSN 0278-0070, DOI 10.1109/43.7792)
(en) A. Ahmad, N. Nanda et K. Garg, « The use of irreducible characteristic polynomials in an LFSR based testing of digital circuits », TENCON '89. Fourth IEEE Region 10 International Conference,‎ 22-24 novembre 1989, p. 494-496 (DOI 10.1109/TENCON.1989.176866)

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

Références[modifier | modifier le code]

↑ ^{a et b} Klein 2013, p. 17
↑ ^{a b et c} Cagigal 1986, p. 191
↑ ^{a b c d et e} Ahmad 2003, p. 2
↑ Marjane 2011, p. 80-81
↑ ^{a b et c} Marjane 2011, p. 81
↑ ^{a et b} Klein 2013, p. 19
↑ ^{a et b} Marjane 2011, p. 83
↑ Ahmad 2003, p. 3
↑ ^{a et b} Klein 2013, p. 18
↑ Moon 2005, p. 154
↑ Reeds 1985, p. 505
↑ Marjane 2011, p. 14
↑ Ben Atti 2006, p. 76
↑ ^{a et b} Marjane 2011, p. 22
↑ ^{a et b} Lauradoux 2007, p. 2
↑ Goresky 2002, p. 2827
↑ Goresky 2002, p. 2828
↑ Joux 2006, p. 437
↑ Marjane 2011, p. 152
↑ Liang 2011, p. 1
↑ ^{a et b} PATEL 1971, p. 11
↑ McCluskey 1985, p. 21
↑ McCluskey 1985, p. 25
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées A49p933
↑ Ajane 2011, p. 1

Liens externes[modifier | modifier le code]

[A23p17-1] {a et b} Klein 2013, p. 17

[A3p191-2] {a b et c} Cagigal 1986, p. 191

[A21p2-3] {a b c d et e} Ahmad 2003, p. 2

[A34p8081-4] Marjane 2011, p. 80-81

[A34p81-5] {a b et c} Marjane 2011, p. 81

[A23p19-6] {a et b} Klein 2013, p. 19

[A34p83-7] {a et b} Marjane 2011, p. 83

[A21p3-8] Ahmad 2003, p. 3

[A23p18-9] {a et b} Klein 2013, p. 18

[A29p154-10] Moon 2005, p. 154

[A35p505-11] Reeds 1985, p. 505

[A34p14-12] Marjane 2011, p. 14

[A31p76-13] Ben Atti 2006, p. 76

[A34p22-14] {a et b} Marjane 2011, p. 22

[A4p2-15] {a et b} Lauradoux 2007, p. 2

[A22p2827-16] Goresky 2002, p. 2827

[A22p2828-17] Goresky 2002, p. 2828

[A33p437-18] Joux 2006, p. 437

[A34p152-19] Marjane 2011, p. 152

[A1p1-20] Liang 2011, p. 1

[A12p11-21] {a et b} PATEL 1971, p. 11

[A47p21-22] McCluskey 1985, p. 21

[A47p25-23] McCluskey 1985, p. 25

[A49p933-24] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées A49p933

[A38p1-25] Ajane 2011, p. 1

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

v · m Générateurs de nombres pseudo-aléatoires
Rapide	Générateur congruentiel linéaire Mersenne Twister RANDU
Cryptographiques	Blum Blum Shub Fortuna ISAAC Yarrow
Briques	Congruence sur les entiers Fonction de hachage LFSR