Chiffrement Affine

Toborockeur
Toborockeur
dans Arithmétique
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.

Réponses

  • Fin de partie
    Fin de partie
    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$.
  • Fin de partie
    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$....
  • Toborockeur
    Toborockeur
    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.
  • claude quitté
    claude quitté
    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 ?
  • Toborockeur
    Toborockeur
    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.
  • claude quitté
    claude quitté
    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$.
  • Math Coss
    Math Coss
    La transformation en couples ?
    Claude Quitté a écrit:
    Utilisation d'un isomorphisme d'anneaux dit isomorphisme chinois.
  • Toborockeur
    Toborockeur
    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.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 30

ChaurienCidrolinGuegoMatricule_63biguine_equationgerard0pldx1stfjzestezorgzygomathique +19 Invités