Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
151 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Chiffrement Affine

Envoyé par Toborockeur 
Chiffrement Affine
il y a deux années
avatar
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 il y a deux années et a été effectuée par Toborockeur.
Re: Chiffrement Affine
il y a deux années
avatar
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 il y a deux années et a été effectuée par Fin de partie.
Re: Chiffrement Affine
il y a deux années
avatar
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)
Re: Chiffrement Affine
il y a deux années
avatar
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.
Re: Chiffrement Affine
il y a deux années
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 ?
Re: Chiffrement Affine
il y a deux années
avatar
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 il y a deux années et a été effectuée par AD.
Re: Chiffrement Affine
il y a deux années
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$.
Re: Chiffrement Affine
il y a deux années
La transformation en couples ?
Citation
Claude Quitté
Utilisation d'un isomorphisme d'anneaux dit isomorphisme chinois.
Re: Chiffrement Affine
il y a deux années
avatar
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 il y a deux années et a été effectuée par AD.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 138 374, Messages: 1 343 357, Utilisateurs: 24 821.
Notre dernier utilisateur inscrit wilno.


Ce forum
Discussions: 5 134, Messages: 62 234.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page