Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Équations différentielles : un Cours complet avec des exemples
- Ensemble et application Partie II
- Ensemble et application Partie I
- Espaces vectoriels et Applications linéaires - supérieur
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... LicenceMaths 2e/3e a ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau LicenceMaths 2e/3e a
protocole RSA
Posté par bouri
Bonjour à tous,
une question de cryptographie/arithmétique que je n'arrive pas à résoudre :
Si on connait M3 modulo n1, M3 modulo n2, M3 modulo n3 avec n1, n2 et n3 sans facteur commun premier, comment réussir à trouver M?
Peut être avec le théorème des restes chinois?
Merci d'avance pour vos réponses
Avec le théorème des restes chinois on arrive à trouver M3 modulo n1n2n3 mais après comment en déduire M?
Euh en fait, je ne comprend pas pourquoi dans ce cas on ne cherche pas directement M en faisant la table des cubes modulo juste n1 (ou n2 ou n3)?
ben tu peux aussi chercher l'ensemble des m tels que :
m^3 = a [n_1]
m^3 = b [n_2]
m^3 = c [n_3]
pus prendre leur intersection ...
mais de toute façon chercher à résoudre m^n = x [p] revient d'abord à connaitre m^n [p] ... qui se fait généralement avec un tableur ...
Le truc est que M est inférieur à n1,n2 et n3 donc M^3 < (n1 n2 n3) alors à la fin c'est une racine cubique ordinaire, pas modulaire, qu'on fait.
Même si les nombres sont très grands, une racine cubique ordinaire (dans N) se calcule asse vite sur ordinateur.
quand on travaille avec des modulos il n'y a pas de racine cubique ordinaire tout comme il n'y a pas de division : il y a des inverses et il il y a des nombres dont le cube est ... ce qu'on veut !!!
en particulier il peut y avoir plusieurs ""racine cubique"" !!!
Oui je sais bien, mais ici c'est une situation particulière, à cause de ce que j'ai mentionné, on peut utiliser l'algorithme habituel pour extraire une racine cubique d'un entier, c'est pour çà que c'est une attaque réalisable en pratique. Si on devait extraire une racine cubique modulo un très grand entier, ca ne serait pas faisable en pratique à cause des grands entiers utilisés habituellement.