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'utiliserBigInteger
au lieu de long. - oui, p est grand (dans mon cas, 23929 pour être précis)
Vous devez vous connecter pour publier un commentaire.
En supposant que les deux facteurs ne seront pas de débordement, 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à.int
. Sinon, nous allons juste utiliserlong
s de x et y. Le faitCe fragment de code implémente le bien connu "exponentiation rapide" de l'algorithme, aussi connu comme L'Exponentiation par la quadrature.
Il utilise également le fait que (a * b) mod p = ((mod p) * (b mod p)) mod p. (À la fois l'addition et la multiplication sont des structures conservées sous la prise d'un premier module -- c'est un homomorphism). De cette façon, à chaque étape de l'algorithme, il se réduit à des nombres plus petits que p.
Alors que vous pourriez essayer de calculer ces entrelacée dans une boucle, il n'y a pas de réel avantage à le faire. Simplement calculer séparément, multiplions les ensemble, et de prendre le mod une dernière fois.
Être averti que vous obtiendrez de débordement si p^2 est plus grand que le plus grand représentable, de type int, et que cela va vous amener à avoir la bonne réponse. Pour Java, le passage à grand entier pourrait être sage, ou au moins faire un moment de l'exécution sur la taille de p et de lancer une exception.
Enfin, si c'est pour les fins, vous devriez probablement utiliser une bibliothèque pour ce faire, plutôt que de mettre en place vous-même. Il est très facile de faire quelque chose de mal qui semble fonctionner, mais fournit peu ou pas de sécurité.
Essayer