RSA :/ - Page 1

Voilà, en essayant de casser RSA selon certaines contraintes (exercice donné par le prof), j'arrive au problème suivant:
m*14702^15 = 12677ˆ2692 mod 18721
QQn a une idée astuce, pour réduire la complexité du calcul?

merci

qu'est-ce que tu cherches à faire ? trouver m ?

oui

alors qu'est-ce qui te pose problème ? c'est de calculer les puissances, ou c'est de diviser par 14702^15 ?

calculer la puissance 2692:/

ben c'est pas un problème, tu peux le calculer en O(log(2692)) multiplications
http://en.wikipedia.org/wiki/Exponentiation_by_squaring

Sauf que je compte pas le programmer
Il n'y a pas d'autre astuce à par la methode barbare :/

ben utilise un logiciel pour le faire, c'est pas ça qui manque... (genre maple & co) ((mais du coup je comprends plus ce que ton topic vient faire dans "algorithmie" ))
et juste par curiosité c'est quoi la méthode barbare ?

Je n'ai pas ce genre de logiciel :/
Pour moi methode barbare = methode qui ne profite pas vraiment des maths (genre j'aurai pensé qu'il y avait qqc à faire avec ce modulo).
Enfin pas bien grave tout ca :/

j'ai absolument rien compris, mais si tu dis que c'est pas grave tant mieux

Pour simplifier le calcul de 12677ˆ2692 mod 18721, je crois qu'il faut regarder du coté des classes d'équivalences (il me semble que j'avais fais un exo identique en math, quand on étudiait ça)
(edit: il faut peut être utiliser le fait que 12677 et 18721 sont premiers entre eux)

je vois pas très bien ce que ça peut apporter ça servirait si 12677 était plus grand que 18721 (pour le ramener mod 18721), mais sinon non ^^
sinon il suffit de poser x = 12677^21 [18721], et alors 12677^2692 = (x²²²²².x)²² [18721]

tp rendu ! je verai bien la solution, et je la posterai!
thx

le 12677ˆ2692 mod 18721 ça se calcul très bien; on calcule un à un les 12677^n [18721]:
si 12677^(p-1) = b [18721], alors 12677^p = b*p[18721], on calcul le modulo, et on recommence. De cette manière on reste avec des nombres relativement petits (on peut aussi faire 12677 = 7x1811, et le faire pour chacun )

Comme on est faignasse: (mais c'est relativement inutile ici si t'a de quoi faire tourner un algo )
A un moment on va tomber sur 12677^k=1[18721], et là il suffit de faire une division euclidienne de 2692 par k. (puisque le résultat va être cyclique )

Avec un petit algo du genre:

int r = 12677;
int i=1;
while (r != 1) {
r = (r * 12677)%18721;
i++;
}
return i;

On trouve directement i=192, donc 12677^(2692) [18721] = 12677^(192*28+4) [18721] = 1.12677^4 [18721] = 13145.
ça se fait en une ligne de Ti-basic.. (et ça s'apprend en Term spé maths il me semble )

Par contre, ta première partie de l'équation me semble bizzard.. (m n'est pas du tout entier ? )

on peut aussi se rendre compte que i=192 suffit sans faire de programme : 18721 = 97*193, donc comme modulo 193 les x inversibles vérifient x^192 = 1 et modulo 97 x^192 = (x^96)² = 1, modulo 18721 tous les x inversibles sont tels que x^192 = 1

et m est entier : c'est toute l'équation qui est mod 18721 ^^

.Ouais enfin sortir du petit théorème de Fermat (ou du théorème d'Euler / Carmichael, tant qu'a faire, c'est quand même plus esthétique de toucher réellement aux groupes cycliques plutôt que de balancer le petit thm de Fermat ), ça rend p-t la chose légèrement moins accessible

.ok

qui dit RSA dit petit théorème de Fermat, donc bon... (ah oui apparemment c'est la fonction de Carmichael, je connaissais pas ^^ menfin bon c'est ni plus esthétique ni moins esthétique puisque c'est rigoureusement la même démonstration)

Spe-Maths, oulà ca commence à dater :P
Enfin merci pour l'explication