From e878014111cef8e935255d892d3d132429d03469 Mon Sep 17 00:00:00 2001 From: Christophe Guyeux Date: Fri, 20 Feb 2015 16:29:03 +0100 Subject: [PATCH] ajout de la partie chaos --- chaos.tex | 461 ++++++++++++++++++++++++++++++++++++++++++++++++++++ graphe1.pdf | Bin 0 -> 3657 bytes graphe2.pdf | Bin 0 -> 4242 bytes 3 files changed, 461 insertions(+) create mode 100644 chaos.tex create mode 100644 graphe1.pdf create mode 100644 graphe2.pdf diff --git a/chaos.tex b/chaos.tex new file mode 100644 index 0000000..74d07cf --- /dev/null +++ b/chaos.tex @@ -0,0 +1,461 @@ + + +\subsection{Notations and terminologies}\label{sec:notations} + + +Denote by $\mathds{B}$ the Boolean set, by $\mathds{N}^\ast$ the set +of natural integers $\{1,2,3, \hdots \}$, and by $\mathds{N}=\mathds{N}^\ast \cup \{0\}$. +For $a,b \in \mathds{N}, a \leqslant b$, $\llbracket a, b \rrbracket$ means the set +$\{a, a+1, \hdots , b\}$ of integers belonging between $a$ and $b$. +For any finite set $X$, $|X|$ denotes its cardinality. +The $n-$th of a sequence $v$ of vectors is $v^n$ while its $i-$th component is $v_i^n$, +so $v=\left(v^n\right)_{n \in \mathds{N}}$. +Finally, $\overline{x}$ stands for the negation of the Boolean $x$, while $\lfloor y \rfloor$ is +the largest integer lower than $y$. + +\subsubsection{Devaney's Chaotic Dynamical Systems} +\label{subsec:Devaney} + + +Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f : +\mathcal{X} \rightarrow \mathcal{X}$. + +\begin{Def} +The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets +$U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq +\varnothing$. +\end{Def} + +\begin{Def} +An element $x$ is a \emph{periodic point} for $f$ of period $n\in \mathds{N}^*$ +if $f^{n}(x)=x$.% The set of periodic points of $f$ is denoted $Per(f).$ +\end{Def} + +\begin{Def} +$f$ is said to be \emph{regular} on $(\mathcal{X}, \tau)$ if the set of periodic +points for $f$ is dense in $\mathcal{X}$: for any point $x$ in $\mathcal{X}$, +any neighborhood of $x$ contains at least one periodic point (without +necessarily the same period). +\end{Def} + + +\begin{Def}[Devaney's formulation of chaos~\cite{Devaney}] +The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and +topologically transitive. +\end{Def} + +The chaos property is strongly linked to the notion of ``sensitivity'', defined +on a metric space $(\mathcal{X},d)$ by: + +\begin{Def} +\label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions} +if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any +neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that +$d\left(f^{n}(x), f^{n}(y)\right) >\delta $. + +The constant $\delta$ is called the \emph{constant of sensitivity} of $f$. +\end{Def} + +Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is +chaotic and $(\mathcal{X}, d)$ is a metric space, then $f$ has the property of +sensitive dependence on initial conditions (this property was formerly an +element of the definition of chaos). + + +\subsubsection{Introducing the \textit{CIPRNG} categories of chaotic iterations based pseudorandom number generators} + +Define by $\mathcal{S}_X$ the set of sequences whose elements belong in $X \subset \mathds{N}, X \neq \varnothing$, +that is, $\mathcal{S}_X = \mathcal{X}^\mathds{N}$. +Let $\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$, and +$\mathcal{P} \subset \mathds{N}^\ast$ a non empty and finite set of integers. + +Any couple $(u,v) \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$ defines +a ``chaotic iterations based'' pseudorandom number generator, which is denoted by $\textit{CIPRNG}_f^2(u,v)$~\cite{wbg10:ip}. It is +defined as follows: +\begin{equation} +\label{CIPRNGver2} +\left\{ +\begin{array}{l} + x^0 \in \mathds{B}^\mathsf{N}\\ + \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if }~ i=u^n \\ x_i^n & \text{else} \end{array} \right.\\ + \forall n \in \mathds{N}, y^n = x^{v^n} . +\end{array} +\right. +\end{equation} +The outputted sequence produced by this generator is $\left(y^n\right)_{n \in \mathds{N}}$. +Remark that, given a sequence $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ called a ``chaotic strategy'', +the following way to iterate: +$$x^0 \in \mathds{B}^\mathsf{N}, \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if }~ i=S^n \\ x_i^n & \text{else} \end{array} \right. ,$$ +is referred in the discrete mathematics literature as ``chaotic iterations''~\cite{Robert} (a terminology which has +\emph{a priori} no relation with the mathematical theory of chaos recalled previously), which +explains the name provided to these categories of pseudorandom number generators. + + +The formerly proposed $\textit{CIPRNG}_f^1(u)$~\cite{bgw09:ip,guyeuxTaiwan10} is equal to \linebreak $\textit{CIPRNG}_f^2\left(u,\left(1\right)_{n\in \mathds{N}}\right)$, where $\left(1\right)_{n\in \mathds{N}}$ is the sequence that is +uniformly equal to 1. +It has been proven as chaotic for the vectorial Boolean negation $f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$, +$(x_1, \hdots , x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, \overline{x_\mathsf{N}})$ in \cite{bgw09:ip} +and for a larger set of well-chosen iteration functions in~\cite{bcgr11:ip} but, +as only one bit is modified at each iteration, this generator is not able to pass any reasonable statistical tests. + +The $\textit{XOR~CIPRNG}(S)$, for its part~\cite{DBLP:journals/corr/abs-1112-5239}, is defined as follows: $x^0 \in \mathds{B}^\mathsf{N}$, and $\forall n \in \mathds{N}, x^{n+1} = x^n \oplus S^n$ +where $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ and $\oplus$ stands for the bitwise \emph{exclusive or} (xor) operation +between the binary decomposition of $x^n$ and $S^n$. This is indeed a $CIPRNG_{f_0}^2 (u,v)$ generator: +%, for +%$u,v \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$: +for any given $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, $v^n$ is the number +of 1's in the binary decomposition of $S^n$ while $u^{v^n}, u^{v^n+1}, \hdots , u^{v^{n+1}-1}$ +are the positions of these ones. +The $\textit{XOR~CIPRNG}$ has been proven chaotic and it is able to pass all the most stringent statistical +batteries of tests~\cite{DBLP:journals/corr/abs-1112-5239}, namely: DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, and TestU01~\cite{LEcuyerS07}, +which encompasses the two former ones. Furthermore, the output sequence is cryptographically secure +when $S$ is cryptographically secure~\cite{DBLP:journals/corr/abs-1112-5239}. +We are then left to prove $\textit{CIPRNG}_f^2(u,v)$ is chaotic. + +\subsection{The $\textit{CIPRNG}_f^2(u,v)$ is chaotic for well-chosen $f$}\label{sec:wellchosen} + +\subsubsection{The generator as a discrete dynamical system} + + +Using notations of the previous section, consider a $\textit{CIPRNG}_f^2(u,v)$ generator $G$, with +$\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$, +$u \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, and $v \in \mathcal{S}_\mathcal{P}$, with +$\mathcal{P} \subset \mathds{N}$ a finite nonempty set having the cardinality +$\mathsf{p} \in \mathds{N}^\ast$. +Denote by $p_1, p_2, \hdots, p_\mathsf{p}$ the ordered elements of $\mathcal{P}$: $\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$ +and $p_1< p_2< \hdots < p_\mathsf{p}$. +Let +$$ +\begin{array}{cccc} + F_f: & \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket & \longrightarrow & \mathds{B}^\mathsf{N}\\ + & (e,i) & \longmapsto & (e_1, \hdots , e_{i-1}, f(e)_i, e_{i+1}, \hdots , e_{\mathsf{N}}) +\end{array} +$$ +and +$$ +\begin{array}{cccc} + F_{f,\mathsf{p}} : & \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^\mathsf{p} & \longrightarrow & \mathds{B}^\mathsf{N}\\ + & (e,(u^0, u^1, \hdots, u^{\mathsf{p}-1})) & \longmapsto & F_f(\hdots (F_f(F_f(e,u^0), u^1), \hdots), u^{\mathsf{p}-1}) . +\end{array} +$$ + +Denote by $\mathcal{X}_{\mathsf{N},\mathcal{P}}= \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, where +$\mathds{S}_{\mathsf{N},\mathcal{P}}=\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}\times \mathcal{S}_\mathcal{P}$, +we define the shift operation on sequences as follows, +$$\begin{array}{cccc} +\sigma:&\mathcal{S}_{X} &\longrightarrow +& \mathcal{S}_{X} \\ +& (u^k)_{k \in \mathds{N}} & \longmapsto & (u^{k+1})_{k \in \mathds{N}}, +\end{array} +$$ +and let +$$\begin{array}{cccc} +\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow +&\mathds{S}_{\mathsf{N},\mathcal{P}} \\ +& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \longmapsto & \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right),\sigma\left((v^k)_{k \in \mathds{N}}\right)\right). +\end{array} +$$ +In other words, $\Sigma$ receives two sequences $u$ and $v$, and +it operates $v^0$ shifts on the first sequence and a single shift +on the second one. +Let +\begin{equation} +\begin{array}{cccc} +G_f :& \mathcal{X}_{\mathsf{N},\mathcal{P}} & \longrightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\ + & (e,(u,v)) & \longmapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) . +\end{array} +\end{equation} +Then the outputs $(y^0, y^1, \hdots )$ produced by the $\textit{CIPRNG}_f^2(u,v)$ generator +are the first components of the iterations $X^0 = (x^0, (u,v))$ and $\forall n \in \mathds{N}, +X^{n+1} = G_f(X^n)$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. + + + + + + +\subsubsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} + +We define a distance $d$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ as follows. +Consider +$x=(e,s)$ and $\check{x}=(\check{e},\check{s})$ in +$\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $, +where $s=(u,v)$ and $\check{s}=(\check{u},\check{v})$ are in $ \mathds{S}_{\mathsf{N},\mathcal{P}} = +\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. +\begin{itemize} +\item $e$ and $\check{e}$ are integers belonging in $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. The Hamming distance +on their binary decomposition, that is, the number of dissimilar binary digits, constitutes the integral +part of $d(X,\check{X})$. +\item The fractional part is constituted by the differences between $v^0$ and $\check{v}^0$, followed by the differences +between finite sequences $u^0, u^1, \hdots, u^{v^0-1}$ and $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, followed by + differences between $v^1$ and $\check{v}^1$, followed by the differences +between $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ and $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc. +More precisely, let $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ and $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. +\begin{itemize} +\item The $p$ first digits of $d(x,\check{x})$ is $|v^0-\check{v}^0|$ written in decimal numeration (and with $p$ digits). +\item The next $n\times \max{(\mathcal{P})}$ digits aim at measuring how much $u^0, u^1, \hdots, u^{v^0-1}$ differs from $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. The $n$ first +digits are $|u^0-\check{u}^0|$. They are followed by +$|u^1-\check{u}^1|$ written with $n$ digits, etc. +\begin{itemize} +\item If +$v^0=\check{v}^0$, then the process is continued until $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ and the fractional +part of $d(X,\check{X})$ is completed by 0's until reaching +$p+n\times \max{(\mathcal{P})}$ digits. +\item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$ blocs of $n$ +digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$, +$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by O's if required. +\item The case $v^0>\check{v}^0$ is dealt similarly. +\end{itemize} +\item The next $p$ digits are $|v^1-\check{v}^1|$, etc. +\end{itemize} +\end{itemize} + + + + +\begin{xpl} +Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), and that +$s=\left\{ +\begin{array}{l} +u=\underline{6,} ~ \underline{11,5}, ...\\ +v=1,2,... +\end{array} +\right.$\\ +while +$\check{s}=\left\{ +\begin{array}{l} +\check{u}=\underline{6,4} ~ \underline{1}, ...\\ +\check{v}=2,1,... +\end{array} +\right.$ + +So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$ +Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, +and we use $p$ digits to code this difference ($\mathcal{P}$ being $\{1,2,11\}$, this difference can be equal to 10). We then take the $v^0=1$ first terms of $u$, each term being coded in $n=2$ digits, that is, 06. As we can iterate +at most $\max{(\mathcal{P})}$ times, we must complete this +value by some 0's in such a way that the obtained result +has $n\times \max{(\mathcal{P})}=22$ digits, that is: +0600000000000000000000. Similarly, the $\check{v}^0=2$ first +terms in $\check{u}$ are represented by 0604000000000000000000, and the absolute value of their +difference is equal to 0004000000000000000000. These digits are concatenated to 01, and +we start again with the remainder of the sequences. +\end{xpl} + + +\begin{xpl} +Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that + +$s=\left\{ +\begin{array}{l} +u=\underline{6,7,} ~ \underline{4,2,} ...\\ +v=2,2,... +\end{array} +\right.$\\ +while +$\check{s}=\left\{ +\begin{array}{l} +\check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\ +\check{v}=7,2,... +\end{array} +\right.$ + +So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, as $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$, +and $|9800000-4200000| = 5600000$. +\end{xpl} + + + +$d$ can be more rigorously written as follows: +$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$ +where: % $p=\max \mathcal{P}$ and: +\begin{itemize} +\item $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance, +\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline +$$\begin{array}{rcl} + d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= & + \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} + \bigg(|v^k - \check{v}^k| \\ + & & + \left| \sum_{l=0}^{v^k-1} + \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} - + \sum_{l=0}^{\check{v}^k-1} + \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg) +\end{array} +$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$ +\end{itemize} + + +Let us show that, +\begin{proposition} +$d$ is a distance on $\mathcal{X}$. +\end{proposition} + + +\begin{proof} + $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance. We will prove that + $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is a distance +too, thus $d$ will also be a distance, being the sum of two distances. + \begin{itemize} +\item Obviously, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, and if $s=\check{s}$, then +$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$. Conversely, if $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, then +$\forall k \in \mathds{N}, v^k=\check{v}^k$ due to the +definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null and correspond to $|u^0-\check{u}^0|$, we can conclude that $u^0=\check{u}^0$. An extension of this result to the whole first $n \times \max{(\mathcal{P})}$ bloc leads to $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, and by checking all the $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$. + \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is clearly symmetric +($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). +\item The triangle inequality is obtained because the absolute value satisfies it too. + \end{itemize} +\end{proof} + + +Before being able to study the topological behavior of the general +chaotic iterations, we must first establish that: + +\begin{proposition} + For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on +$\left( \mathcal{X},d\right)$. +\end{proposition} + + +\begin{proof} +We will show this result by using the sequential continuity. Consider a +sequence $x^n=(e^n,(u^n,v^n)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}^\mathds{N}$ such +that $d(x^n,x) \longrightarrow 0$, for some $x=(e,(u,v))\in +\mathcal{X}_{\mathsf{N},\mathcal{P}}$. We will show that +$d\left(G_f(x^n),G_f(x)\right) \longrightarrow 0$. +Remark that $u$ and $v$ are sequences of sequences. + +As $d(x^n,x) \longrightarrow 0$, there exists +$n_0\in\mathds{N}$ such that +$d(x^n,x) < 10^{-(p+n \max{(\mathcal{P})})}$ +(its $p+n \max{(\mathcal{P})}$ first digits are null). +In particular, $\forall n \geqslant n_0, e^n=e$, +as the Hamming distance between the integral parts of +$x$ and $\check{x}$ is 0. Similarly, due to the nullity +of the $p+n \max{(\mathcal{P})}$ first digits of +$d(x^n,x)$, we can conclude that $\forall n \geqslant n_0$, +$(v^n)^0=v^0$, and that $\forall n \geqslant n_0$, +$(u^n)^0=u^0$, $(u^n)^1=u^1$, ..., $(u^n)^{v^0-1}=u^{v^0-1}$. +This implies that: +\begin{itemize} +\item $G_f(x^n)_1=G_f(x)_1$: they have the same +Boolean vector as first coordinate. +\item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\Sigma (u^n,v^n); \Sigma(u,v)) = 10^{p+n \max{(\mathcal{P})}} d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u^n,v^n); (u,v))$. As the right part of the equality tends +to 0, we can deduce that it is the case too for the left part of the equality, and so +$G_f(x^n)_2$ is convergent to $G_f(x)_2$. +\end{itemize} +\end{proof} + +\begin{figure}[h] +\centering +\includegraphics[scale=0.85]{graphe1.pdf} +\caption{Chaotic iterations of $f_0$, defining the $CIPRNG_{f_0}^1$ ($\mathsf{N}=2$)} +\label{graphe1} +\end{figure} + +\subsubsection{The $\textit{CIPRNG}_f^2(u,v)$ as iterations on a graph} + +We define the directed graph $\mathcal{G}_{f,\mathcal{P}}$ as follows. +\begin{itemize} +\item Its vertices are the $2^\mathsf{N}$ elements of $\mathds{B}^\mathsf{N}$. +\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples +having their elements in $\llbracket 1, \mathsf{N} \rrbracket $. +\item There is an arc labeled $a_1, \hdots, a_{p_i}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if $y=F_{f,p_i} (x, (a_1, \hdots, a_{p_i})) $. +\end{itemize} + + +\begin{figure}[h] +\centering +\includegraphics[scale=0.85]{graphe2.pdf} +\caption{Iteration graph of $CIPRNG_{f_0}^2$, $\mathcal{P}=\{2,3\}$, $\mathsf{N}=2$} +\label{graphe2} +\end{figure} + +\begin{xpl} +Consider for instance $\mathsf{N}=2$, $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2, (x_1,x_2) \longmapsto (\overline{x_1}, \overline{x_2})$, and +$\mathcal{P}=\{2,3\}$. Chaotic iterations of $f_0$ are given in Figure~\ref{graphe1} while the digraph $\mathcal{G}_{f_0,\{2,3\}}$ is depicted in +Figure~\ref{graphe2}. Notice that here, orientations of arcs are not necessary +since the function $f$ is equal to its inverse $f^{-1}$. +\end{xpl} + +\subsubsection{Proofs of chaos} + +We will show that, +\begin{proposition} +\label{prop:trans} + $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected if and only if $G_f$ is +topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$. +\end{proposition} + + +\begin{proof} +Suppose that $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected. +Let $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) +\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. +We will find a point $y$ in the open ball $\mathcal{B}(x,\varepsilon )$ and +$n_0 \in \mathds{N}$ such that $G_f^{n_0}(y)=\check{x}$: this strong transitivity +will imply the transitivity property. +We can suppose that $\varepsilon <1$ without loss of generality. + +Let us denote by $(E,(U,V))$ the elements of $y$. As +$y$ must be in $\mathcal{B}(x,\varepsilon)$ and $\varepsilon < 1$, +$E$ must be equal to $e$. Let $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$. +$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ must be lower than +$\varepsilon$, so the $k$ first digits of the fractional part of +$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ are null. +Let $k_1$ the smallest integer such that, if $V^0=v^0$, ..., $V^{k_1}=v^{k_1}$, + $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$. +Then $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$. +In other words, any $y$ of the form $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}), +(v^0, ..., v^{k_1}))$ is in $\mathcal{B}(x,\varepsilon)$. + +Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\mathcal{G}_{f,\mathcal{P}}$ +being strongly connected, there is a path between $e'$ and $\check{e}$. Denote +by $a_0, \hdots, a_{k_2}$ the edges visited by this path. We denote by +$V^{k_1}=|a_0|$ (number of terms in the finite sequence $a_1$), +$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, and by +$U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$, +$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,... + +Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., + a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak + $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ..., + |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. So $y\in \mathcal{B}(x,\varepsilon)$ + and $G_{f}^{k_1+k_2}(y)=\check{x}$. + + +Conversely, if $\mathcal{G}_{f,\mathcal{P}}$ is not strongly connected, then there are +2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$. +That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$ +and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$ +cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transitive. +\end{proof} + + +We show now that, +\begin{proposition} +If $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected, then $G_f$ is +regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$. +\end{proposition} + +\begin{proof} +Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. +As in the proofs of Prop.~\ref{prop:trans}, let $k_1 \in \mathds{N}$ such +that +$$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$ +$$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\} +\subset \mathcal{B}(x,\varepsilon),$$ +and $y=G_f^{k_1}(e,(u,v))$. $\mathcal{G}_{f,\mathcal{P}}$ being strongly connected, +there is at least a path from the Boolean state $y_1$ of $y$ and $e$. +Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path. +Then the point: +$$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., + a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$ +$$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$ +is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$. +\end{proof} + +$G_f$ being topologically transitive and regular, we can thus conclude that +\begin{Theo} +The pseudorandom number generator $\textit{CIPRNG}_f^2$ denoted by $G_f$ in +this section is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if +and only if its graph $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected. +\end{Theo} diff --git a/graphe1.pdf b/graphe1.pdf new file mode 100644 index 0000000000000000000000000000000000000000..0e0e765dd683f6f0aff86d2ce5a94a09e4aa646f GIT binary patch literal 3657 zcmai12~-o;8b%Me3|IkIYzw!_5(*@l>=8sD0TEdu1W>?Y2m=`*i^)Vmiwi1>SQP74 zL6qVX6kI^17Nm8fmVknyNJXp*izpT=&ke=bJAo7|eaAT=hxzm0`)_liDhNzLXaJc|FhUE)G)k>nifI6&-w=Ss;u0@q5{RTj14`!rK7SDcSF7PN zz}7ptyMuu+D7-h6)gNX-P|OlcN+7flZ499g?4wl6VTJHp?}5V2#NG?2uw*PyBF6xQ zM#xn(vhbu>wPd+iu0ol7Hp*mhSxi2MM~hcWR5A>us$%0D2iB6c1Zw3muw{nr<|^Wp zLR?A!PJbOx$mKKI**n=Y3-~ zZ0mV``OoK7$u43+)D5TP!!z@DKOmY9w^+1v6ZV{JJnS9@zqBAep zK0*|;D&R+* zvZmE{Z89?qFR^>${-nJ-sAx}TDpG5=wLuCGROeo9PzSpCkzD;l<_oppBg(mZtJ z(r>(U*BPmgJ+tPDMUNg>=csq*cSn3-p61k*HSy;9zQQ#BO}xwoB4^NjtUX~#WAtBl^9NYUL_5ABpf#1`Xrjwo7#c#&4Odg;1zqt0~?hd0CAKJYgwe~9#1FY#0LG7mR zLR_$p&$H8Np6$MOjH_POIr8ig(U~ZZ&Sx_iEGIhZK&LxEzW`P`mXD^8c)1wJZ;O8}0w7@A4m&a%|!Ag0clJD;l zjKyn7;8YMotiLTVeLjgeFq;8rRY0Wm!POcU^ za5*q5NPh7ez+tmFunbR)lq4MZ3w#PBDql=LApI>Fll%>?Mrd;hNg^)wRK&yKz=A^v zOdbZfkQD-OjRuye?*L$s%^+JuLOq41RA4k>xstX5Q!C+U$rh7z#DpZFZ|~r^^aexO z|HjgTJg0A%V2}q;-cSn9*|$B~cjEkszr;srZ$-FFa&&qjG~ZlS2$nPnC=sB!Y{>&b zHE-qeSM6Q3tmS1Nd}*PJ|JmSQT|yhXd%pK*`m*DR>%x@q)LdypO!?V}tb-jh zt*+n=Iq4H-e`nSgS^gf+c)#k&-g&cEW~5v=*3M1NHbqP`j@a?Pzvm&^uwAF~lVzN< zFnu)tZ}$wzu5XQ zx>cBpoTE8{V)>fgLYuG>Tgxe**`6DbWwG^&{f+Z8ezV-{;o~=ELd>xd6UI<-3a8r? zS}x9-a>3nH+1R(eFtynCkTqjcgKmb!&S%K3P2K4YBC@Lkn&FzCU> zM%I(PI!V@=%`?Rr4Qb~#raP-FzDA;k=sUve9OfXM>8*#i8wRy*8 zJJfjD-gT-9I@(j>x9#5Yqg6=Uv79k+r$pn!%0?EvD@tsAv3e}SOzK2+#P$&O>#Db` z9&4ZFS!Ktz^_efjB3}&sXOgQK!--GX) z(Q`ZJrHtsk`!3_{jl65((QTVM71Bt>?}v-47S5>l7`0?WX=$U)jXCR1-YCn7A9>26 z@6C%_51p%OIK55AQ#Wq@Hs)o~y6{n>dM~H>j80=;zSJgLdH49_ie;tYPamhhywrQ9 zCzDb+E9Q84J-c|8=23LluA8Z=9*&zgo7zmIx5sM7_g1#dayXTk&;2g!+TQW|ZJcG@ zr9XGCt|%zs*S^&>FFjRxGVZ~hmm8xCy3bz!EQ40rHafFHH?L<)#6#Kjg((|nJ*_>n zDlvzX=@2B3xb3E`?u?qIImD<{hP{YV+%;lPN$+Q1No4Q0nLWn|Hnn_k8{xw7crEyDl8W2eMzDQs`7q8tW8Xe zkth@-9g1bR2Eb2$PR<|C6-*}x7QDoRC3_A)d+NsYxJQ0X%f`rj7`!b~=Z0|py|34xKkfWly7aQToD zKD5zM1|-9O*yt#n?T0o7j|1O7KD41s`Y=C~J$x<7<_yaP<+6sa<@4c_@nH-GpYbm? z?hqTHmOvsuXzOa@EHa|a)HSwx->4Ixnz`gy>0C}L;l9pr=j1)|hHW&i*H literal 0 HcmV?d00001 diff --git a/graphe2.pdf b/graphe2.pdf new file mode 100644 index 0000000000000000000000000000000000000000..9ea5f8e9c238fd79ba8a92b46abfa9e1c76758f0 GIT binary patch literal 4242 zcmb7I2|QG58>f;Q%6@Ih;ihZ3W?$@*L9$JjkP&0%m>C%}jbm+8wo;$C$x@c9h1;b? zQmG_MS-TNYKD3}k$&yOprtcg}xwrd$zu!0KceeLD@3Z{h<^MdRL!;Un;?M*X4!{EZ zfFP8a84BaTWrYGh01<9-1$dGJ^TR?Q0Ee=$K!G7FqzisgSDKK| z3S)voK$jK;arhwstRHaX1_&9#D1eS7kpK<^3Fue~9)6)9ryy$fBm77X0in4T8Y>Wa z&|74Lu*k@qKh_M05zJ?!<{Sf%09+S!K)hcF$eJGlfgw;RK$;bTdkEpz`7VpXLt$LO zP=1(@35EjXIZ-E&#bs>dN5Xhu;R9z(1aK4rjLNt85v2>39KjGa!~qBd6vmbt48cHP zY=apPNClaE7Kn5Tg@ho3hl=brc!qb!ify!(@KuoA-15Br;~ykfLDNgrvn68gbrP=- zbmwK~aYj5^u;b+t5Ck$I02wZO9v+~;-)5u7z$3tP10mR741)b)M-ia~1^?vTqUaI5 zHj$8>8w5K)YsHlU82vXR7GM}8o zcmXg*_=Pz(9~PoW$eSHz+`KgGFX+tRfq*VDGaw#3he#9z*+`a<5#i1g;0VS;tjl&^N za8Pbx0nqFUK%81Ugt?c!%v0A;q=#R6{(dR;thTFWdbgO>UdZ{1lxrU2^i{)T#mVWY z4(Y;UZ>NOiNuvk7xg;0u$xoYxm6gq|9sknv?$wn)KjmC)-GiZ8)VuatItZ$MHV(`; zHaSR|8Vm{5)|qIh7x!OVS$|06pXDW5#Y@i5^eRp@TdystxlK)sd1GYn2WH%v}(V>4+n=g!qVYOpM+LR1_yff#ByhkyA_I*x_aX9u|qt$z+TXmh%+svi{T&Y~_vS06VWfM`gs^cm4 z?kf)e9BPAJ;^MeW-RJnr+sz5$7jR%O?kaIL!=S#1l5k4NAnWl9`kGq8eaZpqM^P4j zNhwpl#eRD@UHkSO$z$|d)4R$hf|Wk;*1Xoj6`tXyo+C7=XAyLhQ#bM)(rccqZFwlv zs}t>a@YrX1kyyCqk7_NQB7L3lj>g(J#~_L1d%1ktkpe=OWlh9Uxzwx*OQG%~ZclLz zeqRS+=?ZkiG0vMpf}Ed5Y|GQ~!mWdxmLQ9*KSC?6wGta7)5rHRPej{$U5_`&sAT#y za!0*pO#I5a;-VXSf1Hj}mM`u{FAJCG+VeTd_tOYE!d>f*^pib<@kP+deJ{_qucMkK znCP!6s3(|l607S^wRa^b$uCtI2;1+?4X7ccd1NQad!0aCi9N(FELAlxRZxJ1tzGqr~SUezE!<#{ZPbnSYQ6{a{hqDaHOQ#cP#-4+fd2RQvwxVXXhT$D;Qj9W)yehQI9mn^Y)q8<^G?fRHNTNm5^4@R{|+FV7xAPyxM8I@+R(a26-b9y?TSH}rd5c&Vn&L*|FbSA{PI%I`%RC3>7*aiYj#V08NO5{{CV z&CX|v^c^T3cmGVfyM`el|3hJcd9THAa7JOrvTQCp$2-Wmz_&ZEM%=wE&20^r&2*?x zXk1#ld|E}Rpr(2};CHTO2Wcq5FC%Qo!2Fd;QKe4a4gFU)R2iR2966^^ zkaF)CExF%k#KYjMVa)9hiP4fWO~GeZ;iD52%ZoiWSM?24T+Ez^`;aZCTW)x^?Us{- z_ff42<~f7}DKdCF_Ez)12xP&M;+?KXBB%Zu>i8yl_c9-LgvA<3B&xEvYAPq1ncL;Z-JVD$h|lee&YA z1Ml=J1xE;HQl17W8tK)A?K^#4csScytwg7P*|?ZJH`)FF|T^1iZ?F6~UUze;^Zp2@Y&(d%3f3g3$-x#K{^n02_SZaag z<}!t^M25n+(478~yC593AZ*JOhCKnlwY7%^y_)D{SQLmn(UAc--q=J*t=#uvy+DI9xeD;4b#Q7aP2{7k6RZ z@(hm3gvfml$Io|_;=>M-)v5=jIy-3j+|HyWm#H--bvnn@e&9%{)1=LvRdCR@w2HyiY?7ppMHG@peUbtmas-LP^?YKP~qcPh%X6R{u_8Ty4!<(CORHp z>~)*(_EF3o=myB>rfN*bhSYJozXd!{)Fu8-Vvd%!F}y_ zo{hAVKmG8k(7!JsxQ^ubGN#hgJ6C3gbU8SC+q9?zx97EaKK3B|s^uw&&j=HgC2kw5 z?PLvAH3w|}g0V`VIdh}x$O*!>p!C$*#?cv6di+U_bY(_yU6a|)aq5+URM8fT()GRL zWo4yLn=+aj{@gOQUD&@V4KKekwZOKgUUL7`)bbzuGH0|}rXS?5HETP9?^u6Xw{>J# zE$5Er5%kR;{3<67oVeB;XN%T!J2I_)LE&i&eq@tpE*PP9p7i9j%w){&ceS57_doGf zwn7WzH=>o*^GJsuyP$siNuw%WqgT48obpAlU)xwuRJL|+ez~UT^Unq=@k0vb^u1-} zy-$>kB3{3#-tcAYUScf4%xD~B7Y~kFi_h$o85$gUGx9p4YDM@#eye2oL|ATLMEpdF zcxzDe+Rs+VI}Se-n%fTnV_2Gu!y;P%Tu34Nqb@6)D+q;~u{+=k z4nXvgjg1L_HD3@VoZTZ}dj!Ch!QwI*!GKK^2)OYBp$NDNTu{U1hx{MzeXIQxLBC~A=@H>1Ox)#+F+VNen7~#HZsgpe`~{$zn8<~zLz85;o|mheTn$*<%lo_ zf0M)GN#EJP6R_XugSUNnr~j)BJmq`;2;{~3ARz;03E}LY2yWbH5WxlG%I8A>Qoh3! dhE!j`T;Vla3NwVzEP@1MED@!nW8-3r`VZIsX+Qt~ literal 0 HcmV?d00001 -- 2.39.5