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

Factorisation d un nombre premier sous la forme P=(x-1)(y-1) (x,y deux nombres premiers)




  1. #1
    toutankhamon

    Factorisation d un nombre premier sous la forme P=(x-1)(y-1) (x,y deux nombres premiers)

    Bonjour...

    Je suis sur un site qui propose des cryptogrammes a décoder et je suis en ce moment sur un message RSA...

    Il me faut donc décomposer 157 en un facteur de 2 nombres premiers auquel on retranche 1

    autrement dit:

    x , y deux nombres premiers

    157=(x-1)(y-1)

    Aprés avoir fait des recherches sur internet , je pense avoir trouvé les outils mathématiques nécéssaires...
    Mais malheureusement mon niveau mathématiques ne suis pas


    D'aprés mes recherches il faut utiliser le petit théoréme de fermat ou bien sa généralisation avec Euler...

    Mais pour le coup je seche comme une vielle bouse au soleil

    Merci d'avance et bonne journée

    /!\ je ne cherche pas a avoir la solution mais seulement une piste qui me permette d'avancé /!\

    -----


  2. Publicité
  3. #2
    invité576543
    Invité

    Re : Factorisation d un nombre premier sous la forme P=(x-1)(y-1) (x,y deux nombres premiers)

    Déjà, on pourrait enlever le premier "premier" dans le titre, ça ferait un peu plus sérieux

    Ensuite, tu as dû te tromper aussi dans l'énoncé, parce que la seule solution à (x-1)(y-1) impair avec x et y premiers est x=y=2

    Cordialement,

  4. #3
    jobherzt

    Re : Factorisation d un nombre premier sous la forme P=(x-1)(y-1) (x,y deux nombres premiers)

    Accessoirement 157 est lui meme premier, donc ca va etre difficile...

    Et comme le dit michel, si x et y sont premiers impairs, alors x-1 et y-1 sont pairs, donc (x-1)(y-1) est multiple de 4.


  5. #4
    toutankhamon

    Re : Factorisation d un nombre premier sous la forme P=(x-1)(y-1) (x,y deux nombres premiers)

    Merci de vos reponses rapides
    jai du raté un truc ^^


    le principe du RSA c'est


    Alice choisit deux grands entiers naturels premiers p et q (d'environ 100 chiffres chacun ou plus) et fait leur produit n = p·q. Puis elle choisit un entier e premier avec (p-1)·(q-1). Enfin, elle publie dans un annuaire, par exemple sur le web, sa clef publique: (RSA, n, e).

    Pour déchiffrer il me faut :


    Pour déchiffrer: Entrez, en plus de e, n et la taille des blocs, la valeur de d

    la crypto me donne :

    n = 1487932939581322413763429 et e = 157

    et on a

    taille des blocs:

    il découpe son message chiffré en blocs de même longueur représentant chacun un nombre plus petit que n
    la clef d:

    la clef d de déchiffrage (c'est sa clef privée). Celle-ci doit satisfaire l'équation e·d mod ((p-1)(q-1)) = 1
    je pensais que
    Puis elle choisit un entier e premier avec (p-1)·(q-1).
    signifiait e=(p-1)(q-1)

    enfin bref plus je reflechis plus je m embrouille
    mais je me rends compte de mon erreur de vouloir décomposer un nombre premier hum......

    Tous les quotes ont été extraits du site apprendre en ligne
    Dernière modification par toutankhamon ; 10/12/2008 à 11h35.

  6. #5
    jobherzt

    Re : Factorisation d un nombre premier sous la forme P=(x-1)(y-1) (x,y deux nombres premiers)

    C'est bien ce qu'il me semblait

    Bon, "e premier avec (p-1)(q-1)" veut simplement dire que le seul diviseur commun de e et de (p-1)(q-1) est 1. Le moyen le plus simple d'en trouver un, c'est justement de prendre un nombre premier, et en general on ne le choisit pas trop grand, vu qu'il est public.

    A priori, et c'est bien tout l'interet de RSA comme systeme de cryptage, le seul moyen de trouver p et q c'est de factoriser n. Ce qui avec un logiciel adapté se fait en un quelques millisecondes. J'ai la reponse sous les yeux si ca t'interresse, sinon je te laisse chercher.

  7. A voir en vidéo sur Futura
  8. #6
    invité576543
    Invité

    Re : Factorisation d un nombre premier sous la forme P=(x-1)(y-1) (x,y deux nombres premiers)

    Citation Envoyé par toutankhamon Voir le message
    je pensais que signifiait e=(p-1)(q-1)
    Non, c'est tout le contraire. e n'a pas de facteur en commun avec (p-1)(q-1).

    Par exemple, pour n = 35, (p-1)(q-1)=24, et e=11 serait acceptable.


    Par ailleurs, e t'est donné. Ce qu'on te demande c'est de trouver d, c'est à dire "attaquer" la méthode de chiffrement.

    C'est facile, parce que n est petit et aisément factorisé par des logiciels courants...

    Ensuite, une fois trouvés p et q, d se calcule par des algorithmes classiques (c'est le coefficient de Bezout de e pour le pgcd de e et (p-1)(q-1) )

    Cordialement,

  9. #7
    toutankhamon

    Re : Factorisation d un nombre premier sous la forme P=(x-1)(y-1) (x,y deux nombres premiers)

    merci une nouvelle fois pour vos réponse rapide et claires

    Jobhertz merci d'avoir gardé le silence mais si a noel je n'est toujours pas déchiffré ce cryptogramme je t'enverrai un MP pour que tu me donne le nom du programme utilisé

    Et merci a toi aussi Michel

    Me vas partir a la recherche du programme de factorisation....

  10. Publicité

Sur le même thème :

Discussions similaires

  1. Factorisation d'un nombre premier
    Par WizartS dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 11/04/2009, 22h53
  2. deux nombres premiers entre eux
    Par codepvc dans le forum Mathématiques du supérieur
    Réponses: 19
    Dernier message: 26/11/2008, 17h35
  3. Le GIMPS a trouvé DEUX nouveaux nombres de Mersenne premiers :
    Par T.Rex dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 07/09/2008, 20h58
  4. Deux nombres premiers entre eux
    Par Universmaster dans le forum Mathématiques du collège et du lycée
    Réponses: 22
    Dernier message: 09/12/2007, 17h22
  5. Record : deux nouveaux nombres premiers jumeaux découverts !
    Par RSSBot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 1
    Dernier message: 18/01/2007, 14h48