Générateurs Pseudo-Aléatoires à Base De Registres Filtrés

Générateurs Pseudo-Aléatoires à Base De Registres Filtrés

la plupart des générateurs pseudo-aléatoires sont construits en utilisant les registres filtrés.En effet ces registres sont faciles à implémenter mais également économique dans leur mise en oeuvre matériel.Raisons pour laquelle on les utilise dans les chiffrements par flot mais aussi par bloc.Pour mieux illustrer cette partie du mémoire nous :manipulerons et étudierons les propriétés des LFSR.mais également mettrons au point des algorithmes pour retrouver le plus petit LFSR générant une suite de bits donnée.

Régistre à Décalage à Rétroaction Linéaire

Cette approche qui a été introduite en 1959 par Niezereiter nous a permis de décrire le dévelop- pement en série formelle de la séquence (a) sous forme d’une fraction rationnelle et ceci grâce à l’intervention du polynôme de rétroaction ci-dessous : 1) ; donc cette suite est périodique. Puisque la sécurité des LFSR dépend de la complexité linéaire, nous allons maintenant nous intéresser à la plus petite relation de récurrence permettant de reproduire la séquence(aDéfinition 3.1.3. Soit A un anneau commutatif intègre.On appelle série formelle( ou série génératrice) sur A toute expression symbolique .

La procédure InitGenArbre(n) s’exécute en temps constants. Prendre aléatoirement un élément dans un ensemble se fait aussi en temps constants. Dans chaque itération, AjoutArete(T, v, d) s’exécute en O(d). CommePour montrer que l’algorithme est vrai, on garde le même invariant de boucle : »À chaque itération, le sous-arbre constitué par lL’initialisation est la même que celle dans la section précédente. La différence est que dans chaque itération, le nombre d est pris aléatoirement un par un dans le multi- ensemble M set. Comme la somme des éléments de M set vaut n − 2, au final, on a’ensemble des sommets ConstSat ∪ Leaf.

Précédemment, on a vu comment générer une forêt d’arbres sans point isolé. Dans notre cas, il est probable que la forêt générée admet quelques sommets isolés. Cela doit toujours se faire de manière uniforme. Une composante de la forêt est soit un arbre à degré contraint, soit un sommet isolé. Pour une forêt quelconque d’ordre n avec m arêtes, on a toujours k = n − m composantes connexes. Pour une composante connexe= 0. La forêt à degré contraint existe alors s’il existe k.

Génération aléatoire de graphes à degré contraint quel- conque

Après avoir construit une forêt à degré contraint, construisons maintenant un graphe. Supposons que |D| ≥ 2 et D ⊂ {1, 2, · · · , n − 1}.Pour construire le graphe, on part d’un graphe avec un nombre minimum d’arêtes dont les degrés des sommets sont aussi minimaux. Puis, itérativement, on rajoute une ou plusieurs arêtes au graphe de tel sorte que le graphe conserve la contrainte à chaque itération.Étant donné un graphe G = (V, E) à degré contraint D, un sommet v du graphe G tel que deg(v) < ∆, on souhaite rajouter des arêtes au graphe en augmentant le degré de v. On prend un entier d ∈ D tel que deg(v) < d ≤ ∆. Il y a deux cas possibles, soit, l’application de ce procédure k fois à un sommet v augmente le degré de v de 2k et rajoute k arêtes au graphe. On note AugDeg(G, v, k) la fonction qui exécute, si possible, k fois la procédure. Dans le cas contraire, AugDeg(G, v, k) ne modifie pas l’état du graphe.

Génération aléatoire de graphes à degré contraint quelconque Initialisation du graphe

En général, si min(D)n est pair, on génère un graphe min(D)-régulier. Sinon,on génère un graphe min(D)-régulier d’ordre n − 1 sur un sous-ensemble de cardi-nimum dont les degrés des sommets sont dans D. Appelons InitGenGraphe(n, m, D) cette procédure. On remarque que si tous les éléments de D et n sont impairs alors l’initialisation est impossible.Après l’initialisation, il ne reste plus qu’à rajouter des arêtes au graphe. On prend donc un degré d tel que le changement de degré d’un sommet v à d rajoute au plus m − |E| arêtes, qui est le nombre d’arêtes restantes .