Répondre à la discussion
Affichage des résultats 1 à 11 sur 11

modulo



  1. #1
    carl159

    Question modulo

    Bonjour,
    j'ai : d*517 = k*((p-1)(q-1)) + 1
    comment fait-on pour trouver d ?
    est-ce qu'il existe plusieurs valeurs de d ?
    k est-il une valeur unique ou il y a plusieurs possibilités et quelle est la méthode pour la trouver ?
    Merci.

    -----


  2. Publicité
  3. #2
    ericcc

    Re : modulo

    C'est quoi p et q ?
    Pour d=1 il y a une solution évidente, de même avec p=q=2 ....

  4. #3
    carl159

    Re : modulo

    p=29 et q=31

  5. #4
    Gwyddon

    Re : modulo

    Mets sous la forme d*x + k*y = z

    (x,y,z connus, k et d inconnus). C'est la forme classique des équations diophantiennes du 1er degré.

    Ensuite, cherche le pgcd de x et y ; si z n'est pas divisible par ce dernier, c'est foutu il n'y a pas de solution. Sinon, tu divises, puis tu résouds en utilisant la méthode classique avec l'algo d'Euclide + théorème de Gauss
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  6. #5
    Pole

    Re : modulo

    d=1/517 mod (p-1)*(q-1)
    On peut utiliser l'algorithme d'Euclide modifié.
    lien
    Ca sent le RSA....

    Pole.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  7. A voir en vidéo sur Futura
  8. #6
    kron

    Re : modulo

    Exa...
    A ce propos, je voulais savoir, y a t-il une méthode simple pour inverser l'exposant public dans Z/nZ*, sans passer par les équations diophantiennes ?
    Life is music !

  9. Publicité
  10. #7
    rvz

    Re : modulo

    Tu serais pas en train de poser la question "Est ce que c'est facile de casser le RSA ?" par hasard.

    Si c'est le cas, la réponse est non, car casser le RSA revient à trouver la décomposition en facteur premier de n, et, même si les algorithmes pour faire ça sont très simples théoriquement, ils sont néanmoins très très lourds informatiquement.

    __
    rvz

  11. #8
    kron

    Re : modulo

    Pas exactement.
    Ma question est juste de savoir s'il existe un algorithme rapide permettant, connaissant p,q,n,e de trouver d...
    ...
    ...
    Oui en fait c'est ça, comment casser RSA en connaissant la factorisation de n...

    Théoriquement, le calcul ne demande qu'un temps polynômial, non ? C'est "pas si long"...
    Life is music !

  12. #9
    rvz

    Re : modulo

    Ah ok.
    Si tu connais tous tes paramètres, pour inverser d dans Z/(p-1)(q-1)Z, comme a dit Pole, on sait le faire, via des algorithmes d'Euclide, reposant essentiellement sur la division euclidienne et la relation de Bezout.

    Par contre, pour la factorisation d'un entier, c'est très compliqué. Si tu te donnes un N, la seule manière de aire, c'est de tester par tous les nombres plus petit que, mettons, sa racine. Or la racine de N est bien expontielle en la taille des données ie log(N).

    Cela dit, il existe des algorithmes probabilistes qui te disent si un nombre est premier avec une bonne probabilité. Cf test de Miller Rabbin et trucs du même genre : Je me souviens du livre très clair de Michel Demazure à ce sujet, intitulé Cours d'Arithmétique.

    __
    rvz

  13. #10
    kron

    Re : modulo

    et sans utiliser l'algorithme d'euclide et Bézout ?
    Y a t-il une altenative, même utilisant des outils mathématiques plus avancés ?
    Life is music !

  14. #11
    Pole

    Re : modulo

    Pourquoi chercher compliqué?
    L'algorithme d'Euclide (pour a et b) fait O(log en base phi(minimun de a et b)) étapes.
    (phi est le nombre d'or,(1+sqrt(5))/2)~1.618033)
    On peut l'améliorer en prenant des restes qui peuvent être négatifs.
    La complexité est toujours <= à l'algo d'Euclide, et son maximun est O(log en base 2(minimun de a et b)).
    Je pense qu'on peut l'appliquer à l'algo d'Euclide modifié.
    Ces algorithmes sont très rapides (par rapport à Rabin-Miller) et peuvent être appliqués rapidement jusqu'à environ 1000 chiffres.

    Pour la factorisation, Peter Shor a trouvé un algo polynomial .... mais qui marche que sur des ordis quantiques.
    Pour ton ordi, j'ai utilisé dans l'autre fil sur le RSA mon code en java (lien ici), ce qui m'a permis de factoriser ce nombre de 60 chiffres en 1100 secondes à 1.7 GHz. L'algorithme utilisé est le MPQS (Multi Polinomial Quadratic Sieve), pour le crible quadratique c'est trop long.
    Je rapelle le record de factorisation pour un nombre du RSA : 200 chiffres.


    Pole.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

Sur le même thème :

Discussions similaires

  1. Equation, modulo 4
    Par bastien90210 dans le forum Mathématiques du collège et du lycée
    Réponses: 12
    Dernier message: 10/10/2007, 20h38
  2. modulo
    Par dim756 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 31/08/2007, 20h47
  3. inverse du modulo
    Par dolmen dans le forum Mathématiques du collège et du lycée
    Réponses: 11
    Dernier message: 07/01/2007, 19h57
  4. Formule de modulo
    Par Hachem dans le forum Mathématiques du supérieur
    Réponses: 17
    Dernier message: 14/12/2006, 17h28
  5. fonction modulo
    Par Brumaire dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 06/11/2004, 11h06