Bonjour,
Je recherche une méthode rapide pour calculer, à la main :
5^13 modulo 55
Moi j'ai trouvé 15 en faisant une boduille mais je suis que ca marche
pas (pas respecter le modulo)
Merci de votre aide
Vieille histoire de modulos :)
14 messages
- Page 1 sur 1
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
Ben ...
5^1 = 5 [55]
5^2 = 25 [55]
5^3 = 5*25 = 125 = 15 [55]
5^4 = 5*15 = 75 = 20 [55]
5^5 = 5*20 = 100 = -10 [55]
5^10 = (5^5)^2 = (-10)^2 = 100 = -10 [55]
5^13 = 5^10 * 5^3 = -150 = 15 [55]
5^1 = 5 [55]
5^2 = 25 [55]
5^3 = 5*25 = 125 = 15 [55]
5^4 = 5*15 = 75 = 20 [55]
5^5 = 5*20 = 100 = -10 [55]
5^10 = (5^5)^2 = (-10)^2 = 100 = -10 [55]
5^13 = 5^10 * 5^3 = -150 = 15 [55]
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
On peut aussi utiliser la méthode "savante" :) qui utilise le petit
théorème de Fermat et le théorème des restes chinois:
5^13 mod 55 = (5^10)*(5^3) mod (11*5)
On décompose comme ceci:
(5^10)*(5^3) mod 11
(5^10)*(5^3) mod 5
Pour la première congruence:
(5^10)*(5^3) mod 11 = (5^10 mod 11) *(5^3 mod 11)
le premier terme à droite est égal à 1 selon Fermat donc il reste
5^3 = 4 mod 11
Pour la deuxième congruence, il est évident que c'est
5^13 = 0 mod 5
Finalement on recombine ces deux résultats avec le th. des restes
chinois, c.a.d. qu'on recherche un x tel que:
x=4 mod 11
x=0 mod 5
Par inspection on voit que ce plus petit x positif est bien x=15.
Mais je ne suis pas sûr que ce soit la méthode la plus rapide.
théorème de Fermat et le théorème des restes chinois:
5^13 mod 55 = (5^10)*(5^3) mod (11*5)
On décompose comme ceci:
(5^10)*(5^3) mod 11
(5^10)*(5^3) mod 5
Pour la première congruence:
(5^10)*(5^3) mod 11 = (5^10 mod 11) *(5^3 mod 11)
le premier terme à droite est égal à 1 selon Fermat donc il reste
5^3 = 4 mod 11
Pour la deuxième congruence, il est évident que c'est
5^13 = 0 mod 5
Finalement on recombine ces deux résultats avec le th. des restes
chinois, c.a.d. qu'on recherche un x tel que:
x=4 mod 11
x=0 mod 5
Par inspection on voit que ce plus petit x positif est bien x=15.
Mais je ne suis pas sûr que ce soit la méthode la plus rapide.
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
Par inspection ???
x = 4 modulo 11
x = 0 modulo 5
On résoud (avec Euclide)
5a = 1 modulo 11, a = 9, inverse de 5 modulo 11
11b = 1 modulo 5, b = 1 (quoique là, c'est immédiat)
et x = 4*5*a + 0*11*b modulo 55 (restes chinois)
soit x = 180 = 15 modulo 55
Tant qu'à faire, utiliser le marteau pilon jusqu'au bout...
--
philippe
(chephip at free dot fr)
x = 4 modulo 11
x = 0 modulo 5
On résoud (avec Euclide)
5a = 1 modulo 11, a = 9, inverse de 5 modulo 11
11b = 1 modulo 5, b = 1 (quoique là, c'est immédiat)
et x = 4*5*a + 0*11*b modulo 55 (restes chinois)
soit x = 180 = 15 modulo 55
Tant qu'à faire, utiliser le marteau pilon jusqu'au bout...
--
philippe
(chephip at free dot fr)
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
Je voulais dire visuellement, par essais et erreur, la deuxième
congruence nous dit que x doit être un multiple de 5, donc on essaie
5,10,15 dans la première congruence, voilà. Je voulais juste
mentionner cette méthode, c'est tout.
congruence nous dit que x doit être un multiple de 5, donc on essaie
5,10,15 dans la première congruence, voilà. Je voulais juste
mentionner cette méthode, c'est tout.
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
Sylvain Croussette a écrit :
> Philippe 92 dixit:
>[color=green]
>> Sylvain Croussette a écrit :
>> [ calcul de 5^13 modulo 55 ][/color]
....[color=green][color=darkred]
>>>
>>> Pour la deuxième congruence, il est évident que c'est
>>> 5^13 = 0 mod 5
>>>
>>> Finalement on recombine ces deux résultats avec le th. des restes
>>> chinois, c.a.d. qu'on recherche un x tel que:
>>> x=4 mod 11
>>> x=0 mod 5
>>>
>>> Par inspection on voit que ce plus petit x positif est bien x=15.
>>
>> Par inspection ???
>>[/color]
>
> Je voulais dire visuellement, par essais et erreur,[/color]
C'est bien ce que j'avais compris
Le théorème des restes chinois nous permet de *calculer* x,
sans aucun "essai et erreur", d'où ma remarque :
[color=green]
>> Tant qu'à faire, utiliser le marteau pilon jusqu'au bout...[/color]
--
philippe
(chephip at free dot fr)
> Philippe 92 dixit:
>[color=green]
>> Sylvain Croussette a écrit :
>> [ calcul de 5^13 modulo 55 ][/color]
....[color=green][color=darkred]
>>>
>>> Pour la deuxième congruence, il est évident que c'est
>>> 5^13 = 0 mod 5
>>>
>>> Finalement on recombine ces deux résultats avec le th. des restes
>>> chinois, c.a.d. qu'on recherche un x tel que:
>>> x=4 mod 11
>>> x=0 mod 5
>>>
>>> Par inspection on voit que ce plus petit x positif est bien x=15.
>>
>> Par inspection ???
>>[/color]
>
> Je voulais dire visuellement, par essais et erreur,[/color]
C'est bien ce que j'avais compris
Le théorème des restes chinois nous permet de *calculer* x,
sans aucun "essai et erreur", d'où ma remarque :
[color=green]
>> Tant qu'à faire, utiliser le marteau pilon jusqu'au bout...[/color]
--
philippe
(chephip at free dot fr)
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
Bertrand, as-tu déjà entendu parler de la fonction indicatrice d'Euler ?
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
Guillaume Yziquel wrote:
> Patrick Coilland wrote:
>[color=green]
>>
>> "Bertrand" a écrit dans le message de
>> news: 421473a7$0$1980$636a15ce@news.free.fr...
>>[color=darkred]
>>> Bonjour,
>>>
>>> Je recherche une méthode rapide pour calculer, à la main :
>>> 5^13 modulo 55
>>>
>>> Moi j'ai trouvé 15 en faisant une boduille mais je suis que ca marche
>>> pas (pas respecter le modulo)
>>> Merci de votre aide
>>
>>
>>
>> Ben ...
>> 5^1 = 5 [55]
>> 5^2 = 25 [55]
>> 5^3 = 5*25 = 125 = 15 [55]
>> 5^4 = 5*15 = 75 = 20 [55]
>> 5^5 = 5*20 = 100 = -10 [55]
>> 5^10 = (5^5)^2 = (-10)^2 = 100 = -10 [55]
>> 5^13 = 5^10 * 5^3 = -150 = 15 [55]
>>[/color]
>
> Bertrand, as-tu déjà entendu parler de la fonction indicatrice d'Euler ?[/color]
Bonsoir à toi, merci pour toutes ces réponses.
J'avais en fait trouvé la bonne réponse, mais ca posait un problème pour
un calcul de RSA... Mais j'ai m'étais planté dans mon algo.
Sinon, oui je connais la fonction (dzeta je crois ??). En fait, j'ai
fait prépa, ca fait 3 ans mnt, et je n'étais plus sur de mes calculs...
Mais j'apprécie toujours les maths !
Faudrait que je vienne plus souvent ici
Encore merci à tous
bonne soirée
> Patrick Coilland wrote:
>[color=green]
>>
>> "Bertrand" a écrit dans le message de
>> news: 421473a7$0$1980$636a15ce@news.free.fr...
>>[color=darkred]
>>> Bonjour,
>>>
>>> Je recherche une méthode rapide pour calculer, à la main :
>>> 5^13 modulo 55
>>>
>>> Moi j'ai trouvé 15 en faisant une boduille mais je suis que ca marche
>>> pas (pas respecter le modulo)
>>> Merci de votre aide
>>
>>
>>
>> Ben ...
>> 5^1 = 5 [55]
>> 5^2 = 25 [55]
>> 5^3 = 5*25 = 125 = 15 [55]
>> 5^4 = 5*15 = 75 = 20 [55]
>> 5^5 = 5*20 = 100 = -10 [55]
>> 5^10 = (5^5)^2 = (-10)^2 = 100 = -10 [55]
>> 5^13 = 5^10 * 5^3 = -150 = 15 [55]
>>[/color]
>
> Bertrand, as-tu déjà entendu parler de la fonction indicatrice d'Euler ?[/color]
Bonsoir à toi, merci pour toutes ces réponses.
J'avais en fait trouvé la bonne réponse, mais ca posait un problème pour
un calcul de RSA... Mais j'ai m'étais planté dans mon algo.
Sinon, oui je connais la fonction (dzeta je crois ??). En fait, j'ai
fait prépa, ca fait 3 ans mnt, et je n'étais plus sur de mes calculs...
Mais j'apprécie toujours les maths !
Faudrait que je vienne plus souvent ici
Encore merci à tous
bonne soirée
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
Bertrand a écrit :
> Guillaume Yziquel wrote:[color=green]
>> Patrick Coilland wrote:[color=darkred]
>>> "Bertrand" a écrit dans le message de news:
>>> 421473a7$0$1980$636a15ce@news.free.fr...
>>>
>>>> Je recherche une méthode rapide pour calculer, à la main :
>>>> 5^13 modulo 55
>>>
>>> Ben ...
>>> 5^1 = 5 [55]
>>> 5^2 = 25 [55]
>>> 5^3 = 5*25 = 125 = 15 [55]
>>> 5^4 = 5*15 = 75 = 20 [55]
>>> 5^5 = 5*20 = 100 = -10 [55]
>>> 5^10 = (5^5)^2 = (-10)^2 = 100 = -10 [55]
>>> 5^13 = 5^10 * 5^3 = -150 = 15 [55]
>>
>> Bertrand, as-tu déjà entendu parler de la fonction indicatrice d'Euler ?[/color][/color]
Mais ici il faut prendre quelques précautions car 5 n'est pas premier
avec 55
on ne peut donc pas écrire 5^phi(55) = 1 (mod 55) car c'est faux !
On commence avec 5^13 = a (mod 55) => a = 0 mod 5 et donc a = 5b
on peut alors simplifier par 5 la congruence 5^13 = 5b (mod 55) en
5^12 = b (mod 11) et là 5^phi(11) = 1 (mod 11)
(mais en fait c'est le petit théorème de Fermat car 11 est premier
et phi(11) = 10)
On peut donc "simplifier l'exposant modulo 10"
5^12 = 5^2 = 3 = b (mod 11)
et donc a = 5b = 15
Ce qui explique pourquoi le résultat 15 était déja là dans le calcul de
5^3,
5^13 = 5^3 (mod 55) bien que 5^10 != 1 (mod 55) !
> Bonsoir à toi, merci pour toutes ces réponses.
> J'avais en fait trouvé la bonne réponse, mais ca posait un problème pour un
> calcul de RSA... Mais j'ai m'étais planté dans mon algo.
Là dedans Fermat et phi(n) ca sert...
> Sinon, oui je connais la fonction (dzeta je crois ??).
traditionellement c'est phi(n)
dzeta(x) c'est autre chose... pour info :
dzeta(x) = 1 + 1/2^x + 1/3^x + 1/4^x + ... = sum (1/n^x, n= 1..infini)
Bonne soirée.
--
philippe
(chephip at free dot fr)
> Guillaume Yziquel wrote:[color=green]
>> Patrick Coilland wrote:[color=darkred]
>>> "Bertrand" a écrit dans le message de news:
>>> 421473a7$0$1980$636a15ce@news.free.fr...
>>>
>>>> Je recherche une méthode rapide pour calculer, à la main :
>>>> 5^13 modulo 55
>>>
>>> Ben ...
>>> 5^1 = 5 [55]
>>> 5^2 = 25 [55]
>>> 5^3 = 5*25 = 125 = 15 [55]
>>> 5^4 = 5*15 = 75 = 20 [55]
>>> 5^5 = 5*20 = 100 = -10 [55]
>>> 5^10 = (5^5)^2 = (-10)^2 = 100 = -10 [55]
>>> 5^13 = 5^10 * 5^3 = -150 = 15 [55]
>>
>> Bertrand, as-tu déjà entendu parler de la fonction indicatrice d'Euler ?[/color][/color]
Mais ici il faut prendre quelques précautions car 5 n'est pas premier
avec 55
on ne peut donc pas écrire 5^phi(55) = 1 (mod 55) car c'est faux !
On commence avec 5^13 = a (mod 55) => a = 0 mod 5 et donc a = 5b
on peut alors simplifier par 5 la congruence 5^13 = 5b (mod 55) en
5^12 = b (mod 11) et là 5^phi(11) = 1 (mod 11)
(mais en fait c'est le petit théorème de Fermat car 11 est premier
et phi(11) = 10)
On peut donc "simplifier l'exposant modulo 10"
5^12 = 5^2 = 3 = b (mod 11)
et donc a = 5b = 15
Ce qui explique pourquoi le résultat 15 était déja là dans le calcul de
5^3,
5^13 = 5^3 (mod 55) bien que 5^10 != 1 (mod 55) !
> Bonsoir à toi, merci pour toutes ces réponses.
> J'avais en fait trouvé la bonne réponse, mais ca posait un problème pour un
> calcul de RSA... Mais j'ai m'étais planté dans mon algo.
Là dedans Fermat et phi(n) ca sert...
> Sinon, oui je connais la fonction (dzeta je crois ??).
traditionellement c'est phi(n)
dzeta(x) c'est autre chose... pour info :
dzeta(x) = 1 + 1/2^x + 1/3^x + 1/4^x + ... = sum (1/n^x, n= 1..infini)
Bonne soirée.
--
philippe
(chephip at free dot fr)
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
On peut aussi utiliser la méthode "savante"
Je pinaille. Pour 55 on sait facilement faire 55=5x11.
Mais en général, décomposer un nombre en facteurs premiers n'a à priori
aucune raison d'être facile. Si on remplaçait 55 par
20583708274802734082735826208375802374812737502803785728037803572126164261921582052783562
et 13 par
13824782070874285780319328753208728037528037121062633857205728081912849829395267185702182807184
il me semble qu'il faille se résigner à faire une méthode "pas de géant,
pas de bébé" pour être efficace.
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
Guillaume Yziquel dixit:
>Sylvain Croussette wrote:[color=green]
>> "Patrick Coilland" dixit:
>>
>> On peut aussi utiliser la méthode "savante" qui utilise le petit
>> théorème de Fermat et le théorème des restes chinois:
>>
>> 5^13 mod 55 = (5^10)*(5^3) mod (11*5)
>
>Je pinaille. Pour 55 on sait facilement faire 55=5x11.
>Mais en général, décomposer un nombre en facteurs premiers n'a à priori
>aucune raison d'être facile. Si on remplaçait 55 par
>20583708274802734082735826208375802374812737502803785728037803572126164261921582052783562[/color]
= 2 * 3 * 107 * 7177 * 8505406151825711 *
525231285345396649639489814778353026386652686230322783356123383763
>et 13 par
>13824782070874285780319328753208728037528037121062633857205728081912849829395267185702182807184
= 2^4 * 3 * 11 * 97 * 839959 * 834793631981 *
384959837049896042705252898508505235019866600270886224072588526183573531
factorisés en 30 secondes sur mon vieux pentium-2 450 mhz. Bon
d'accord ce sont des mauvais exemples
>il me semble qu'il faille se résigner à faire une méthode "pas de géant,
>pas de bébé" pour être efficace.
Le message original parlait de calcul à la main, dans ce cas
évidemment c'est difficile à factoriser. Mais pour RSA, le
déchiffreur connait sa propre clé secrète et aussi les facteurs
premiers p et q du modulo qu'il n'a donc pas à factoriser, alors il
peut utiliser le théorème des restes chinois pour déchiffrer un
message, cette méthode diminue le travail à faire d'un facteur de 4 en
théorie. Dans le temps où je m'intéressais à RSA, tous les logiciels
qui l'implémentait utilisait cette méthode pour déchiffrer et signer
les messages.
Cependant si c'est un adversaire qui essaie de déchiffrer un message,
il ne connait pas les facteurs p et q et dans ce cas comme vous dites
cette méthode n'est pas utile en pratique.
>Sylvain Croussette wrote:[color=green]
>> "Patrick Coilland" dixit:
>>
>> On peut aussi utiliser la méthode "savante"
qui utilise le petit>> théorème de Fermat et le théorème des restes chinois:
>>
>> 5^13 mod 55 = (5^10)*(5^3) mod (11*5)
>
>Je pinaille. Pour 55 on sait facilement faire 55=5x11.
>Mais en général, décomposer un nombre en facteurs premiers n'a à priori
>aucune raison d'être facile. Si on remplaçait 55 par
>20583708274802734082735826208375802374812737502803785728037803572126164261921582052783562[/color]
= 2 * 3 * 107 * 7177 * 8505406151825711 *
525231285345396649639489814778353026386652686230322783356123383763
>et 13 par
>13824782070874285780319328753208728037528037121062633857205728081912849829395267185702182807184
= 2^4 * 3 * 11 * 97 * 839959 * 834793631981 *
384959837049896042705252898508505235019866600270886224072588526183573531
factorisés en 30 secondes sur mon vieux pentium-2 450 mhz. Bon
d'accord ce sont des mauvais exemples
>il me semble qu'il faille se résigner à faire une méthode "pas de géant,
>pas de bébé" pour être efficace.
Le message original parlait de calcul à la main, dans ce cas
évidemment c'est difficile à factoriser. Mais pour RSA, le
déchiffreur connait sa propre clé secrète et aussi les facteurs
premiers p et q du modulo qu'il n'a donc pas à factoriser, alors il
peut utiliser le théorème des restes chinois pour déchiffrer un
message, cette méthode diminue le travail à faire d'un facteur de 4 en
théorie. Dans le temps où je m'intéressais à RSA, tous les logiciels
qui l'implémentait utilisait cette méthode pour déchiffrer et signer
les messages.
Cependant si c'est un adversaire qui essaie de déchiffrer un message,
il ne connait pas les facteurs p et q et dans ce cas comme vous dites
cette méthode n'est pas utile en pratique.
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
Philippe 92 wrote:
> Bertrand a écrit :
>[color=green]
>> Guillaume Yziquel wrote:
>>[color=darkred]
>>> Patrick Coilland wrote:
>>>
>>>> "Bertrand" a écrit dans le message de
>>>> news: 421473a7$0$1980$636a15ce@news.free.fr...
>>>>
>>>>> Je recherche une méthode rapide pour calculer, à la main :
>>>>> 5^13 modulo 55
>>>>
>>>>
>>>> Ben ...
>>>> 5^1 = 5 [55]
>>>> 5^2 = 25 [55]
>>>> 5^3 = 5*25 = 125 = 15 [55]
>>>> 5^4 = 5*15 = 75 = 20 [55]
>>>> 5^5 = 5*20 = 100 = -10 [55]
>>>> 5^10 = (5^5)^2 = (-10)^2 = 100 = -10 [55]
>>>> 5^13 = 5^10 * 5^3 = -150 = 15 [55]
>>>
>>>
>>> Bertrand, as-tu déjà entendu parler de la fonction indicatrice d'Euler ?[/color]
>
>
> Mais ici il faut prendre quelques précautions car 5 n'est pas premier
> avec 55
> on ne peut donc pas écrire 5^phi(55) = 1 (mod 55) car c'est faux ![/color]
Ca c'est vrai. En tant qu'anneau, on a l'isomorphisme
Z/55Z isomorphe à Z/5Z X Z/11Z.
Quand on exponentie à la puissance phi(5), dans la partie Z/5Z on
obtient 0 ou 1 selon qu'on avait à faire à un iversible ou pas. Pareil
dans Z/11Z et phi(11).
Dans notre cas précis, 5^phi(55) ça va donner (0,1) dans Z/5Z X Z/11Z.
Ainsi calculer 5^(phi(55)+1) ça donne clairement 5 modulo 55.
Maintenant, en remarquant que 5 divise 55, on obtient 5^(phi(11)+1)
c'est 5. 5^11=5
5^13=5*25=125=15 modulo 55.
Ca a donc bien à voir avec la fonction indicatrice... même si
algorithmiquement, décomposer un nombre en facteur premiers n'est pas
une sinécure.
> On commence avec 5^13 = a (mod 55) => a = 0 mod 5 et donc a = 5b
> on peut alors simplifier par 5 la congruence 5^13 = 5b (mod 55) en
> 5^12 = b (mod 11) et là 5^phi(11) = 1 (mod 11)
> (mais en fait c'est le petit théorème de Fermat car 11 est premier
> et phi(11) = 10)
> On peut donc "simplifier l'exposant modulo 10"
> 5^12 = 5^2 = 3 = b (mod 11)
> et donc a = 5b = 15
> Ce qui explique pourquoi le résultat 15 était déja là dans le calcul de
> 5^3,
> 5^13 = 5^3 (mod 55) bien que 5^10 != 1 (mod 55) !
>[color=green]
>> Bonsoir à toi, merci pour toutes ces réponses.
>> J'avais en fait trouvé la bonne réponse, mais ca posait un problème
>> pour un calcul de RSA... Mais j'ai m'étais planté dans mon algo.
>
>
> Là dedans Fermat et phi(n) ca sert...
>
>> Sinon, oui je connais la fonction (dzeta je crois ??).
>
>
> traditionellement c'est phi(n)
>
> dzeta(x) c'est autre chose... pour info :
> dzeta(x) = 1 + 1/2^x + 1/3^x + 1/4^x + ... = sum (1/n^x, n= 1..infini)
>
> Bonne soirée.
>[/color]
> Bertrand a écrit :
>[color=green]
>> Guillaume Yziquel wrote:
>>[color=darkred]
>>> Patrick Coilland wrote:
>>>
>>>> "Bertrand" a écrit dans le message de
>>>> news: 421473a7$0$1980$636a15ce@news.free.fr...
>>>>
>>>>> Je recherche une méthode rapide pour calculer, à la main :
>>>>> 5^13 modulo 55
>>>>
>>>>
>>>> Ben ...
>>>> 5^1 = 5 [55]
>>>> 5^2 = 25 [55]
>>>> 5^3 = 5*25 = 125 = 15 [55]
>>>> 5^4 = 5*15 = 75 = 20 [55]
>>>> 5^5 = 5*20 = 100 = -10 [55]
>>>> 5^10 = (5^5)^2 = (-10)^2 = 100 = -10 [55]
>>>> 5^13 = 5^10 * 5^3 = -150 = 15 [55]
>>>
>>>
>>> Bertrand, as-tu déjà entendu parler de la fonction indicatrice d'Euler ?[/color]
>
>
> Mais ici il faut prendre quelques précautions car 5 n'est pas premier
> avec 55
> on ne peut donc pas écrire 5^phi(55) = 1 (mod 55) car c'est faux ![/color]
Ca c'est vrai. En tant qu'anneau, on a l'isomorphisme
Z/55Z isomorphe à Z/5Z X Z/11Z.
Quand on exponentie à la puissance phi(5), dans la partie Z/5Z on
obtient 0 ou 1 selon qu'on avait à faire à un iversible ou pas. Pareil
dans Z/11Z et phi(11).
Dans notre cas précis, 5^phi(55) ça va donner (0,1) dans Z/5Z X Z/11Z.
Ainsi calculer 5^(phi(55)+1) ça donne clairement 5 modulo 55.
Maintenant, en remarquant que 5 divise 55, on obtient 5^(phi(11)+1)
c'est 5. 5^11=5
5^13=5*25=125=15 modulo 55.
Ca a donc bien à voir avec la fonction indicatrice... même si
algorithmiquement, décomposer un nombre en facteur premiers n'est pas
une sinécure.
> On commence avec 5^13 = a (mod 55) => a = 0 mod 5 et donc a = 5b
> on peut alors simplifier par 5 la congruence 5^13 = 5b (mod 55) en
> 5^12 = b (mod 11) et là 5^phi(11) = 1 (mod 11)
> (mais en fait c'est le petit théorème de Fermat car 11 est premier
> et phi(11) = 10)
> On peut donc "simplifier l'exposant modulo 10"
> 5^12 = 5^2 = 3 = b (mod 11)
> et donc a = 5b = 15
> Ce qui explique pourquoi le résultat 15 était déja là dans le calcul de
> 5^3,
> 5^13 = 5^3 (mod 55) bien que 5^10 != 1 (mod 55) !
>[color=green]
>> Bonsoir à toi, merci pour toutes ces réponses.
>> J'avais en fait trouvé la bonne réponse, mais ca posait un problème
>> pour un calcul de RSA... Mais j'ai m'étais planté dans mon algo.
>
>
> Là dedans Fermat et phi(n) ca sert...
>
>> Sinon, oui je connais la fonction (dzeta je crois ??).
>
>
> traditionellement c'est phi(n)
>
> dzeta(x) c'est autre chose... pour info :
> dzeta(x) = 1 + 1/2^x + 1/3^x + 1/4^x + ... = sum (1/n^x, n= 1..infini)
>
> Bonne soirée.
>[/color]
Re: vieille histoire de modulos :)
par Anonyme » 30 Avr 2005, 18:19
Sylvain Croussette wrote:
> Guillaume Yziquel dixit:
>[color=green]
>>20583708274802734082735826208375802374812737502803785728037803572126164261921582052783562
>
> = 2 * 3 * 107 * 7177 * 8505406151825711 *
> 525231285345396649639489814778353026386652686230322783356123383763
>
>>et 13 par
>>13824782070874285780319328753208728037528037121062633857205728081912849829395267185702182807184
>
> = 2^4 * 3 * 11 * 97 * 839959 * 834793631981 *
>
> 384959837049896042705252898508505235019866600270886224072588526183573531
>
> factorisés en 30 secondes sur mon vieux pentium-2 450 mhz. Bon
> d'accord ce sont des mauvais exemples[/color]
Je sais pas pourquoi, mais j'étais persuadé que quelqu'un ferait ça. Par
contre pour 13, c'était pas la peine.
[color=green]
>>il me semble qu'il faille se résigner à faire une méthode "pas de géant,
>>pas de bébé" pour être efficace.[/color]
ou peut-être un peu raffiné.
> Le message original parlait de calcul à la main, dans ce cas
> évidemment c'est difficile à factoriser. Mais pour RSA, le
> déchiffreur connait sa propre clé secrète et aussi les facteurs
> premiers p et q du modulo qu'il n'a donc pas à factoriser, alors il
> peut utiliser le théorème des restes chinois pour déchiffrer un
> message, cette méthode diminue le travail à faire d'un facteur de 4 en
Ah bon. 4 ? Asymptotiquement, ou pratiquement ?
> théorie. Dans le temps où je m'intéressais à RSA, tous les logiciels
> qui l'implémentait utilisait cette méthode pour déchiffrer et signer
> les messages.
> Cependant si c'est un adversaire qui essaie de déchiffrer un message,
> il ne connait pas les facteurs p et q et dans ce cas comme vous dites
> cette méthode n'est pas utile en pratique.
On est donc bien d'accord.
> Guillaume Yziquel dixit:
>[color=green]
>>20583708274802734082735826208375802374812737502803785728037803572126164261921582052783562
>
> = 2 * 3 * 107 * 7177 * 8505406151825711 *
> 525231285345396649639489814778353026386652686230322783356123383763
>
>>et 13 par
>>13824782070874285780319328753208728037528037121062633857205728081912849829395267185702182807184
>
> = 2^4 * 3 * 11 * 97 * 839959 * 834793631981 *
>
> 384959837049896042705252898508505235019866600270886224072588526183573531
>
> factorisés en 30 secondes sur mon vieux pentium-2 450 mhz. Bon
> d'accord ce sont des mauvais exemples
[/color]Je sais pas pourquoi, mais j'étais persuadé que quelqu'un ferait ça. Par
contre pour 13, c'était pas la peine.
[color=green]
>>il me semble qu'il faille se résigner à faire une méthode "pas de géant,
>>pas de bébé" pour être efficace.[/color]
ou peut-être un peu raffiné.
> Le message original parlait de calcul à la main, dans ce cas
> évidemment c'est difficile à factoriser. Mais pour RSA, le
> déchiffreur connait sa propre clé secrète et aussi les facteurs
> premiers p et q du modulo qu'il n'a donc pas à factoriser, alors il
> peut utiliser le théorème des restes chinois pour déchiffrer un
> message, cette méthode diminue le travail à faire d'un facteur de 4 en
Ah bon. 4 ? Asymptotiquement, ou pratiquement ?
> théorie. Dans le temps où je m'intéressais à RSA, tous les logiciels
> qui l'implémentait utilisait cette méthode pour déchiffrer et signer
> les messages.
> Cependant si c'est un adversaire qui essaie de déchiffrer un message,
> il ne connait pas les facteurs p et q et dans ce cas comme vous dites
> cette méthode n'est pas utile en pratique.
On est donc bien d'accord.
par demco » 01 Juin 2005, 18:27
Vous êtes des cracks. Merci bcp à tous ceux qui participent à ce forum, vous n'imaginez pas à quel point votre aide est précieuse !
14 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 54 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :