Aritmetică modulară

În numeroase probleme de informatică se cere determinarea restului împărțirii unui anumit număr (de regulă rezultat ale unui calcul) la o valoare dată, N. De cele mai multe ori numărul nu poate fi determinat direct, valoarea sa fiind prea mare. În aceste situații intervine aritmetica modulară, în care restul cerut se determină facând operații cu resturi la împărțirea cu N a unor rezultate parțiale.

Fie $N>1$ un număr natural și două numere întregi $a$ și $b$. Spunem că $a$ și $b$ sunt congruente modulo $N$ , $a\equiv b\mathrm{mod}N$ dacă $N|(a-b)$. Echivalent, dacă $a$ și $b$ dau același rest la împărțirea cu $N$.

Adunarea și înmulțirea

Avem următoarele reguli – spunem că congruența modulo N este compatibilă cu adunarea și înmulțirea numerelor întregi :

• Dacă $a\equiv x\mathrm{mod}N$ și $b\equiv y\mathrm{mod}N$, atunci $a+b\equiv x+y\mathrm{mod}N$.
• Dacă $a\equiv x\mathrm{mod}N$ și $b\equiv y\mathrm{mod}N$, atunci $a\cdot b\equiv x\cdot y\mathrm{mod}N$.

Consecințe (C/C++):

• având două numere naturale a, b, iar N > 1 unu număr natural:
  • restul împărțirii sumei la N este (a + b) % N = (a % N + b % N) % N
  • restul împărțirii produsului la N este (a * b) % N = ((a % N) * (b % N)) % N
• având n numere naturale A[1], A[2], …, A[n], restul împărțirii la N a produsului lor se determină astfel:

int P = 1;
for(int i =1 ; i <= n ; i ++)
    P = (P * A[i]) % N;

• pentru a calcula restul împărțirii la N a lui N! – N factorial:

int P = 1;
for(int i =1 ; i <= N ; i ++)
    P = (P * i) % N;

Scăderea

Fie numerele naturale a ≥ b și N>1. Deși congruența modulo N este compatibilă cu operația de scădere, expresia (a-b)%N = (a%N-b%N)%N nu este întotdeauna corectă.

Mai precis, chiar dacă a > b, deci (a-b)%N≥0, expresia (a%N-b%N) și deci (a%N-b%N)%N poate fi negativă. Situatia poate fi rezolvată ușor, adunând la X=(a%N-b%N)%N valoarea N, astfel X nemaifiind negativ.

Exemplu: Fie n m, două numere naturale, 1 ≤ n ≤ m ≤ 1000. Determinați restul împărțirii lui m!-n! la 1009.

Rezolvare: Fie N = 1009. Deoarece numere sunt mari, nu putem calcula factorialele. Vom calcula A = m! % N, B= n! % N, apoi X = (A-B)%N. Dacă X este negativ, vom aduna la X valoarea N, acesta fiind și rezultatul.

Următoarea secvență C++ implementează ideea de mai sus:

int n , m;
const int N = 1009;
cin >> n >> m; // n <= m
int  A = 1, B = 1;
for(int i = 1 ; i <= m ; i ++)
    A = (A * i) % N;
for(int i = 1 ; i <= n ; i ++)
    B = (B * i) % N;
int X = A - B;
if(X < 0)
    X += N;
cout << X;

Împărțirea. Inversul modular

Congruența modulo N nu este compatibilă cu împărțirea. Consecința este că (B/A) % N != ((B % N)/(A % N)) % N. Pentru a determina rezultatul modulo N al unor expresii în care intervin împărțiri vom folosi inversul modular.

Acesta permite transformarea expresiei B/A % N într-o înmulțire și poate fi determinat numai dacă numerele A și N sunt prime între ele.

Mai precis, dacă 1 ≤ A < N, inversul lui A modulo N este un număr natural 1 ≤ A-1 < N cu proprietatea că $A\cdot A^{-1}\equiv 1\mathrm{mod}N$. Atunci (B/A) % N = (B * A-1) % N = ((B%N)*(A-1%N))%N.

Există mai multe modalități de a determina inversul modular. În cele ce urmează vom nota inversul modular al lui A cu I.

O primă variantă este să analizăm fiecare număr k cuprins între 1 și N-1. Dacă A * k % N este 1, atunci I=k. Complexitatea este $O(n)$.

Aplicând teorema lui Euler, $A^{\phi (N)}\equiv 1(\mathrm{mod}N)$, unde $\phi (N)$ este indicatorul lui Euler. Atunci $A\cdot A^{\phi (N)-1}\equiv 1(\mathrm{mod}N)$, deci $I=A^{\phi (N)-1}\mathrm{mod}N$. Acest rezultat poate fi determinat folosind exponențierea rapidă cu complexitatea $O({\log }_{2}N)$. Putem calcula indicatorul lui Euler cu complexitatea $O(\sqrt{N})$, deci complexitatea determinării inversului modular devine $O({\log }_{2}N\cdot \sqrt{N})$.

Dacă N este prim, atunci $\phi (N)=N–1$, deci $I=A^{N-2}\mathrm{mod}N$. Pentru determinare folosim exponențierea rapidă.

Cea mai eficientă metodă de a determina inversul modular folosește algoritmul lui Euclid extins, pentru A și N. Conform acestuia, există X și Y astfel încât A*X + N*Y = 1, deoarece 1=cmmdc(A,N), A și N fiind prime între ele. Trecând la operațiile modulo N, obținem $A\cdot X\equiv 1\mathrm{mod}N$, deoarece $N\cdot Y\equiv 1\mathrm{mod}N$. De aici rezultă că inversul modular al lui A modulo N este chiar X. Dacă X determinat astfel este negativ, îl vom mări cu N până când devine pozitiv.

Următoarea secvență C++ determină inversul modular al lui A, modulo N:

void euclid(int a , int b ,int & x ,int & y)
{
    if(b == 0)
    {
        x = 1, y = 1;
    }
    else
    {
        int x1 , y1;
        euclid(b , a % b , x1 , y1);
        x = y1;
        y = x1 - a / b * y1;
    }
}

int main()
{
    int A = 9, N = 11; // prime intre ele, 1 <= A < N
    int X , Y;
    euclid(A, N , X ,Y);
    while(X < 0)
        X += N;
    cout << X; // 5
    return 0;
}

Inversul modular poate fi folosit, de exemplu pentru a calcula $C_n^k$ modulo P, unde P este un număr prim.