Modulo de très grands nombres
Résolu
tomsawyer1311
Messages postés
375
Date d'inscription
Statut
Membre
Dernière intervention
-
tomsawyer1311 Messages postés 375 Date d'inscription Statut Membre Dernière intervention -
tomsawyer1311 Messages postés 375 Date d'inscription Statut Membre Dernière intervention -
A voir également:
- Modulo de très grands nombres
- Code binaire des nombres - Guide
- Nombre de jours entre deux dates excel - Guide
- Nombres faciles - Télécharger - Outils professionnels
- Citez un des logiciels lui permettant de faire des calculs sur des tableaux de nombres (tableur). - Forum Excel
- Modulo 97 ✓ - Forum Excel
7 réponses
La bibliothèque gmp est faite pour ca.
Pour savoir l'utiliser:
https://openclassrooms.com/fr/courses
Sheeps.
Pour savoir l'utiliser:
https://openclassrooms.com/fr/courses
Sheeps.
enfin si tu le fais en C++, après, normalement, pour calculer ce genre de nombre tu peux programmer un algorithme d'exponentiation rapide:
Par exemple pour 72^137, tu décompose 137 en puissance de 2, ce qui donne:
128+8+1
Ensuite vu que c'est de la criptographie, tu devra faire modulo un nombre et bah tu le fera au fur et à mesure de ton exponentiation rapide. Si tu fais mod 5 par exemple. (Je vais pas mon compliquer la vie avec de grands nombres ^^), ca donne:
72^1 % 5 = 72 % 5 = 2
72^2 % 5 = 2^2 % 5 = 4
72^4 % 5 = 4^2 % 5 = 1
Bon la je tombe sur 1, ca va me simplifier la vie, vu que 1^2 = 1 donc 72^8 =1 et 72^128 = 1 (en fait toutes les puissances de 2 d'après)
=> tu reprend ton nombres avec les nouvelles valeur:
Tu sais que 72^137 = 72^(128+8+1) = 72^128 * 72^8 * 72^1
Ce qui modulo 5 = 1 * 1 * 2 = 2
Voilà, bon la j'ai choisi des valeurs faciles pour pas m'emm****er mais si tu n'as pas compris dis-le moi et je ferrais avec un nombre plus grand.
Par exemple pour 72^137, tu décompose 137 en puissance de 2, ce qui donne:
128+8+1
Ensuite vu que c'est de la criptographie, tu devra faire modulo un nombre et bah tu le fera au fur et à mesure de ton exponentiation rapide. Si tu fais mod 5 par exemple. (Je vais pas mon compliquer la vie avec de grands nombres ^^), ca donne:
72^1 % 5 = 72 % 5 = 2
72^2 % 5 = 2^2 % 5 = 4
72^4 % 5 = 4^2 % 5 = 1
Bon la je tombe sur 1, ca va me simplifier la vie, vu que 1^2 = 1 donc 72^8 =1 et 72^128 = 1 (en fait toutes les puissances de 2 d'après)
=> tu reprend ton nombres avec les nouvelles valeur:
Tu sais que 72^137 = 72^(128+8+1) = 72^128 * 72^8 * 72^1
Ce qui modulo 5 = 1 * 1 * 2 = 2
Voilà, bon la j'ai choisi des valeurs faciles pour pas m'emm****er mais si tu n'as pas compris dis-le moi et je ferrais avec un nombre plus grand.
Bon allez, je t'ai fais le début mais c'est bien parce que je suis au taff hein ... ^^
#include <stdio.h>
int main(int argc,char **argv)
{
int nombre, exposant, modulo;// le nombre décomposé en 3
int i,j; // les itérateurs nécessaires
const int TAILLE = 100; //ca devrais suffire
int tableau[TAILLE]; //tableau pour stocker la décomposition en puissance de 2
printf("nombre? :");
scanf("%d", &nombre);
printf("\nexposant? :");
scanf("%d", &exposant);
printf("\nmodulo? :");
scanf("%d", &modulo);
i=1;
while( i < modulo) //pour prendre la plus grande des puissances de 2
{
i = i*2;
}
if (i != modulo)
i = i/2; // mais inférieure au nombre quand meme donc une itération en moins
j = 0;
while(modulo > 0) //décomposition en puissance de 2
{
if(modulo >= i)
{
tableau[j] = i;
j++;
modulo = modulo - i;
i = i/2;
}
else
{
i = i/2;
}
}
//bon là tu as ta décomposition dans le tableau et tableau[0] est le plus grand, ce qui sera ton marqueur de fin pour l'exponentiation rapide
return 0;
}
Ce n'était pas la peine de me commencer un programme, mais c'est gentil quand même merci. En fait, j'apprends ce langage assez complexe je trouve. Il y a certaines choses que je maîtrise assez (variables, conditions et boucles) d'autres où j'y travaille (les pointeurs surtout).
Là, c'est juste que je voulais tester l'algo RSA sur papier, or je pensais que mon ordi me remplacerait haut la main en ce qui concerne les calculs.
Mais, je vais lire ton code. Ca me fera progresser.
Là, c'est juste que je voulais tester l'algo RSA sur papier, or je pensais que mon ordi me remplacerait haut la main en ce qui concerne les calculs.
Mais, je vais lire ton code. Ca me fera progresser.
Mouais, j'ai fais ca parce que je m'ennuyais, après le code n'est pas vraiment utile. Pour tout te dire, ce que j'ai fais c'est seulement pour décomposer l'exposant en puissance de 2, ce qui est beaucoup moins long dans une application précise qu'en traitant avec des variables.
Le plus important, c'est le raisonnement mathématique de mon premier post, ne t'attardes pas sur ce morceau de code ;).
Le plus important, c'est le raisonnement mathématique de mon premier post, ne t'attardes pas sur ce morceau de code ;).
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Bon, ça fonctionne pas. En fait si mais, ça me mets le nombre long le plus élevé. Je vais réessayer avec des double ça devrait être possible.
Bon, alors je pensais avoir trouvé la solution mais non.
J'ai utilisé la fonction fmod() qui avait l'air de bien fonctionner.
J'ai fait un test avec : 3 ^ 45 % 13433.
D'après le programme : 3 ^ 45 = 2954312706550833610752
D'après la calculatrice d'Ubuntu : 3 ^ 45 = 2 954 312 706 550 833 698 643
Ensuite, 3 ^ 45 % 13433 donne :
dans le programme : 819
dans la calculatrice : 8112.
C'est pas très mathématiques tout ça. Je taquine bien entendu.
J'ai utilisé la fonction fmod() qui avait l'air de bien fonctionner.
J'ai fait un test avec : 3 ^ 45 % 13433.
D'après le programme : 3 ^ 45 = 2954312706550833610752
D'après la calculatrice d'Ubuntu : 3 ^ 45 = 2 954 312 706 550 833 698 643
Ensuite, 3 ^ 45 % 13433 donne :
dans le programme : 819
dans la calculatrice : 8112.
C'est pas très mathématiques tout ça. Je taquine bien entendu.
Pour les puissances de 3 :
Remarque : pour avoir le chiffre des unités d'une multiplication, il suffit de multiplier les chiffres des unités des deux nombres :
1265877467 * 6385864633 finit comme 3*7, c'est à dire par 1. Il suffit de poser la multiplication comme pour la faire à la main, et c'est évident
commence par 3 puissance 0 ->1
tu multiplies par 3 ->3 finit par 3
tu multiplies par 3 -> 9 finit par 9
tu multiplies par 3-> 27 finit par 7
tu multiplies par 3 -> finira comme 3*7 = 21 -> par 1
tu multiplies par 3 -> finira comme 3*1 -> par 3
et ça continue 9,7,1,3,9,7...
Remarque : pour avoir le chiffre des unités d'une multiplication, il suffit de multiplier les chiffres des unités des deux nombres :
1265877467 * 6385864633 finit comme 3*7, c'est à dire par 1. Il suffit de poser la multiplication comme pour la faire à la main, et c'est évident
commence par 3 puissance 0 ->1
tu multiplies par 3 ->3 finit par 3
tu multiplies par 3 -> 9 finit par 9
tu multiplies par 3-> 27 finit par 7
tu multiplies par 3 -> finira comme 3*7 = 21 -> par 1
tu multiplies par 3 -> finira comme 3*1 -> par 3
et ça continue 9,7,1,3,9,7...