Exponentiation modulaire en Java

Question

Je besoin d'un moyen de calculer:

(g^u * y^v) mod p

en Java.

J'ai trouvé cet algorithme de calcul (g ^ u) mod p:

int modulo(int a,int b,int c) {
    long x=1
    long y=a;
    while(b > 0){
        if(b%2 == 1){
            x=(x*y)%c;
        }
        y = (y*y)%c; // squaring the base
        b /= 2;
    }
    return (int) x%c;
}

et il fonctionne très bien, mais je ne peux pas sembler trouver un moyen de le faire pour

(g^u * y^v) mod p

que mes compétences en mathématiques sont atone.

Pour mettre en contexte, il est pour une implémentation java d'un « réduit » DSA -. La partie vérification exige que cela soit résolu

Answer 1

En supposant que les deux facteurs ne débordera pas, je crois que vous pouvez simplifier une expression comme celle de cette façon:

(x * y) mod p = ( (x mod p)*(y mod p) ) mod p. Je suis sûr que vous pouvez le comprendre à partir de là.

Answer 2

Ce fragment de code implémente le bien connu de l'algorithme « exponentiation rapide », également connu sous le nom Exponentiation en élevant au carré .

Elle utilise également le fait que (a * b) mod p = ((a mod p) de * (b mod p)) mod p. (Les deux additions et multiplications sont conservées structures sous prenant un module premier - c'est un homomorphisme). De cette façon, à chaque point de l'algorithme réduit à un nombre plus petit que p.

Alors que vous pourriez essayer de calculer ces de manière entrelacée dans une boucle, il n'y a pas de réel avantage à le faire. Il suffit de les calculer séparément, les multiplier ensemble, et de prendre une dernière fois mod.

Soyez averti que vous aurez débordement si p ^ 2 est supérieure à la plus grande int représentable, et que cela vous risquez d'avoir une mauvaise réponse. Pour Java, le passage à grand entier peut être prudent, ou au moins faire un contrôle d'exécution de la taille de p et lancer une exception.

Enfin, si cela est à des fins de chiffrement, vous devriez probablement utiliser une bibliothèque pour ce faire, plutôt que de vous-même la mise en œuvre. Il est très facile de faire quelque chose un peu mal qui semble fonctionner, mais offre peu ou pas de sécurité.

Answer 3

Essayez

  

(Math.pow (q, u) * Math.pow (y, v))% p