Activité sur le cryptage RSA: différents sous-cas ?

[Anonyme]

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

[Anonyme]

"Courbe paramétrique" 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".

[Anonyme]

C'est malheureusement ce à quoi nous incite notre énnoncé, en supposant
d'abord "a premier avec n" puis "a=rp" avec 0 a écrit dans
le message de news:23pevv0rf5v8b821u31ubugdd5noi0ple6@4ax.com...
> "Courbe paramétrique" wrote:
>[color=green]
> >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[/color]
pq=n[color=green]
> >
> >- 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[/color]
entiers[color=green]
> >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[/color]
cette[color=green]
> >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".
>[/color]

[Anonyme]

"Courbe paramétrique" wrote:

>C'est malheureusement ce à quoi nous incite notre énnoncé, en supposant
>d'abord "a premier avec n" puis "a=rp" avec 0...
>Merci de votre réponse.
>
Alors lisez ceci, ca répond à la question jej pense:
http://groups.google.com/groups?hl=fr&lr=&ie=UTF-8&th=670702f86b9fad3a&rnum=1