Calcul d'un modulo d'un tres grand nombre Fermé

Question

Bonjour,
J'ai fais une fonction qui permet de calculer un nombre avec un très grand exposant sur un grand modulo. Pour un système de cryptographie.

Voici ma fonction :

unsigned long long int puisd(int x, int y, int z)
{
    unsigned long long int res=1;
    while (y>0) {
        if ((y%2)==1) {
            res=(res*x)%z;
            y--;
        }
        else {
            x=(x*x)%z;
            y=(y/2);
        }
    }
    return res;
}

Donc x = le nombre en question, y = l'exposant, et z = le modulo.

Alors pour 17266^28549 modulo 94631, soit puisd(17266,28549,94631), il m'affiche : 27938.

Mais je sais pas comment prouver que mon résultat est correct : \. 
Donc ce serait pour demander si mon code est t-il bon ?

Merci d'avance, cya

fiddy · Answer

Salut,
Le résultat est incorrect. Le résultat est 93399.
Le C n'est pas très bon  en natif pour les calculs. Pour le genre d'opérations que tu veux faire, à toi d'implémenter les algorithmes pour calculer les puissances modulaires. Il y en a de performants. D'ailleurs, il doit sûrement exister des bibliothèques prêtes à l'emploi.
Cdlt

Trigor · Answer

Le probleme c'est que je dois utilisé la méthode "des carrées et multiplication", 

J'ai reesayer avec une fonction recurssive : 

int puisd(int x, int y, int z)
{
    if (y==0) return 1;
    if (y%2==0) return (puisd(x, y/2, z) * puisd(x, y/2, z))%z;
    if (y%2==1) return (x * puisd(x, y-1, z))%z;
    else return 0;
}

Fonctionne avec de petit nombre, mais sans succes avec les gros nombres : (
Je trouve 61934 avec cette fonction...

crypto · Answer

BONJOUR
cé un probleme résolu par des algorithmes dits de l'exponentiation modulaire je te conseille de chercher sur internet sur ce terme. une nuite de multiplications et de carrés pour trouver le résultat final.
mais en pratique ce sont des grands nombres par exemple au minimum 1024 bits pour le RSA et tu dois pouvoir multiplier 2 nombres je te conseille de voir des algorithmes comme MONTGOMERY cé pratique. et tu peux utliser GMP cé pratique aussi.
bon courage

Calcul d'un modulo d'un tres grand nombre

3 réponses

Discussions similaires

Newsletters