Putere rapidă, modulo și invers modular în C++

Ridicarea rapidă la putere calculează a la exponentul b folosind descompunerea binară a exponentului. În aritmetica modulară păstrăm numai restul la împărțirea cu m, ceea ce permite rezultate utile chiar dacă puterea completă este uriașă.

Împărțirea modulară cere însă atenție: nu împărțim pur și simplu resturile. Pentru a împărți prin a modulo m avem nevoie de un invers modular, iar acesta există exact când a și m sunt prime între ele.

Cum funcționează

Dacă exponentul este par, a^b=(a²)^(b/2). Dacă este impar, separăm un factor a și tratăm exponentul rămas. În varianta iterativă, result acumulează factorii necesari, a se ridică la pătrat, iar b se înjumătățește. La fiecare pas, produsul matematic result·a^b rămâne congruent cu puterea inițială modulo m.

Operațiile de adunare și înmulțire pot fi reduse modulo m după fiecare pas. Reducerea nu elimină însă riscul de overflow înaintea operatorului %. Programul presupune 2 <= m <= 1000000000, astfel încât produsul a două resturi încape în long long. Exponentul este între zero și un miliard, iar baza are modulul cel mult un miliard. Normalizăm resturile negative prin (a%m+m)%m.

Pentru invers folosim algoritmul lui Euclid extins. El găsește coeficienți x,y astfel încât a·x+m·y=gcd(a,m). Dacă gcd este unu, relația devine a·x congruent cu 1 modulo m, deci x normalizat este inversul. Dacă gcd este diferit de unu, inversul nu există și afișăm explicit acest fapt.

În apelul recursiv avem b·u+(a%b)·v=g. Înlocuind a%b cu a-(a/b)·b obținem x=v și y=u-(a/b)·v. Această deducție explică actualizarea coeficienților; schimbarea ordinii lor fără relația algebrică produce rezultate aparent plauzibile, dar greșite. Coeficienții pot fi negativi și trebuie stocați într-un tip cu semn.

Exemplu urmărit pas cu pas

Pentru 3^5 modulo 7, pornim cu result=1. Bitul impar al exponentului introduce factorul 3; baza devine 2 modulo 7 și exponentul 2. Următorul pas păstrează result, apoi baza devine 4 și exponentul 1. Ultima înmulțire produce 3·4 modulo 7, adică 5.

Inversul lui 3 modulo 7 este 5, deoarece 3·5=15 lasă restul 1. În schimb, 6 nu are invers modulo 9, deoarece gcd(6,9)=3. Puterea modulară există în ambele cazuri; inexistența inversului nu împiedică ridicarea la putere.

Implementare C++17

#include <iostream>
long long power(long long a, long long b, long long m) {
    a = (a % m + m) % m;
    long long result = 1 % m;
    while (b > 0) {
        if (b % 2 == 1)
            result = result * a % m;
        a = a * a % m;
        b /= 2;
    }
    return result;
}
long long extended(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long u, v;
    long long g = extended(b, a % b, u, v);
    x = v;
    y = u - (a / b) * v;
    return g;
}
int main() {
    long long a, b, m;
    std::cin >> a >> b >> m;
    std::cout << power(a, b, m) << '\n';
    long long x, y, normalized = (a % m + m) % m;
    if (extended(normalized, m, x, y) != 1)
        std::cout << "NU EXISTA\n";
    else
        std::cout << (x % m + m) % m << '\n';
}

De ce funcționează și cât costă

Înjumătățirea exponentului păstrează invariantul puterii și ajunge la zero, când result este răspunsul. Euclid extins păstrează identitatea lui Bézout la fiecare revenire; pentru gcd=1 aceasta furnizează direct inversul.

Puterea rapidă folosește O(log b) înmulțiri și O(1) memorie. Euclid extins are O(log m) pași în limitele problemei și folosește stivă recursivă de aceeași ordine. Aceste estimări consideră operațiile pe întregi de dimensiune fixă.

Greșeli frecvente

Nu folosi pow în virgulă mobilă pentru puteri modulare exacte. Nu presupune că a^(m-2) este invers pentru orice modul: formula respectivă cere condițiile teoremei lui Fermat, inclusiv modul prim și bază nenulă modulo el. Nu aplica % cu modul zero.

Exersează

Calculează inversul lui 5 modulo 12 și explică de ce există, deși 12 nu este prim.

Rezolvare explicată: gcd(5,12)=1, iar 5·5=25 este congruent cu 1 modulo 12. Inversul este 5; primalitatea modulului nu este necesară pentru criteriul general.

Continuă să înveți

Euclid, baze de numerație și recursivitate.

Întrebări frecvente

De ce exponentul zero produce unu?

Produsul fără factori este unu. În program inițializăm result cu 1 modulo m; convenția este declarată inclusiv pentru baza zero în această operație algoritmică.

De ce restul unei baze negative se normalizează?

În C++, restul poate fi negativ când operandul din stânga este negativ. Adăugarea modulului și o nouă reducere aduc rezultatul în intervalul 0..m-1.

Când există invers modular?

Exact când baza și modulul sunt prime între ele. Identitatea lui Bézout oferă atât criteriul, cât și metoda de calcul.

Pot împărți două resturi cu operatorul /?

Nu în general. Împărțirea modulară se realizează prin înmulțirea cu inversul divizorului, dacă acel invers există.

De ce reducerea modulo nu previne automat overflow?

Înmulțirea este evaluată înainte de %. Tipul trebuie să poată reprezenta produsul intermediar sau trebuie utilizată o metodă separată de înmulțire modulară sigură.