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
41 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
l’an passé
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 l’an passé et a été effectuée par Toborockeur.
Re: Chiffrement Affine
l’an passé
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 l’an passé et a été effectuée par Fin de partie.
Re: Chiffrement Affine
l’an passé
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
l’an passé
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
l’an passé
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
l’an passé
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 l’an passé et a été effectuée par AD.
Re: Chiffrement Affine
l’an passé
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
l’an passé
La transformation en couples ?
Citation
Claude Quitté
Utilisation d'un isomorphisme d'anneaux dit isomorphisme chinois.
Re: Chiffrement Affine
l’an passé
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 l’an passé 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: 136 345, Messages: 1 318 050, Utilisateurs: 24 023.
Notre dernier utilisateur inscrit Etienne l’autre.


Ce forum
Discussions: 5 044, Messages: 61 006.

 

 
©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