Aide sur modulo

[kcnarfou]

bonjour
je m'intéresse au calcul d'une clé RSA .
L'établissement de la clé est le suivant :

1- on choisit deux nombres premiers p = 3, q = 11 ;
2- leur produit n = 3 x 11 = 33 est le module de chiffrement ;
3- ;)(n) = (3-1) x (11-1) = 2 x 10 = 20 ;
4 -on choisit e= 3 (premier avec 20) comme exposant de chiffrement ;
5- l'exposant de déchiffrement est d = 7, l'inverse de 3 modulo 20 (en effet ed = 3 x 7 ;) 1 mod 20).

Pour ce dernier point (5) je ne comprends pas :
- quel est l'inverse d'un modulo
- le 3 modulo 20 .
Pour moi un modulo est le reste de la div Euclidienne donc par ex, 20 mod 3 = 2

merci de votre aide

[nodjim]

Si n est l'inverse de m modulo p, alors n.m=1 modulo p. Modulo p premier, tout nombre compris entre 1 et p-1 a un inverse mod p.

[Axiom]

Bonjour... :happy:

Tu peux aller voir aussi de ce côté pour comprendre davantage le principe de chiffrement RSA et l'inverse modulaire d'un nombre. :lol3:
=> Inverse modulaire
=> Chiffrement RSA

Mais selon moi Nodjin a parfaitement synthétisé le principal, l'inverse modulaire est très lié au théorème de Bachet-Bézout, et tu peux l'obtenir facilement à l'aide de l'algorithme étendu d'Euclide dont voici une version écrite en Java :

Code: Tout sélectionner

public static int[] euclide(int a, int b) {
   int[] result = new int[3];

   int r1 = a;
   int r2 = b;
   float u1 = 1;
   float v1 = 0;
   float u2 = 0;
   float v2 = 1;

   while (r2 != 0) {
      float q = r1 / r2;
      float rs = r1;
      float us = u1;
      float vs = v1;
      r1 = r2;
      u1 = u2;
      v1 = v2;
      r2 = Math.round(rs - q * r2);
      u2 = us - q * u2;
      v2 = vs - q * v2;
   }

   result[0] = Math.round(r1);
   result[1] = Math.round(u1);
   result[2] = Math.round(v1);

   return result;
}

public static int inverseEuclide(int a, int b) {
   int[] euclide = euclide(a, b);
   int result = euclide[1];

   if (result >= 0) {
      return result % b;
   } else {
      return (b - ((-result) % b));
   }
}

Ici, a est le nombre dont on cherche l'inverse modulaire et b, le modulo. Attention, ils doivent être premiers entre eux... :lol3:

Pour ce qui est du 3, il s'agit de la valeur de ton et le 20 est la valeur de ton .

En fait, on calcule ici l'inverse modulaire de par l'indicatrice d'Euler . :happy:

[mathelot]

quand on écrit



3 est le modulo et 2 est le résidu (de 20 modulo 3)

[kcnarfou]

merci mais je n'ai rien compris :cry:

[kcnarfou]

quand on écrit



3 est le modulo et 2 est le résidu (de 20 modulo 3)

oui merci . Ça j'avais saisi .

A partir de ça , comment calcule t'on le module inverse ?
Et 3 modulo 20 je ne comprends pas

[godzylla]

ça viendrais d'une fonction modulo utilisé en informatique qui peut trouver le reste d'une fraction et en même temps la valeur entière de la fraction.

la page wikipedia c'est du grand n'importe quoi, ils font exprès de ne pas expliquer? il y a presque une secte sur futura forum, il ne veulent pas que ce soit logique il faut que ce soit culturel. il se sont evadé de wOW ou d'un autre jeu de role de con ou il etais chevalier de monaco qui pense controler la france.

9 mod 4: c'est trouver pour 9 le dénominateur de sorte à obtenir une approximation par défaut. il y a pas de modulo pour les nombre inférieur à 1, c'est simplement les nombre réel et pas les entiers relatifs.

peut etre qu'un expert en logarithme népérien et exponentiel se serrai énervé pour utiliser cela sur modulo?

technique de mauvais prof de fac; ils ne font pas assez d'exercice et butine d'equations en equations pour trouver mieux.
exemple: l'inverse modulaire u de 3 modulo 11. comme si 3<11 ne posais pas de pbm
le medef dit que c'est un peut comme utiliser un airbus A 380 pour acheter son pain, c'est obligeant.
il semblerai que ce devienne du dessin a vouloir tout de suite utiliser la complexité en oubliant poids /masse
un fan d'ulysse 31 https://www.youtube.com/watch?v=vxlNw-vz7l8

[mathafou]

Bonjour,

l'inverse de 3 modulo 20

cette phrase, kcnarfou, tu la comprends complètement de travers
il ne s'agit pas de "l'inverse d'un modulo", ça ne veut rien dire, ça.

mais de l'inverse d'un nombre, de l'inverse du nombre 3
et en faisant toutes les opérations "modulo 20"
la découpe de la phrase est bien là "l'inverse de 3" forme un tout syntaxique
et "modulo 20" un autre


tout ça vient d'une compréhension erronée à la base de ce que veut dire "modulo" :

Pour moi un modulo est le reste de la div Euclidienne

non
le modulo est le diviseur dans la division Euclidienne
comme le dit godzylla :

ça viendrais d'une fonction modulo utilisé en informatique

tu confonds 43 mod 20 sur une calculette qui est une opération

et 43 3 mod 20 qui est une relation entre les nombres 43 et 3
relation qui exprime qu'ils ont le même reste dans la division euclidienne par 20 (par le "modulo")
PS : encore plus frappant comme distinction entre l'opération mod et la relation d'équivalence (congruence) modulo m :
43 23 63 -17 ... mod 20
parce que tous ces nombres ont même reste 3 dans la division euclidienne par 20
y compris -17 = (-1)*20 + 3, quotient -1, reste 3


par définition, l'inverse d'un nombre x est le nombre y qui multiplié par x donne 1

ici on cherche donc un nombre y qui multiplié par 3 donne 1, en faisant les opérations modulo 20
c'est à dire en ne considérant que les restes des nombres dans leur division par 20.

on "constate" (ou on trouve avec l'algorithme d'Euclide)
que 7*3 = 21
et comme 21 divisé par 20 à pour reste 1 : que l'on écrit 21 1 mod 20
les nombres 21 et 1 sont congrus (= équivalents) "modulo 20"

soit 7*3 = 21 1 mod 20

le nombre 7 est donc bien l'inverse de 3, par définition, modulo 20

et pour éviter toute confusion avec l'opération "mod" sur calculette , il est largement préférable d'écrire les "modulo" en mathématique entre crochets

3*7 1 [mod 20] ou simplement s'il n'y a pas de confusion 3*7 1 [20]
on "rappelle" (= entre crochets) que toutes les opérations se font "modulo 20", c'est à dire sur les restes de la division Euclidienne par 20

[godzylla]

Bonjour,

cette phrase, kcnarfou, tu la comprends complètement de travers
il ne s'agit pas de "l'inverse d'un modulo", ça ne veut rien dire, ça.

mais de l'inverse d'un nombre, de l'inverse du nombre 3
et en faisant toutes les opérations "modulo 20"
la découpe de la phrase est bien là "l'inverse de 3" forme un tout syntaxique
et "modulo 20" un autre


tout ça vient d'une compréhension erronée à la base de ce que veut dire "modulo" :

non
le modulo est le diviseur dans la division Euclidienne
comme le dit godzylla :
tu confonds 43 mod 20 sur une calculette qui est une opération

et 43 3 mod 20 qui est une relation entre les nombres 43 et 3
relation qui exprime qu'ils ont le même reste dans la division euclidienne par 20 (par le "modulo")

si tu le dit. j'aurai pas deviné, c'est la première fois que j'entends parler d'algèbre sans qu'il n'y ai besoin de longueur commune. il n'y a plus R?
je vais lire tout cela.

inverse si je me souviens étais enseigné en 2 nd ou 1 ere avec f(x)=1/x

il y aurai cette question de ax+by=1, il faut aimer le programme du lycée en math pour y trouver un sens.

il y a ces réponses aussi: http://www.les-mathematiques.net/phorum/read.php?5,874339,874955

j'ai bien compris, c'est donc de la logique combinatoire et pas une équation ou une formule de mathématiques. je me suis fait avoir a penser que cela pouvais servir de façon à calculer.
inverse n'est pas en rapport avec une fraction, c'est simplement une notation.
je suis déçu je m'attendais à un vrai savoir. si il y a une correspondance entre 1 et le dénominateur 20 pour obtenir 21 il faut l'ecrire de droite a gauche.

[nodjim]

On peut calculer l'inverse de a modulo b: il suffit de résoudre l'équation diophantienne ax-by=1. En trouvant x, tu auras bien ax=1 modulo b, et donc x sera l'inverse de a mod b.

[mathafou]

On peut calculer l'inverse de a modulo b: il suffit de résoudre l'équation diophantienne ax-by=1. En trouvant x, tu auras bien ax=1 modulo b, et donc x sera l'inverse de a mod b.

encore faut il découper les phrases correctement pour comprendre ce que cela veut dire :
(l'inverse de a) ,(mod b)
(ax=1), (modulo b) et pas (ax) = (1 modulo b)
"modulo b" est un seul élément indissociable, qui joue le role d'adjectif, et qui qualifie la sorte "d'égalité" que c'est
ce n'est pas une égalité mais une congruence, que l'on tolère d'écrire parfois "=" à tort, en tolérant la paresse de chercher le symbole spécial , lorsque la confusion est impossible, par exemple parce qu'on a écrit "modulo m"

ceci dit, parler d'équation diophantienne ici est un peu un marteau pilon pour écraser un moustique :
il suffit de connaitre sa table de 3 pour savoir quel multiple de 3 dépasse un multiple de 20 de une unité
(ce que veut dire exactement 3*7 1 [mod 20] : 3*7 est 1 de plus qu'un certain multiple de 20)
sinon oui, avec des valeurs plus grandes, on trouve ça ainsi (équation diophantienne et algorithme d'Euclide pour les résoudre)

pour rebondir sur le 1/x, "1/x" est une notation qui n'est valable que dans un corps
fondamentalement on a construit cela à partir de définitions, qui est réellement :
on appelle inverse de quelque chose A, le quelque chose B, lorsqu'il existe, tel que A*B = I
I l'élément "neutre" pour la multiplication, l'élément de l'ensemble tel que pour tout élément A on a ait A*I = I*A = A

on parle ainsi de l'inverse d'une matrice A, etc.

dans l'ensemble des nombres entiers, disons même dans Z, il n'y a pas d'inverses, sauf 1 (et aussi -1 dans Z) qui est l'inverse de lui même (1/2 n'est pas un nombre entier, ne fait pas partie de l'ensemble)
ici on considère un ensemble de "nombres" que l'on peut grâce à la congruence assimiler aux restes de la division par 20, dans lequel certains nombres (par exemple 3) possèdent un inverse, et d'autres pas (par exemple 2 n'a pas d'inverse)

[OY9151]

Bonjour ,

Ayant parcouru les réponses des uns et des autres et je crois avoir
compris que le problème principal de Kcnarfou est de la forme suivante:
CALCULER L'INVERSE D'UN ENTIER a MODULO UN ENTIER b ???

Si c'est cela alors on pourra toujours utiliser le schéma d'OURAGH. Ainsi
par exemple la recherche de l'inverse de 3 modulo 20 se fera comme suite

....20.......3........2........1
.....0......-6.......-1......
.............(7)........-1........1

Donc on relève bien que (7) est l'inverse de 3 modulo 20.
Un autre exemple: trouver l'inverse de 17 modulo 83. La schéma d'OURAGH
donnera

....83.........17........15.......2.........1
.....0.........-4.........-1......-7
..............(-39)........8......-7........1

d'où l'inverse de 17 modulo 83 est le nombre (-39) que l'on peut ramener
à (-39+83=44 ). On peut vérifier que reste de (44*17/83)=1
Cordialement.

[godzylla]

je n'aime pas trop qu'il soit utilisé modulo dans ce cas de figure. déjà que la fonction est presque impossible a programmer de façon a ce qu'elle soit utile. c'est meme utiliser les chiffres sans que se soit des nombres, ça deviens des lettres de caractère.

il faut que ce soit un tableau créé et comparé.

[OY9151]

Bonjour ,
et Knarfou avait pourtant posté
"A partir de ça , comment calcule t'on le module inverse ?
Et 3 modulo 20 je ne comprends pas"

et depuis rien. Si M. Knarfou les réponses vous intéresse toujours sachez
que par exemple la résolution de l'équation ( où le signe "=" se lit " est congru à")
13x=8[101] consistera à trouver le nombre c qui est l'inverse de 13 modulo 101 et
écrire x=8c[101]=......[101].

Cordialement.