Bonjour tout le monde. Auriez vous une méthode (pas trop complexe ) permettant de calculer assez rapidement des choses comme :
 
8^46 (mod 40)
 
J'ai en fait besoin d'un outils dans ce genre car je débute en cryptage RSA, et j'aimerai vérifier que ma clef privée trouvé par factorisation est la bonne et me donne le bon résultat.
 
Merci  

up

Méthode Egytienne.. Des que la puissance est trop grande pour la calculatrice

C'est pas vraiment évident à appliquer sur des problèmes de congruence modulo n. Mais merci pour ta réponse

Pour autant que je me souvienne, la congruence conserve la somme et la puissance, cad que a = p [n] et b = q [n] => a + b = p + q [n] et a = p [n] => a^k = p^k [n]. (remplacer les signes égal par un signe congrue à, évidemment).

Sinon y'a la façon simple : détecter des «patterns» (une texture, des séries qui reviennent quoi).

En l'occurrence, on voit que
8 = 8 [40]
8^2 = 24 [40]
8^3 = 32 [40]
8^4 = 16 [40]
8^5 = 8 [40]

Donc ça signifie que les congruences vont toutes être les mêmes par la suite.

Donc 8^45 = 8 [40]
et 8^46 = 32 [40]

Pour transformer ça en algorithme, tu peux essayer d'utiliser le moment ou tu trouves une congruence égale à ton nombre de départ (en général c'est comme ça qu'on trouve une boucle).

merci pour cette méthode, le problème c'est que je dois tout faire à la main (j'ai pas le droit à un pc pendant mes partiels )

la méthode de mahuf me parait bien, surtout à la main.

Au final, tu dois arriver à 2, et ça fait pas mal de boucle pour en arriver jusque la, car cela implique que l'on recommence avec 32[40] etc..

Je comprends pas vraiment ton dernier commentaire.
 
La difficulté c'est surtout de calculer les puissances de 8 puis de diviser, surtout si on trouve pas de série logique.
 
Sinon je crois qu'il y a un moyen de simplifier les congruences, mais je ne me rappelle plus laquelle.
 
La congruence passe à la multiplication et l'addition mais pas par la division ...
 
En fait, dès que tu retombes sur ton nombre de départ, un nombre déjà rencontré ou encore 0 ou 1, tu sais que tu tiens la solution.
 
Après, c'est une question de chance aussi ^^ mais les exos sont souvent faits pour que ça marche.

 
 
Ok excuse moi pour mon dernier commentaire, j'avais mal compris l'explication de ta méthode. Je vais tester sur des exemples, mais en fait elle m'a l'air pas mal du tout
 
Merci beaucoup!