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

[toutankhamon]

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é /!\

[invité576543]

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,

[jobherzt]

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.

[toutankhamon]

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

[jobherzt]

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.

[invité576543]

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,

[toutankhamon]

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....