L'Exponentiation modulaire en Java

J'ai besoin d'un moyen de calculer:

(g^u * y^v) mod p

en Java.

J'ai trouvé cet algorithme pour le calcul de 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 n'arrive pas à trouver un moyen de le faire pour

(g^u * y^v) mod p

que mes compétences en mathématiques sont médiocres.

Pour mettre en contexte, c'est pour une implémentation java d'une "réduction" de la DSA - la vérification de la nécessité de résoudre la question.

  • Je suppose que p est premier, non?
  • oui, p est premier, je pense que cela résout-il: (g^u * y^v) mod p = (g^u mod p) * (y^v mod p) mod p, bien que je ne l'ai testé avec de petits nombres jusqu'à présent
  • Et est-il grand? Le mod p partie s'intéresse à moi comme si vous vouliez l'utiliser BigInteger au lieu de long.
  • oui, p est grand (dans mon cas, 23929 pour être précis)
InformationsquelleAutor Carl Hagen | 2010-11-01