L'exponentiation modulaire échoue pour un grand mod en C++

Question

C'est le code que j'utilise pour calculer (n^p)%mod. Malheureusement, il échoue pour les grandes valeurs de mod (dans mon cas mod = 10000000000ULL) lorsque je l'appelle de la méthode main(). Une idée; Pourquoi?

ull powMod(ull n, ull p, ull mod) { 
    ull ans = 1; 
    n = n%mod; 
    while(p) { 
     if(p%2 == 1) { 
      ans = (ans*n)%mod; 
     } 
     n = (n*n)%mod; 
     p /= 2; 
    } 
    return ans; 
} 

Ici, ull est un typedef pour unsigned long long.

Answer 1

Oui, vous pouvez le faire en C++. Comme d'autres l'ont souligné, vous ne pouvez pas le faire directement . En utilisant une petite goutte de la théorie des nombres, il est possible de décomposer le problème en deux sous-problèmes gérables.

Considérons d'abord que 10^10 = 2^10 * 5^10. Les deux facteurs sont en coprime, donc vous pouvez utiliser le Chinese remainder theorem pour trouver la puissance modulo 10^10 en utilisant les puissances modulo 2^10 et modulo 5^10.

Notez que dans le code suivant la magie valeurs u2 et u5 ont été trouvés avec l'Extended Euclidean Algorithm. Vous n'avez pas besoin de programmer cet algorithme vous-même, car ces valeurs sont constantes. J'utilise maxima et sa fonction gcdex, pour les calculer.

est ici la version modifiée:

typedef unsigned long long ull; 

ull const M = 10000000000ull; 

ull pow_mod10_10(ull n, ull p) { 
    ull const m2 = 1024; // 2^10 
    ull const m5 = 9765625; // 5^10 
    ull const M2 = 9765625; // 5^10 = M/m2 
    ull const M5 = 1024; // 2^10 = M/m5 
    ull const u2 = 841;  // u2*M2 = 1 mod m2 
    ull const u5 = 1745224; // u5*M5 = 1 mod m5 

    ull b2 = 1; 
    ull b5 = 1; 
    ull n2 = n % m2; 
    ull n5 = n % m5; 

    while(p) { 
    if(p%2 == 1) { 
     b2 = (b2*n2)%m2; 
     b5 = (b5*n5)%m5; 
    } 
    n2 = (n2*n2)%m2; 
    n5 = (n5*n5)%m5; 
    p /= 2; 
    } 

    ull np = (((b2*u2)%M)*M2)%M; 
    np += (((b5*u5)%M)*M5)%M; 
    np %= M; 
    return np; 
} 

Answer 2

L'un des problèmes possibles ici semble être que lorsque vous faites (a*b)%c, la partie a*b elle-même pourrait déborder, ce qui entraînerait une mauvaise réponse. Une façon de contourner cela est d'utiliser l'identité que

(a*b)%c 

est équivalent à

(a%c * b%c)%c 

Cela permettra d'éviter les débordements dans les multiplications intermédiaires ainsi.

Answer 3

Il semble que vous ne pouvez pas l'éviter.

Si mod est 10000000000ULL, en (a*b)%c dans votre programme, à la fois a et b sont plus petits que mod pour que nous les traitons comme 9999999999ULL, a*b sera 99999999980000000001, mais unsigned long long ne peut exprimer 2^64-1=18446744073709551615 < 99999999980000000001 de sorte que votre méthode sera débordement.

Answer 4

Votre ligne de code

n = (n*n)%mod; 

est exécuté de manière répétée. Tant que n est inférieur à mod, cela peut entraîner l'évaluation (mod-1) * (mod-1) à un moment donné.

Sur l'entrée n peut ne pas être si grand, mais la ligne de code mentionnée augmente n dans la boucle.