Augmenter l'entropie d'un message
dans Algèbre
Bonjour,
En premier lieu, quand je parle d'entropie, il s'agit de l'entropie selon Shannon.
De manière succinte, comme le suggère le titre, je cherche une application bijective (ou un algorithme inversible) pour augmenter l'entropie selon la théorie de l'information de Shanon. Mais l'entropie de Renyi convient aussi.
Formellement, on a une source d'information notée $X_m$ définie comme une suite de nombre définie dans $\mathbb{Z}_q$ ( noté aussi $\mathbb{Z}/q\mathbb{Z}$ ); $X_m = \{x_i \in \mathbb{Z}_q, i \in [0, m[\}$.
Il me faudrait alors une application $f$ qui transforme $X_m$ en $Y_n$ que l'on peut définir ainsi $f:
\left|
\begin{array}{rcl}
\mathbb{Z}_q & \longrightarrow & \mathbb{Z}_q \\
X_m & \longmapsto & Y_n \\
\end{array}
\right.$
Avec $Y_n = \{y_i \in \mathbb{Z}_q, i \in [0, n[\}$.
Il est évident que $m \leqslant n$.
Je ne veux pas nécessairement une application $f$ avec $m = n$ telle que $f:
\left|
\begin{array}{rcl}
X_n & \longrightarrow & Y_n \\
x_i & \longmapsto & y_i \\
\end{array}
\right. \nmid i \in [0, n[ $
Car cela va être compliqué à trouver je pense mais si vous la trouvez cela m’intéresse.
Ce n'est pas la peine de me répondre que pour obtenir $Y_n$, il suffit d'ajouter à $X_m$ des éléments issus d'une combinaison linaire (par un produit de matrices par exemple) des éléments de $X_m$, car il faudrait que ces contraintes soient respectées:
$\left\{
\begin{array}{l l}
n \ \geqslant \ \frac{m}{2} \\
Card (\{ E \ | E \subset X_m \ et \ E \subset Y_n \}) < \frac{m}{2} \\
H_b(X_m) \ \leqslant \ H_b(Y_m)
\end{array}
\right.$
Pour l'entropie $H_b$ on peut prendre celle de Shannon: $H_b(\{ s_i \in \mathbb{Z}_k | i \in [0, k[ \}, M) = - \sum_{i=0}^{i=k-1} P_M(s_i) log_b(P_M(s_i)) $, mais on peut prendre d'autres définitions tant qu'elle qualifie une entropie selon Shannon, et avec le paramètre $b$.
Pour l'entropie de Shannon, on admet que $ 0 \times log(0) = 0 $ pour les cas où $s_j \notin X_n | j \in [0, n[$ alors $P(s_j, \mathbb{Z}_k) = 0$
$P_M(s) = \frac{freq(s, M)}{card(E)}$
avec $freq(s, M)$ la fréquence d'apparition du symbole $ s $ dans le message $M$ définie ainsi: $freq(v, M) = \sum_{s\in\mathbb{Z}_q} e(s)$
où $e(s, M) = \left \{
\begin{array}{l l}
1 \ si \ s \in M \\
0 \ sinon
\end{array}
\right .$
En premier lieu, quand je parle d'entropie, il s'agit de l'entropie selon Shannon.
De manière succinte, comme le suggère le titre, je cherche une application bijective (ou un algorithme inversible) pour augmenter l'entropie selon la théorie de l'information de Shanon. Mais l'entropie de Renyi convient aussi.
Formellement, on a une source d'information notée $X_m$ définie comme une suite de nombre définie dans $\mathbb{Z}_q$ ( noté aussi $\mathbb{Z}/q\mathbb{Z}$ ); $X_m = \{x_i \in \mathbb{Z}_q, i \in [0, m[\}$.
Il me faudrait alors une application $f$ qui transforme $X_m$ en $Y_n$ que l'on peut définir ainsi $f:
\left|
\begin{array}{rcl}
\mathbb{Z}_q & \longrightarrow & \mathbb{Z}_q \\
X_m & \longmapsto & Y_n \\
\end{array}
\right.$
Avec $Y_n = \{y_i \in \mathbb{Z}_q, i \in [0, n[\}$.
Il est évident que $m \leqslant n$.
Je ne veux pas nécessairement une application $f$ avec $m = n$ telle que $f:
\left|
\begin{array}{rcl}
X_n & \longrightarrow & Y_n \\
x_i & \longmapsto & y_i \\
\end{array}
\right. \nmid i \in [0, n[ $
Car cela va être compliqué à trouver je pense mais si vous la trouvez cela m’intéresse.
Ce n'est pas la peine de me répondre que pour obtenir $Y_n$, il suffit d'ajouter à $X_m$ des éléments issus d'une combinaison linaire (par un produit de matrices par exemple) des éléments de $X_m$, car il faudrait que ces contraintes soient respectées:
$\left\{
\begin{array}{l l}
n \ \geqslant \ \frac{m}{2} \\
Card (\{ E \ | E \subset X_m \ et \ E \subset Y_n \}) < \frac{m}{2} \\
H_b(X_m) \ \leqslant \ H_b(Y_m)
\end{array}
\right.$
Pour l'entropie $H_b$ on peut prendre celle de Shannon: $H_b(\{ s_i \in \mathbb{Z}_k | i \in [0, k[ \}, M) = - \sum_{i=0}^{i=k-1} P_M(s_i) log_b(P_M(s_i)) $, mais on peut prendre d'autres définitions tant qu'elle qualifie une entropie selon Shannon, et avec le paramètre $b$.
Pour l'entropie de Shannon, on admet que $ 0 \times log(0) = 0 $ pour les cas où $s_j \notin X_n | j \in [0, n[$ alors $P(s_j, \mathbb{Z}_k) = 0$
$P_M(s) = \frac{freq(s, M)}{card(E)}$
avec $freq(s, M)$ la fréquence d'apparition du symbole $ s $ dans le message $M$ définie ainsi: $freq(v, M) = \sum_{s\in\mathbb{Z}_q} e(s)$
où $e(s, M) = \left \{
\begin{array}{l l}
1 \ si \ s \in M \\
0 \ sinon
\end{array}
\right .$
Réponses
-
Bonjour,
Juste une petite remarque: je suppose qu'au lieu de
Vous vouliez dire:Il me faudrait alors une application $f$ qui transforme $X_m$ en $Y_n$ que l'on peut définir ainsi $f:\left|\begin{array}{rcl}\mathbb{Z}_q & \longrightarrow & \mathbb{Z}_q \\X_m & \longmapsto & Y_n \\\end{array}\right.$
J'ai aussi du mal à interpréter cette histoire de $E$ et de cardinal de $E$. Je me suis donc permis d'interpréter un peu votre définition de l'entropie ainsi: $H(x)=-\displaystyle \sum_{s\in \mathbb{Z}_q} p_s(x) \log_q (p_s(x))$ avec $x\in (\mathbb{Z}_q)^{n}$ et $p_s(x)=\frac{card \left(\{ i\ | \ i\in |[1,n]|, x_i=s \}\right)}{n}$, ce qui correspond à ce que je connais de l'entropie de Shannon.Il me faudrait alors une application $f$ qui transforme $X_m$ en $Y_n$ que l'on peut définir ainsi $f:\left|\begin{array}{rcl}\mathbb{Z}_q^{(\mathbb{N})} & \longrightarrow & \mathbb{Z}_q^{(\mathbb{N})} \\X_m & \longmapsto & Y_n \\\end{array}\right.$
Si mon interprétation est bonne, je n'y connais rien en cryptographie, mais je ne crois pas qu'on puisse trouver une application bijective $f$ de $ \mathbb{Z}_q^{(\mathbb{N})} $ dans lui-même telle que $\forall x\in\mathbb{Z}_q^{(\mathbb{N})} \ H(x)<H(f(x))$. Parce qu'il y a une classe de message de plus petite entropie (les messages composés à partir d'un seul symbole) et il n'est probablement pas intéressant que ces messages aient un antécédent par $f$.
Si mon interprétation est correcte, on ne pourra donc négocier cette histoire qu'avec une application $f$ injective, mais non bijective (ce qui doit probablement correspondre à une partie des algorithmes inversibles). -
Merci Titi le curieux, oui votre interprétation est bonne, mon formalisme laissait effectivement à désirer.
En fait, oui l'application n'a pas besoin d'être bijective, elle correspond à un codage, il faut cependant une application de décodage.
J'aime bien l'idée d'utiliser un codage de Hill mais à condition que les 3 contraintes spécifiées soient respectées.
Pour le $E$ que vous n'avez pas compris je pense que vous parlez de la 2ème contrainte, j'ai tenté de dire que le nombre de sous-partie de symboles contigus (donc de sous-textes ou sous-chaines) communes à $X_m$ et à $Y_n$ devait être majoré par $\frac{m}{2}$.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 3
+2 Invités