Modulo de très grands nombres

Résolu/Fermé

tomsawyer1311 Messages postés 375 Date d'inscription vendredi 1 mai 2009 Statut Membre Dernière intervention 8 novembre 2019 - 19 mai 2011 à 18:26
tomsawyer1311 Messages postés 375 Date d'inscription vendredi 1 mai 2009 Statut Membre Dernière intervention 8 novembre 2019 - 20 mai 2011 à 14:51

Bonjour tout le monde,

Alors, voilà, j'ai un souci qui, je croyais, était minime mais qui ne me fait pas avancer du tout.

Sur le site du zéro, il y a 2 tutoriels sur l'algorithme RSA (qui permet de générer des clés publiques et privées).

Je commence à lire ce tuto : http://www.siteduzero.com/tutoriel-3-2320-l-algorithme-rsa.html
et au moment de générer les clés problème.

Comme convenu je choisis p et q comme nombres premiers.
Pour bien comprendre et ne pas bêtement copier je choisis mes nombres premiers.
Avec p = 101 et q = 133.
Je lis que n = p x q soit n = 101 x 133 = 13433.
Et phi (n) = (p-1) x (q-1) soit phi (n) = 100 x 132 = 13200
Et e doit être strictement supérieur à p et q et le PGCD de phi (n) et e doit être égal à 1.
e = 137.
J'ai p = 101 ; q = 133 ; n = 13433 ; phi (n) = 13200 ; e = 137.

Pour coder on utilise e et n de cette façon :
ca^e % n = cc
avec ca : caractère en ASCII
% : modulo (le reste de la division euclidienne)
cc : caractère codé

Et là c'est le drame.
Alors que la calculatrice d'Ubuntu m'a parfaitement calculé des opérations simples voilà qu'elle peine avec les puissances et modulos de grands chiffres.

Je décide avec mon petit bagage en C de créer un programme pour calculer les puissances et modulo demandés.

Catastrophe, gcc (le compilateur que j'utilise) me jette littéralement à la gueule : "Tu m'emmerdes avec tes double, utilise des int."

Je m'exécute et ne mets que des int.
Problème, pas besoin d'être fin mathématicien pour savoir que 72^137 dépassera le nombre maximal qu'on peut avoir avec int (ou ses voisins proches, les unsigned int, long long int etc...)
(Oui, le message à coder est "Help !" et 72 est le code ASCII de "H")

Si une âme charitable veut bien m'aider à sortir de ce pétrin, je lui en serai reconnaissant.

<config>PC Portable Ubuntu 10.04 LTS, Mozilla Firefox 4>

A voir également:

Modulo de très grands nombres
Code binaire des nombres - Guide
Barbara veut calculer automatiquement son budget dans un tableau. citez un des logiciels lui permettant de faire des calculs sur des tableaux de nombres (tableur). - Forum Excel
En raison d'un nombre important d'échec de connexion snapchat - Forum Snapchat
Le nombre de tentatives de déverrouillage incorrectes est trop élevé samsung ✓ - Forum Samsung
Nombres faciles - Télécharger - Outils professionnels

7 réponses

Réponse 1 / 7

KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
19 mai 2011 à 19:07

Je te conseilles plutôt ce tutoriel dont la deuxième partie t'apprends à utiliser GMP en C

Réponse 2 / 7

cap'tain sheeps Messages postés 447 Date d'inscription jeudi 19 mai 2011 Statut Membre Dernière intervention 1 octobre 2014 10
20 mai 2011 à 09:09

La bibliothèque gmp est faite pour ca.
Pour savoir l'utiliser:
https://openclassrooms.com/fr/courses
Sheeps.

cap'tain sheeps Messages postés 447 Date d'inscription jeudi 19 mai 2011 Statut Membre Dernière intervention 1 octobre 2014 10
20 mai 2011 à 09:32

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.

cap'tain sheeps Messages postés 447 Date d'inscription jeudi 19 mai 2011 Statut Membre Dernière intervention 1 octobre 2014 10
Modifié par cap'tain sheeps le 20/05/2011 à 10:34

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;
}

cap'tain sheeps Messages postés 447 Date d'inscription jeudi 19 mai 2011 Statut Membre Dernière intervention 1 octobre 2014 10
20 mai 2011 à 10:10

Mouais, je me suis planté quelque part, je corrige ca...

tomsawyer1311 Messages postés 375 Date d'inscription vendredi 1 mai 2009 Statut Membre Dernière intervention 8 novembre 2019 24
20 mai 2011 à 12:25

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.

cap'tain sheeps Messages postés 447 Date d'inscription jeudi 19 mai 2011 Statut Membre Dernière intervention 1 octobre 2014 10
20 mai 2011 à 13:57

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 ;).

Réponse 3 / 7

ljm972 Messages postés 254 Date d'inscription vendredi 23 février 2007 Statut Membre Dernière intervention 6 décembre 2021 29
19 mai 2011 à 19:03

Salut,
utilise des long ( grand entrier )

Réponse 4 / 7

tomsawyer1311 Messages postés 375 Date d'inscription vendredi 1 mai 2009 Statut Membre Dernière intervention 8 novembre 2019 24
19 mai 2011 à 19:22

Ok, j'essaie ça.
Je t'en dis plus.

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question

Réponse 5 / 7

tomsawyer1311 Messages postés 375 Date d'inscription vendredi 1 mai 2009 Statut Membre Dernière intervention 8 novembre 2019 24
Modifié par tomsawyer1311 le 19/05/2011 à 21:38

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.

Réponse 6 / 7

tomsawyer1311 Messages postés 375 Date d'inscription vendredi 1 mai 2009 Statut Membre Dernière intervention 8 novembre 2019 24
19 mai 2011 à 22:27

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.

tomsawyer1311 Messages postés 375 Date d'inscription vendredi 1 mai 2009 Statut Membre Dernière intervention 8 novembre 2019 24
19 mai 2011 à 22:37

J'ai testé le résultat donné par le programme de 3 ^ 45 soit 2954312706550833610752
Je l'ai copié dans la calculatrice et fait le modulo 13433.
Ca me donne bien : 819.

Je pense que "mon" programme est bon mais très mal optimisé. De toute façon ce n'est pas le but.

le père
19 mai 2011 à 22:44

Bonjour
Pas besoin d'être fin mathématicien pour voir que 3 ^ 45 = 2954312706550833610752 est faux.
Une puissance entière de 3 se termine par 1,3,9 ou 7.
Suis le conseil de KX et utilise une bibliothèque faite pour manipuler les nombres avec un nombre arbitraire de chiffres significatifs.

tomsawyer1311 Messages postés 375 Date d'inscription vendredi 1 mai 2009 Statut Membre Dernière intervention 8 novembre 2019 24
19 mai 2011 à 22:47

J'ai du mal à te suivre concernant les puissances de 3.
En ce qui concerne la lecture du tuto conseillé par KX j'y compte beaucoup évidemment.

le père
19 mai 2011 à 23:06

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...

tomsawyer1311 Messages postés 375 Date d'inscription vendredi 1 mai 2009 Statut Membre Dernière intervention 8 novembre 2019 24
19 mai 2011 à 23:18

Merci beaucoup pour ton explication le père. J'avais testé sur la calculatrice mais comme tu l'écris c'est parfait.
Bon je vous laisse.
Pourvu que la nuit me porte conseil.

Ciao
Tom

Réponse 7 / 7

tomsawyer1311 Messages postés 375 Date d'inscription vendredi 1 mai 2009 Statut Membre Dernière intervention 8 novembre 2019 24
20 mai 2011 à 14:51

Alors, grâce à cap'tain sheeps et KX surtout, j'ai résolu le problème, enfin GMP a résolu mon problème.

Je vais pouvoir continuer l'apprentissage de cet algorithme.

Merci beaucoup.

Ciao
Tom

Discussions similaires

modulo C/C++

modulo 97

la fonction modulo en c++

MODULO EN C++

logiciel pour tableau