Discuter:Rivest Shamir Adleman
Un article de Wikipédia, l'encyclopédie libre.
 |
Rivest Shamir Adleman fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser. |
| B | Cet article a été classé comme d'Avancement B selon le Tableau d'évaluation du projet. |
| Moyenne | Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet. (Contester?) |
J'ai un problème avec la ligne.
Or 
, d'après le théorème d'Euler.
Le x sort de nulle part. D'après le contexte, on devrait le remplacer par un M. Mais pourquoi M serait-il premier avec n (pour qu'on puisse appliquer Euler)? PierreL 31 mai 2006 à 13:53 (CEST)
M n'a aucune raison d'être premier avec n a priori. Mais comme n est le produit de deux premiers, il y a peu de chances pour que M ne soit pas premier avec n. Plus précisément, il y a exactement p+q-1 nombres non premiers avec n. Si p et q sont de l'ordre de 
, la probabilité pour que M ne soit pas premier avec n est de l'ordre de 
. Pour n de 1000 bits, soit de l'ordre de 10100, ça fait une chance plus que faible.
Au pire, l'expéditeur peut vérifier que M n'est pas premier avec n (en temps logarithmique, ça ne pose pas de problème), et redemander un n et un e différents si ce n'est pas le cas... Mais ça m'étonnerait :)
PS : tout ceci n'est qu'hypothétique, je n'y connais rien, mais c'est ce qui me semble raisonnable (je m'étais posé la même question :)). (Rnlabra, le 25 juillet 2006).
- La démonstration présentée est effectivement fausse si M n'est pas premier avec n. Néanmoins on peut montrer que
lorsque M n'est pas premier avec n. (Yves, le 21/09/2006)
