Chiffrement Affine

Bonjour,

Je suis sur un exercice sur le chiffrement affine. Soit $n=pq$ ,$p,q$ des nombres premiers impairs distincts. On me demande de montrer que le nombre de clefs involutives (i.e la fonction de chiffrement est égale à la fonction de déchiffrement) est $n+p+q+1$. Je sais déjà par un autre exercice que les clefs (notons les $(a,b)$) sont involutives si et seulement si l'inverse de $a$ est $a$ et si $b(a+1)=0 \mod{n}$. Je n'arrive pas à dénombrer. J'ai essayé de tester avec $n=15$ pour voir ce qui se passe et je ne trouve que $5$ clés (ça part mal) pourtant je suis assez sûr de mon résultat.

Avez vous des indications?
Merci d'avance.

Edit : Je retire ce que j'ai dit pour $n=15$, j'avais oublié de prendre $a=1$.
Edit 2 : En fait cela ne me donne toujours pas le bon nombre de clefs.



Edité 2 fois. La dernière correction date de l’an passé et a été effectuée par Toborockeur.

Puisque $n=pq$ deux nombres premiers distincts.

$m\equiv 0\mod{n}$ est équivalente à $m\equiv 0 \mod{p}$ ET $m\equiv 0 \mod{q}$

Ce qui est clair.

Pour qu'un nombre $m$ soit divisible par $n=pq$ avec $\text{pgcd}(p,q)=1$ il faut et il suffit qu'il soit divisible par $p$ et $q$.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)



Edité 1 fois. La dernière correction date de l’an passé et a été effectuée par Fin de partie.

On n'a peut-être pas besoin de cette propriété.

$a$ est on propre inverse multiplicatif modulo $n$ se traduit par le fait que $a^2-1$ est divisible par $n$....

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)

Oui j'aurais du le préciser dans mon premier message mais j'ai déjà remarqué ça. Cela me permet de trouver les bons $a$ dans la pratique, mais je ne sais pas comment dénombrer à partir de cette condition.

Un sans parole ou si peu. Les involutions $\Z/pq\Z \ni x \mapsto ax + b \in \Z/pq\Z$, $p,q$ premiers impairs distincts. I.e. $a^2 = 1$ et $(a+1)b = 0$. Utilisation d'un isomorphisme d'anneaux dit isomorphisme chinois. Tableau à compléter :
$$
\begin {array} {lllll}
a = (1,1) & a+1 = (2,2) & b : \{0\} \times \{0\} & \# \{b \mid \cdots \} = 1 \\
a = (1,-1) & a+1 = (2,0) & b : \{0\} \times \Z/q\Z & \# \{b \mid \cdots \} = q \\
a = (-1,1) & a+1 = \cdots & b : \cdots & \# \{b \mid \cdots \} = p \\
a = (-1,-1) & a+1 = \cdots & b : \cdots & \# \{b \mid \cdots \} = pq \\
\end {array}
$$
Trop elliptique ? Incompréhensible ?

Comme je le comprends, je compléterais ce tableau comme ça :

$\begin {array} {lllll}

a = (1,1) & a+1 = (2,2) & b : \{0\} \times \{0\} & \# \{b \mid b(a+1)=0 \} = 1 \\

a = (1,-1) & a+1 = (2,0) & b : \{0\} \times \Z/q\Z & \# \{b \mid b(a+1)=0 \} = q \\

a = (-1,1) & a+1 = (0,2) & b : \Z/p\Z \times \{0\} & \# \{b \mid b(a+1)=0\} = p \\

a = (-1,-1) & a+1 = (0,0) & b : \Z/p\Z \times \Z/q\Z & \# \{b \mid b(a+1)=0 \} = pq \\

\end {array}$

Mais je ne comprends pas vraiment le tableau, surtout pourquoi $a$ et $b$ se sont transformés en couples.



Edité 1 fois. La dernière correction date de l’an passé et a été effectuée par AD.

Utilisation de l'isomorphisme chinois $\Z/pq\Z \ni x \bmod pq \longmapsto (x \bmod p, x \bmod q) \in \Z/p\Z \times \Z/q\Z$.

La transformation en couples ?

Citation
Claude Quitté
Utilisation d'un isomorphisme d'anneaux dit isomorphisme chinois.

Donc, les images de $a$ sont celles telles que $a=\pm 1$ et le $b$ sont ceux qui vérifient $a(b+1)=0$. Il va me falloir réviser le théorème chinois je crois. Merci à tous en tout cas.



Edité 1 fois. La dernière correction date de l’an passé et a été effectuée par AD.

Liste des forums - Statistiques du forum

Total
Discussions: 136 283, Messages: 1 317 333, Utilisateurs: 23 995.
Notre dernier utilisateur inscrit Sylva.

---

Ce forum
Discussions: 5 041, Messages: 60 964.