--- /dev/null
+\theograyequilibre*
+
+
+
+
+\begin{proof}
+La preuve de ce théorème s'effectue par induction sur $\mathsf{N}$.
+On peut vérifier aisément que ce théorème est établi pour les
+deux plus petites valeurs paires et impaires, \textit{i.e.} pour
+$\mathsf{N}=3$ et $\mathsf{N}=4$.
+
+Pour le cas initial où $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$
+on a: $S_1=1,1$, $l=2$, $u_0 = \emptyset$ et $v=\emptyset$.
+Ainsi, l'algorithme produit
+$U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$ et $W' = 1,2,1,3$.
+Finalement, $S_3=1,2,1,3,1,2,1,3$ qui vérifie le théorème.
+
+Pour le cas initial où $\mathsf{N}=4$, \textit{i.e.} $\mathsf{N-2}=2$
+on a: $S_1=1,2,1,2$, $l=4$,
+$u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$ et $v=\emptyset$.
+Ainsi, l'algorithme produit
+$U= 1,3,2,3,4,1,4,3,2$, $V = 4$, $W= 3, 1, 2, 1,2, 4$ et $W' = 1, 3, 2, 1,2, 4 $.
+Finalement, $S_4 = 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$ et le code est
+totalement équilibré.
+
+Pour le cas inductif, on définit tout d'abord quelques variables.
+Soit $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) le nombre d'éléments dont le nombre
+de transitions est exactement $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
+Ces deux variables sont caractérisées par le système:
+
+\[
+\left\{
+\begin{array}{lcl}
+c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\
+c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}}
+\end{array}
+\right.
+\Leftrightarrow
+\left\{
+\begin{array}{lcl}
+d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\
+c_{\mathsf{N}} &= &\mathsf{N} - d_{\mathsf{N}}
+\end{array}
+\right.
+\]
+
+Puisque $a_{\mathsf{N}}$ est pair, $d_{\mathsf{N}}$ est un entier.
+Prouvons d'abord que $c_{\mathsf{N}}$ et $d_{\mathsf{N}}$ sont des entiers
+positifs.
+Soit $q_{\mathsf{N}}$ et $r_{\mathsf{N}}$, définis respectivement
+comme étant le quotient et le reste dans la division euclidienne de
+$2^{\mathsf{N}}$ par $2\mathsf{N}$, \textit{i.e.}
+$2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, avec $0 \le r_{\mathsf{N}} <2\mathsf{N}$.
+Tout d'abord, l'entier $r$ est pair puisque $r_{\mathsf{N}}$ est un multiple de 2:
+$ r_{\mathsf{N}}= 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$.
+Ensuite, $a_{\mathsf{N}}$ vaut $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$.
+Ainsi
+$d_{\mathsf{N}}$ vaut $r_{\mathsf{N}}/2$ est est donc un entier positif tel que
+$0 \le d_{\mathsf{N}} <\mathsf{N}$.
+La preuve pour $c_{\mathsf{N}}$ est évidente.
+
+
+Pour chaque $i$, $1 \le i \le \mathsf{N}$, soit $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ et $bi_{\mathsf{N}}$) le nombre d'occurrences de l'élément
+$i$ dans la séquence $u_0, \dots, u_{l-2}$
+(resp. dans les séquences $s_{i_1}, \dots , s_{i_l}$ et $v$)
+à l'étape (\ref{item:nondet}) de l'algorithme.
+
+En raison de la définition de $u'$ à l'étape~(\ref{item:u'}),
+$3.zi_{\mathsf{N}} + ti_{\mathsf{N}}$ est le nombre
+ d'occurrences de $i$ dans la séquence $U$.
+Il est évident que le nombre d'occurrences de $i$ dans la séquence $V$ est
+$2bi_{\mathsf{N}}$ en raison de l'étape (\ref{item:VW}).
+On a ainsi le système suivant:
+$$
+\left\{
+\begin{array}{lcl}
+3.zi_{\mathsf{N}} + ti_{\mathsf{N}} + 2.bi_{\mathsf{N}} + \textit{TC}_{\mathsf{N}-2}(i) &= &\textit{TC}_{\mathsf{N}}(i) \\
+zi_{\mathsf{N}} + ti_{\mathsf{N}} + bi_{\mathsf{N}} & =& \textit{TC}_{\mathsf{N}-2}(i)
+\end{array}
+\right.
+\qquad
+\Leftrightarrow
+$$
+
+\begin{equation}
+\left\{
+\begin{array}{lcl}
+zi_{\mathsf{N}} &= &
+\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) - bi_{\mathsf{N}}}{2}\\
+ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}-bi_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:sys:zt1}
+\end{equation}
+
+Dans ce système de 2 équations à trois inconnues, on pose $b_i=0$.
+Puisque $\textit{TC}_{\mathsf{N}}$ est pair (égal à $a_{\mathsf{N}}$
+ou à $a_{\mathsf{N}}+2$), l'inconnue $zi_{\mathsf{N}}$ est donc un entier.
+Prouvons alors que le système résultant admet toujours
+une solution positive pour $z_i$ et pour $t_i$ telle $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$ et telle que leur somme est égale à
+ $\textit{TC}_{\mathsf{N}-2}(i)$.
+On remarque que cette contrainte est toujours établie si le système admet une solution. On a donc le système suivant:
+
+
+
+\begin{equation}
+\left\{
+\begin{array}{lcl}
+zi_{\mathsf{N}} &= &
+\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) }{2}\\
+ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:sys:zt2}
+\end{equation}
+
+La définition de $\textit{TC}_{\mathsf{N}}(i)$ dépend de la valeur de $\mathsf{N}$. Pour $3 \le N \le 7$, on définit celles-ci comme suit:
+
+\begin{eqnarray*}
+\textit{TC}_{3} & = & [2,2,4] \\
+\textit{TC}_{5} & = & [6,6,8,6,6] \\
+\textit{TC}_{7} & = & [18,18,20,18,18,18,18] \\
+\\
+\textit{TC}_{4} & = & [4,4,4,4] \\
+\textit{TC}_{6} & = & [10,10,10,10,12,12] \\
+\end{eqnarray*}
+Il n'est pas difficile de vérifier que dans chacun des cas précédents,
+le système admet bien une solution.
+
+Pour $N \ge 8$, on définit $\textit{TC}_{\mathsf{N}}(i)$ comme suit:
+\begin{equation}
+\textit{TC}_{\mathsf{N}}(i) = \left\{
+\begin{array}{l}
+a_{\mathsf{N}} \textrm{ si } 1 \le i \le c_{\mathsf{N}} \\
+a_{\mathsf{N}}+2 \textrm{ si } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:TCN:def}
+\end{equation}
+
+
+On a ainsi
+\[
+\begin{array}{rcl}
+\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)
+&\ge&
+a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\
+&\ge&
+\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}
+-2 \left( \frac{2^{\mathsf{N-2}}-r_{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
+&\ge&
+\frac{2^{\mathsf{N}}-2N}{\mathsf{N}}
+-2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
+&\ge&
+\frac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
+\end{array}
+\]
+
+Une simple étude de variation de la fonction $t:\R \rightarrow \R$ telle que
+$x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ montre que
+sa dérivée est strictement positive pour $x \ge 6$ et que $t(8)=224$.
+L'entier $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ est ainsi positif pour chaque $\mathsf{N} \ge 8$, ce qui termine la preuve.
+\end{proof}
--- /dev/null
+
+\subsection{Synthèses des contributions}
+
+Les principales contributions gravitent autour des mathématiques discrètes et plus particulièrement
+les itérations de systèmes dynamiques discrets.
+
+Pour chacun des modes et des conditions de synchronisme,
+il existe des critères (suffisants) de convergence
+globale ou locale.
+
+Nous avons formalisé le mode des
+\emph{itérations mixtes} (introduit par Pr. J. M. Bahi en 2005 notamment)
+qui combine synchronisme et asynchronisme (chapitre~\ref{chap:sdd})
+et leur extension les \emph{itérations mixtes avec délais uniformes}.
+Nous avons pu ainsi énoncer puis démontrer des résultats
+établissant que pour des conditions classiques de convergence des itérations
+synchrones, les itérations mixtes à délai uniforme
+convergent aussi vers le même point fixe.
+
+Nous avons de plus démontré (chapitre~\ref{chap:promela}) qu'on peut simuler
+des SDDs selon tous les modes avec l'outil SPIN de \emph{Model-Checking} pour établir
+formellement leur convergence (ou pas).
+Nous avons énoncé puis prouvé ensuite la correction et la complétude de la démarche.
+Des données pratiques comme la complexité et des synthèses d'expérimentation
+ont aussi été fournies.
+
+Nous nous sommes ensuite intéressés à l'étude du problème dual
+de l'étude de divergence d'un SDD.
+Nous avons proposé plusieurs méthodes de construction de
+fonctions permettant d'obtenir des itérations chaotiques.
+La première non naïve est basée sur des
+conditions suffisantes sur le graphe d'interaction à $\mathsf{N}$ sommets
+(chapitre~\ref{chap:carachaos}).
+Une seconde méthode plus efficace permet en plus de disposer d'une chaîne de Markov doublement
+stochastique et s'appuie sur les cycles hamiltoniens du graphe des
+itérations. Elle est présentée au chapitre~\ref{chap:PRNG:gray}.
+Ces méthodes ont permis d'étendre à l'infini la classe des fonctions
+dont les itérations sont chaotiques.
+
+Nous de plus entrepris d'étudier ces itérations et plus particulièrement leur
+apprentissage par un réseau de neurones.
+Nous avons notamment pu contribuer à montrer pratiquement qu'il
+est très difficile (voir impossible) de les prédire
+à l'aide d'outils d'intelligence artificielle (chapitre~\ref{chp:ANN}).
+
+Avec la production d'une grande collection de fonctions à itérations chaotiques,
+Nous avons donc proposé de répondre à la question suivante: comment engendrer des fonctions
+dont les itérations vont produire des nombres simulant correctement l'aléa.
+En d'autres termes, quelles fonctions peuvent être embarquées dans un PRNG?
+Nous avons d'abord caractérisé les fonctions dont les itérations produisent des nombres
+selon une distribution uniforme (chapitre~\ref{chap:PRNG:chao}). Pour cela il a fallu réécrire
+l'algorithme de génération comme une marche aléatoire dans une partie du $\mathsf{N}$-cube,
+de se ramener à une chaîne de Markov puis d'utiliser la théorie élaborée sur ce sujet
+pour conclure (chapitre~\ref{chap:PRNG:gray}).
+
+Parmi les fonctions retenues, celles issues de la suppression
+d'un cycle hamiltonien dans un $\mathsf{N}$ ont retenu notre attention.
+Nous nous sommes aussi attaché à montrer l'importance de l'équilibrage du cycle
+hamiltonien à enlever (chapitre~\ref{chap:PRNG:gray}).
+Nous avons de plus entrepris dans ce chapitre
+de trouver un majorant du nombre d'itérations suffisant à
+l'obtention d'une distribution uniforme
+
+Nous avons renforcé la thématique de marquage de document numérique de l'équipe AND en
+embarquant ces fonctions dans des outils de watermarking.
+Nous avons participé à la formalisation de la méthode de
+marquage de médias (chapitre~\ref{chap:watermarking}) et particularisé
+ceci à des images numériques fournissant un
+nouveau contexte pour l'étude théorique et mathématique d'algorithmes de marquage.
+Des instances de ces algorithmes ont été présentées en sélectionnant de manière
+pertinente les fonctions à itérer pour garantir une robustesse
+élevée.
+
+D'autre méthodes de watermarking ont été investies (mais plus dans le domaine discret),
+particulièrement celles basées sur la Quantization Index Modulation (QIM), méthodes
+étant supposées comme les plus robustes. Nos principales contributions
+sur ce travail ont été
+d'intégrer ceci à du marquage de document PDF puis de
+présenter ce problème comme un problème d'optimisation (chapitre~\ref{chap:watermarking:pdf}).
+
+Nous avons de plus conçu l'algorithme STABYLO (chapitre~\ref{chap:stabylo})
+qui est un schéma de stéganographie basé sur l'enfouissement de l'information dans les contours
+présents dans une image. Cet algorithme présente un bon compromis entre sécurité
+fournie et complexité algorithmique.
+Nous avons enfin proposé d'exprimer les fonctions de distorsion classiquement utilisées en stéganographie
+comme des méthodes de calcul de gradient
+ou de matrice Hessienne. Grâce à l'étude de ces matrices, nous avons proposé un nouveau schéma de
+stéganographie sécurisé (chapitre~\ref{chap:th:yousra}).
+
+\subsection{Quelques perspectives}
+
+\subsubsection{Étendons les PRNGs}
+La démarche actuelle de génération de nombres pseudo-aléatoires
+consiste à marcher dans une partie d'un $\mathsf{N}$-cube en choisissant son chemin
+à l'aide d'un générateur fourni en entrée. Or ces générateurs sont tous des
+fonctions de $\{0,1\}^{\mathsf{N}}$ dans lui-même. Cette approche
+semble pouvoir se réécrire comme un produit synchrone de deux automates.
+L'intérêt d'une telle réécriture est qu'on pourrait exploiter
+les résultats théoriques et pratiques déjà connus dans la communauté
+des automates.
+Nous pensons investiguer cette voie pour améliorer notre approche,
+s'affranchir, à terme, de tout autre générateur et améliorer la
+connaissance à ce sujet.
+
+De plus, marcher dans une partie d'un $\mathsf{N}$-cube est le modèle théorique que
+nous avons établi pour notre classe de générateurs. On a vu, via les itérations généralisées
+qu'on pouvait modifier plusieurs bits
+en une seule itération. Les premiers travaux pratiques réalisés ont montré
+que le nombre d'itérations suffisant pour converger vers une distribution uniforme
+est plus petit que celui obtenu en marchant et qu'il diminue à mesure que $\mathsf{N}$
+augmente. Pour l'instant, nous n'avons pas réussi à obtenir une majoration du nombre d'itérations
+pour le temps d'arrêt, ce qui pourrait être une perspective.
+
+\subsubsection{Des codes de Gray localement et globalement équilibrés}
+Enfin, pour générer une fonction dont la matrice de Markov est doublement
+stochastique
+--condition nécessaire pour fournir une sortie uniformément distribuée--,
+nous avons proposé principalement la méthode de
+suppression de chemin hamiltonien dans un $\mathsf{N}$-cube.
+Nous avons fait sauter un premier verrou en proposant une méthode déterministe à l'extension
+de Robinson-Cohn. Il est apparu récemment des algorithmes permettant d'obtenir des codes de Gray
+localement équilibrés, c.-à-d. où la longueur du plus grand nombre d'étapes entre
+deux changements d'un même bit est aussi petite que possible.
+Dans tous les cas, aucun des ces codes n'est globalement équilibré ni même presque équilibré.
+Cette double propriété serait cependant très intéressante aussi bien théoriquement que pratiquement
+pour nos générateurs.
+Un second verrou consistera à adapter ces algorithmes pour proposer des codes possédant les
+deux propriétés d'équilibrage.
+
+\subsubsection{Stéganalyse par deep learning}
+
+Les démarches de stéganalyse sont souvent composées de 2 étapes:
+caractérisation puis classification.
+On extrait au préalable une grande quantité des caractéristiques du média
+puis on utilise une méthode de
+classification basée sur celles-ci. La communauté voit souvent cette
+seconde étape comme une boite noire et se concentre
+sur la construction de l'ensemble des caractéristiques les plus discriminantes.
+Autant que nous sachions, les méthodes algébriques
+de réduction de domaine (analyse par composant principaux, SVD)
+ont rarement été utilisées comme une étape intermédiaire entre la caractérisation et
+la classification. Ces méthodes ont déjà été
+appliquées avec succès lorsqu'elles sont combinées avec des méthodes
+d'apprentissage, par exemple dans de la reconnaissance faciale.
+Je propose d'étudier cette piste dans ce domaine.
+
+
+De plus les résultats obtenus en stéganalyse à l'aide de deep learning à base de convolutions
+sont très prometteurs lorsque la clef qui a servi à l'embarquement est constante.
+Malheureusement, lorsque la clef varie, nous n'avons pas réussi à généraliser ces avancées.
+Les démarches les plus efficaces demeurent
+celles obtenues par des approches classiques à base de caractéristiques statistiques (features)
+d'images.
+Cependant, en étudiant plus finement les features, on constate que nombreuses sont celles qui sont aussi
+basées sur des produits de convolution.
+Je propose d'étudier exhaustivement ces features pour d'abord traduire
+en deep-learning celles qui sont des convolutions directes. Il restera ensuite
+à adapter l'outil de deep learning aux caractéristiques restantes ce qui est un autre challenge
+scientifique.
+
--- /dev/null
+
+Introduire mathématiques discrètes
+
+Systèmes dynamiques discrets
+
+convergence vs divergence
+
+chaos <=> aléa
+
+PRNG
+
+codes de Gray
+
+générateur c Sécurité informatique: régularité -> marquage
+
+Dérivées partielles discrete pour la sétagno
\chapter*{Introduction}
-Blabla blabla.
+\input{intro}
\mainmatter
\part{Réseaux discrets}
-\chapter{Iterations discrètes de réseaux booléens}
+\chapter{Iterations discrètes de réseaux booléens}\label{chap:sdd}
Ce chapitre formalise tout d'abord ce qu'est
un réseau booléen (section~\ref{sec:sdd:formalisation}. On y revoit
de telles fonctions.
-\chapter{Prédiction des systèmes chaotiques}
+\chapter{Prédiction des systèmes chaotiques}\label{chp:ANN}
\input{chaosANN}
\part{Applications à la génération de nombres pseudo aléatoires}
-\chapter{Caractérisation des générateurs chaotiques}
+\chapter{Caractérisation des générateurs chaotiques}\label{chap:PRNG:chao}
\input{15RairoGen}
-\chapter{Les générateurs issus des codes de Gray}
+\chapter{Les générateurs issus des codes de Gray}\label{chap:PRNG:gray}
\input{14Secrypt}
\chapter{Des embarquements préservant le chaos}\label{chap:watermarking}
\input{oxford}
-\chapter{Une démarche de marquage de PDF}
+\chapter{Une démarche de marquage de PDF}\label{chap:watermarking:pdf}
\input{ahmad}
-\chapter{Une démarches plus classique de dissimulation: STABYLO}
+\chapter{Une démarches plus classique de dissimulation: STABYLO}\label{chap:stabylo}
\input{stabylo}
-\chapter{Schéma de stéganographie: les dérivées du second ordre}
+\chapter{Schéma de stéganographie: les dérivées du second ordre}\label{chap:th:yousra}
\input{stegoyousra}
\part{Conclusion et Perspectives}
+\input{conclusion}
-\JFC{Perspectives pour SDD->Promela}
-Among drawbacks of the method, one can argue that bounded delays is only
-realistic in practice for close systems.
-However, in real large scale distributed systems where bandwidth is weak,
-this restriction is too strong. In that case, one should only consider that
-matrix $s^{t}$ follows the iterations of the system, \textit{i.e.},
-for all $i$, $j$, $1 \le i \le j \le n$, we have$
-\lim\limits_{t \to \infty} s_{ij}^t = + \infty$.
-One challenge of this work should consist in weakening this constraint.
-We plan as future work to take into account other automatic approaches
-to discharge proofs notably by deductive analysis~\cite{CGK05}.
-
-\JFC{Perspective ANN}
-
-In future work we intend to enlarge the comparison between the
-learning of truly chaotic and non-chaotic behaviors. Other
-computational intelligence tools such as support vector machines will
-be investigated too, to discover which tools are the most relevant
-when facing a truly chaotic phenomenon. A comparison between learning
-rate success and prediction quality will be realized. Concrete
-consequences in biology, physics, and computer science security fields
-will then be stated.
-Ajouter lefait que le codede gray n'est pas optimal.
-On pourrait aussi travailler à établir un classement qui préserverait
-le fait que deux configurations voisines seraient représentées
-par deux entiers voisins. Par optimisation?
-
-\JFC{Perspectives pour les générateurs} : marcher ou sauter... comment on
-pourrait étendre, ce que l'on a déjà, ce qu'il reste à faire.
-
-
-\JFC{prespectives watermarking : réécrire l'algo nicolas dans le formalisme
-du chapitre 8}
-
-% TSI 2015
-% \chapter{Conclusion}
-% Blabla blabla.
\appendix
