Langage C#
  1. Langage C#
  3. Calculer le module d’un nombre à une puissance certan (le nombre à cette puissance est assez grand)
Intereting Posts
Existe-t-il un moyen de passer un TVP à dapper sur .Net Core maintenant? Quelle version de .NET Framework et C # dois-je cibler avec ma bibliothèque de classes? Générer un nombre aléatoire dans une plage gaussienne? Que signifie “DisplayClass” lorsque vous appelez lambda? Comment partager des données entre différents threads En C # en utilisant AOP? En C #, comment collecter une trace de stack d’un programme bloqué IEnumerable comme type de retour pour les méthodes WCF Comment convertir un tableau d’octets en tableau UInt32? LINQ TO XML, Comment remplacer des valeurs par de nouvelles valeurs c # Comment valider si un élément parent a des enfants dans la fonction LINQ récursive? Maintenir le focus de contrôle sur les posts à l’aide de PostBackOptions.TrackFocus Contrôle de BackgroundWorker et WebBrowser Pourquoi l’access à un PerformanceCounter provoque-t-il des collectes de mémoire de gen2? Pourquoi Action / Func est-il meilleur qu’une méthode classique en .Net? c # – décale à gauche un tableau d’octets entier

Calculer le module d’un nombre à une puissance certan (le nombre à cette puissance est assez grand)

Je veux calculer l’algorithme RSA par moi-même. J’ai besoin de calculer le module d’un nombre à une certaine puissance. Le fait est que ce nombre à ce pouvoir peut devenir assez grand.

Voici ce que je veux: 

x = pow(n, p) % q

Comment puis-je déterminer efficacement x?

Si vous utilisez .NET 4, je vous suggère de regarder BigInteger , qui fournit même la méthode ModPow pour tout faire en une seule opération 🙂 

 BigInteger n = ...; BigInteger p = ...; BigInteger q = ...; BigInteger x = BigInteger.ModPow(n, p, q);

Ceci est connu comme la fonction powermod : 

 function modular_pow(base, exponent, modulus) c := 1 for e_prime = 1 to exponent c := (c * base) mod modulus return c

Ceci peut être rendu plus efficace en appliquant une exponentiation en quadrillant: 

 function modular_pow(base, exponent, modulus) result := 1 while exponent > 0 if (exponent & 1) equals 1: result = (result * base) mod modulus exponent := exponent >> 1 base = (base * base) mod modulus return result

Veuillez vérifier ce sujet et cet article sur les moyens de rendre la fonction mathématique plus efficace en soi.

Voir BigInteger.ModPow (Fx 4+), voici le MSDN .

Trivialement … 

 x = 1 for(i = 0; i < p; i++) x = (x*n) % q

Il existe des moyens plus efficaces, tels que l’exponentiation binary, plutôt que cette itération naïve, mais le problème de dépassement de capacité n’est pas dépassé car x est lié par n * q

Bien que toutes les réponses fournies ici soient correctes, j’ai oublié l’algorithme évident du carré et de la multiplication, qui constitue la méthode “classique” de mise en oeuvre de l’exposition modulaire.

Si vous envisagez d’écrire votre propre version de Modpow() :

Vous n’avez besoin que du modulo de puissance q, vos calculs ne doivent donc pas utiliser un nombre supérieur à q^2 , en utilisant le fait que: 

 if a = b (mod q) then a*p = b*p (mod q)

Par conséquent, lors du calcul de la puissance n^p , après chaque multiplication, effectuez une opération (modulo q) sur votre variable de travail.

De plus, si q est premier, vous pouvez utiliser le petit théorème de Fermat, qui stipule que: 

 a^(q-1) = 1 (mod q) (when a is not a multiple of q)

Ceci peut être utilisé pour raccourcir les calculs lorsque p est (beaucoup) plus grand que q