Histoire des codes secrets, page 474

[lionmarron]

A la page 474 de l'Histoire des codes secrets de Simon Singh (dans
l'édition du Livre de Poche), on trouve ceci :

7 * d = 1 (mod 160)

suivit de :

d = 23

Je ne parviens pas à voir ce que ça peut vouloir dire. Entre
parenthèses on trouve ceci (Déduire la valeur de d n'est pas immédiat,
mais l'algorithme d'Euclide [etc...]).

Quel que soit n, quelqu'un peut-il m'expliquer les choses suivantes :

-- que veut dire 1 (mod n) ?

-- Et y a t-il une différence avec 1 mod n ?

Merci pour vos réponses.

AH

[l***@NOSPAMlaposte.net]

Post by lionmarron
A la page 474 de l'Histoire des codes secrets de Simon Singh (dans
7 * d = 1 (mod 160)
d = 23

7 * 23 = 161 = 1 + 160 = 1 mod 160

Post by lionmarron
-- que veut dire 1 (mod n) ?

1 mod n désigne tous les entiers de la forme 1 + k*n, k entier
relatif, ou encore les entiers dont le reste dans la division par n
vaut 1

Post by lionmarron
-- Et y a t-il une diff=E9rence avec 1 mod n ?

non


Lavau Gérard

[Philippe 92]

Post by l***@NOSPAMlaposte.net

Post by lionmarron
A la page 474 de l'Histoire des codes secrets de Simon Singh (dans
7 * d = 1 (mod 160)
d = 23
-- que veut dire 1 (mod n) ?

1 mod n désigne tous les entiers de la forme 1 + k*n, k entier
relatif, ou encore les entiers dont le reste dans la division par n
vaut 1

Bonjour,

Post by l***@NOSPAMlaposte.net

Post by lionmarron
Entre parenthèses on trouve ceci (Déduire la valeur de d n'est
pas immédiat, mais l'algorithme d'Euclide [etc...]).

<http://fr.wikipedia.org/wiki/Algorithme_d'Euclide_%C3%A9tendu>

"L'algorithme d'Euclide étendu est une variante de l'algorithme
d'Euclide qui permet, à partir de deux entiers a et b, de calculer
non seulement leur plus grand commun diviseur (PGCD), mais aussi
un de leurs couples de coefficients de Bézout (deux entiers u et v
tels que au + bv = PGCD(a, b)).
Quand a et b sont premiers entre eux, u est alors l'inverse pour
la multiplication de a modulo b, ce qui est un cas particulièrement
utile."

En effet si a*u + b*v = 1 cela veut dire que a*u = 1 mod b

Amicalement.

[lionmarron]

Merci pour cette réponse et pour celle de lavau.

Je n'ai pas encore compris ce qu'expliquait Simon Singh (il s'agit de
la procédure de chiffrement RSA), mais ce n'est peut-être pas assez
trivial pour que je puisse comprendre d'emblée.

AH