Discuter:Rivest Shamir Adleman
Un article de Wikipédia, l'encyclopédie libre.
[modifier] Déchiffrement du message
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)
et sont vrais pour tout M (même si M multiple de p ou q). On conclut par les restes chinois. Cette remarque a été ajoutée par Sgsixhuit (d · c · b) le 5 janvier 2008
- La démonstration aujourd'hui dans l'article me semble non convaincante car trop compliquée. La démonstration proposée par Sgsixhuit est celle que l'on trouve généralement dans la littérature (livre de TS). Elle a le mérite de la simplicité et ne nécessite même pas l'allusion au théorème des restes chinois mais tout bêtement au théorème de Gauss : si A est multiple de p et q et si p et q sont premiers entre eux alors A est multiple de pq. Sauf avis contraire, je compte changer la dem dans les 8 jours. HB (d) 13 février 2008 à 21:41 (CET)
[modifier] Proposition de démo
- donc ed = k(p − 1)(q − 1) + 1
- Une généralisation du petit théorème de Fermat nous donne
, avec Φ(n) la fonction indicatrice d'Euler (qui correspond au nombre d'éléments de )
- Or, Φ(n) = (p − 1)(q − 1), d'où
- D'où