Bonjour, dans le cadre d'une activité sur le cryptage RSA, l'ennoncé nous
amène à distinger deux sous-cas:
p et q sont, comme de coutumes, deux très grands nombres premiers avec pq=n
- un cas où a est premier avec n
- un second où a=rp avec r entier compris entre 0 et q.
Il s'agit, dans une question, de démontrer que POUR TOUT ENTIER NATUREL A
(et k), a^k(p-1)(q-1)+1 congru à a (mod n)
Voilà, le sujet est introduit ;)
Mon problème est le suivant, il réside en ce spectre très étendu des entiers
naturels a : les deux cas précédemments distingués sont, je pense, loin
d'être suffisants.
Quels autres cas pourraient être à distinguer pour la résolution de cette
question ?
D'avance, merci ;-)
Posted by: Sylvain Croussette
"Courbe paramétrique" <lunatique@free.fr> wrote:
>Bonjour, dans le cadre d'une activité sur le cryptage RSA, l'ennoncé nous
>amène à distinger deux sous-cas:
>
>p et q sont, comme de coutumes, deux très grands nombres premiers avec pq=n
>
>- un cas où a est premier avec n
>- un second où a=rp avec r entier compris entre 0 et q.
>
>Il s'agit, dans une question, de démontrer que POUR TOUT ENTIER NATUREL A
>(et k), a^k(p-1)(q-1)+1 congru à a (mod n)
>
>Voilà, le sujet est introduit ;)
>
>Mon problème est le suivant, il réside en ce spectre très étendu des entiers
>naturels a : les deux cas précédemments distingués sont, je pense, loin
>d'être suffisants.
>
> Quels autres cas pourraient être à distinguer pour la résolution de cette
>question ?
>
>D'avance, merci ;-)
>
Pour prouver que RSA marche, vous n'avez qu'à prouver que
a^[k(p-1)(q-1)+1] congru à a (mod p) où p est premier, c'est donc
aussi vrai mod q. Ensuite, c'est une conséquence du théorème des
restes chinois que a^[k(p-1)(q-1)+1] congru à a (mod pq). Vous n'avez
pas à traiter des "sous-cas".
Posted by: Courbe paramétrique
C'est malheureusement ce à quoi nous incite notre énnoncé, en supposant
d'abord "a premier avec n" puis "a=rp" avec 0<r<q
....
Merci de votre réponse.
"Sylvain Croussette" <NOzorglubSPAM_sylvaincroussette@yahoo.ca> a écrit dans
le message de news:23pevv0rf5v8b821u31ubugdd5noi0ple6@4ax.com...
> "Courbe paramétrique" <lunatique@free.fr> wrote:
>
> >Bonjour, dans le cadre d'une activité sur le cryptage RSA, l'ennoncé nous
> >amène à distinger deux sous-cas:
> >
> >p et q sont, comme de coutumes, deux très grands nombres premiers avec
pq=n
> >
> >- un cas où a est premier avec n
> >- un second où a=rp avec r entier compris entre 0 et q.
> >
> >Il s'agit, dans une question, de démontrer que POUR TOUT ENTIER NATUREL A
> >(et k), a^k(p-1)(q-1)+1 congru à a (mod n)
> >
> >Voilà, le sujet est introduit ;)
> >
> >Mon problème est le suivant, il réside en ce spectre très étendu des
entiers
> >naturels a : les deux cas précédemments distingués sont, je pense, loin
> >d'être suffisants.
> >
> > Quels autres cas pourraient être à distinguer pour la résolution de
cette
> >question ?
> >
> >D'avance, merci ;-)
> >
>
> Pour prouver que RSA marche, vous n'avez qu'à prouver que
> a^[k(p-1)(q-1)+1] congru à a (mod p) où p est premier, c'est donc
> aussi vrai mod q. Ensuite, c'est une conséquence du théorème des
> restes chinois que a^[k(p-1)(q-1)+1] congru à a (mod pq). Vous n'avez
> pas à traiter des "sous-cas".
>
Posted by: Sylvain Croussette
"Courbe paramétrique" <lunatique@free.fr> wrote:
>C'est malheureusement ce à quoi nous incite notre énnoncé, en supposant
>d'abord "a premier avec n" puis "a=rp" avec 0<r<q
>...
>Merci de votre réponse.
>
Alors lisez ceci, ca répond à la question jej pense: http://groups.google.com/groups?hl=...6b9fad3a&rnum=1