Rezolvator Ecuații de Congruență

Rezolvator de Ecuații de Congruență

Parametri de Intrare

Tip Ecuație

Coeficient a a în ax ≡ b (mod m)

Constanta b b în ax ≡ b (mod m)

Modulul m Modulul (trebuie să fie un număr întreg pozitiv)

Introduceți parametrii și faceți clic pe „Rezolvă Ecuația"

1. Ecuația de Congruență Liniară ax ≡ b (mod m):

Existența Soluțiilor:Ecuația are soluție dacă și numai dacă gcd(a, m) divide b (adică b este divizibil cu gcd(a, m))
Numărul de Soluții:Dacă există soluții, există d = gcd(a, m) soluții distincte modulo m
Metoda de Rezolvare:
1. Calculați d = gcd(a, m)
2. Verificați dacă d divide b; dacă nu, nu există soluție
3. Împărțiți ambele părți ale ecuației la d: (a/d)x ≡ (b/d) (mod m/d)
4. Utilizați Algoritmul Euclidian Extins pentru a găsi inversul lui a/d modulo m/d
5. Calculați x₀ = a' × (b/d) mod (m/d)
6. Soluția generală: x = x₀ + k(m/d), unde k = 0, 1, ..., d-1

2. Ecuația de congruență exponențială a^x ≡ b (mod m) (Problema Logaritmului Discret):

Descrierea problemei:Date fiind a, b, m, găsiți cel mai mic întreg nenegativ x astfel încât a^x ≡ b (mod m)
Existența Soluțiilor:
- Dacă gcd(a, m) = 1 și b este un element al grupului ciclic generat de a modulo m, atunci există o soluție
- Metoda de verificare: enumerați puterile lui a până când b este găsit sau un ciclu complet este finalizat
Metoda de Rezolvare:
- Căutare prin forță brută într-un interval mic:Enumerați x = 0, 1, 2, ... până când se găsește o soluție sau se atinge limita de căutare
- Algoritmul Baby-step Giant-step:Complexitate temporală O(√m), potrivit pentru probleme de dimensiune medie
- Algoritmul rho al lui Pollard:Aplicabil pentru module prime mari
Periodicitate:Dacă x₀ este o soluție, atunci x = x₀ + kφ(m) este, de asemenea, o soluție (unde φ(m) este funcția totient a lui Euler)

3. Scenarii de aplicare:

Criptografie:RSA, Schimb de chei Diffie-Hellman, Criptare ElGamal
Cercetare în teoria numerelor:Rădăcini primitive, Reziduuri pătratice, Teorema chineză a resturilor
Generare de Numere Aleatoare:Generator Congruențial Liniar (LCG)
Funcții Hash:Aplicarea aritmeticii modulare în tabelele hash
Programare Competitivă:Exponențiere rapidă, Invers modular, Probleme de teoria numerelor

Complexitate Algoritm:

Ecuații de Congruență Liniară:O(log m) (Complexitatea Algoritmului Euclidian Extins)
Ecuații de Congruență Exponențială (Forță Brută):O(n), unde n este limita de căutare
Ecuații de Congruență Exponențială (BSGS):O(√m), necesită spațiu suplimentar

Teoreme Importante:

Teorema lui Bézout:Ecuația ax + my = gcd(a, m) are întotdeauna soluții întregi
Teorema Mică a lui Fermat:Dacă p este prim și gcd(a, p) = 1, atunci a^(p-1) ≡ 1 (mod p)
Teorema lui Euler:Dacă gcd(a, m) = 1, atunci a^φ(m) ≡ 1 (mod m)
Teorema Chineză a Resturilor:Poate rezolva sisteme de congruențe