Matematici aplicative in informatica (aritmetica modulara, combinari)

Pe scurt

Aritmetica modulară și combinările sunt două concepte matematice fundamentale în informatică, utilizate în criptografie, algoritmi de hashing și analiza algoritmilor. Aritmetica modulară studiază operațiile în inelul claselor de resturi modulo n, iar combinările reprezintă numărul de moduri de a alege k elemente dintr-o mulțime de n elemente, fără a ține cont de ordine. Relația dintre cele două apare frecvent în probleme care necesită calculul combinărilor modulo un număr prim.

Definiții și principii de bază

Aritmetica modulară

• Congruența modulo n: două numere întregi a și b sunt congruente modulo n (scriem a ≡ b (mod n)) dacă diferența lor se divide exact la n, adică n | (a−b)
• Operații modulo n: adunarea, scăderea și înmulțirea se efectuează astfel: (a + b) mod n = (a mod n + b mod n) mod n
• Inversul modular: a^(-1) mod n există doar dacă c.m.m.d.c.(a, n) = 1, iar calculul se face cu algoritmul lui Euclid extins

Combinări

• Definiție: C(n,k) sau (n k) (citit „combinări de n luate câte k”) reprezintă numărul de moduri de a alege k elemente dintr-o mulțime de n elemente, fără a ține cont de ordine
• Formula uzuală: **C(n,k) = n! / (k! * (n−k)!)
• Identitatea lui Pascal: C(n,k) = C(n−1,k−1) + C(n−1,k)
• Triunghiul lui Pascal: instrument eficient pentru calculul iterativ al combinărilor

• Criptografie (de exemplu, RSA)
• Generarea de numere pseudo-aleatoare
• Verificarea corectitudinii datelor (checksum, coduri de bare)
• Algoritmi de hashing

• Analiza algoritmilor (numărul de submulțimi, problema rucsacului, Backtracking)
• Probabilități
• Generarea de submulțimi

Pentru valori mari ale lui n și k, se calculează C(n,k) modulo un număr prim (de obicei 1e9+7) folosind:

• Factoriali precalculați
• Inversi modulari
• Teorema lui Fermat: a^(p−2) mod p pentru invers

• Lema lui Lucas: pentru calcul C(n,k) mod p când p este prim și n, k sunt scrise în baza p
• Teorema chineză a resturilor

• Precalcularea factorialelor și a inverselor într-un vector
• Răspunsul la interogări în O(1)
• Gestionarea memoriei și a overflow-ului prin utilizarea modulului

• Exemplul 1 (Aritmetică modulară - criptare simplă): Să se calculeze (23 * 17 + 45) mod 11**. Rezolvare: 23 mod 11 = 1, 17 mod 11 = 6, 45 mod 11 = 1. Expresia devine (1 * 6 + 1) mod 11 = 7 mod 11 = 7. Răspuns: 7.
• Exemplul 2 (Combinări - număr de submulțimi): Câte submulțimi de câte 3 elemente se pot forma dintr-o mulțime cu 7 elemente? Rezolvare: C(7,3) = 7! / (3! * 4!) = (7*6*5)/(3*2*1) = 35. Răspuns: 35.
• Exemplul 3 (Combinări modulo prim): Calculați C(10,4) mod 7. Rezolvare: C(10,4)=210. 210 mod 7 = 0 (deoarece 210=30*7). Alternativ, se poate calcula cu factoriali modulari: factorialii precalculați: 10! mod 7 se reduce la 0 deoarece 7|10! → rezultat 0. Răspuns: 0.

Verifică-te!

1. Care este condiția necesară pentru ca inversul modular a^(-1) mod n să existe?
2. Folosind identitatea lui Pascal, cum poți exprima C(8,3) în funcție de combinări cu n=7?
3. Ce se întâmplă cu C(n,k) mod p atunci când p este un număr prim mai mic sau egal cu n?