Fotools
EN

Lösare av kongruensekvationer

Indataparametrar

Snabbt exempel:

Beräkningsresultat

Ange parametrar och klicka på "Lös ekvation"

Algoritmförklaring:

1. Linjär kongruensekvation ax ≡ b (mod m):
  • Existens av lösningar:Ekvationen har en lösning om och endast om gcd(a, m) delar b (dvs. b är delbart med gcd(a, m))
  • Antal lösningar:Om lösningar finns, finns det d = gcd(a, m) distinkta lösningar modulo m
  • Lösningsmetod:
    1. Beräkna d = gcd(a, m)
    2. Kontrollera om d delar b; om inte, finns det ingen lösning
    3. Dividera båda sidor av ekvationen med d: (a/d)x ≡ (b/d) (mod m/d)
    4. Använd den utökade euklidiska algoritmen för att hitta inversen av a/d modulo m/d
    5. Beräkna x₀ = a' × (b/d) mod (m/d)
    6. Allmän lösning: x = x₀ + k(m/d), där k = 0, 1, ..., d-1
2. Exponentiell kongruensekvation a^x ≡ b (mod m) (diskret logaritmproblem):
  • Problembeskrivning:Givet a, b, m, hitta det minsta icke-negativa heltal x så att a^x ≡ b (mod m)
  • Existens av lösningar:
    • Om gcd(a, m) = 1 och b är ett element i den cykliska gruppen som genereras av a modulo m, finns en lösning
    • Verifieringsmetod: räkna upp potenser av a tills b hittas eller en full cykel är klar
  • Lösningsmetod:
    • Brute force-sökning i ett litet område:Räkna upp x = 0, 1, 2, ... tills en lösning hittas eller sökgränsen nås
    • Baby-step Giant-step-algoritm:Tidskomplexitet O(√m), lämplig för medelstora problem
    • Pollards rho-algoritm:Tillämpbar för stora primtalsmoduler
  • Periodicitet:Om x₀ är en lösning, är x = x₀ + kφ(m) också en lösning (där φ(m) är Eulers fi-funktion)
3. Tillämpningsområden:
  • Kryptografi:RSA, Diffie-Hellman-nyckelutbyte, ElGamal-kryptering
  • Talteoretisk forskning:Primitiva rötter, kvadratiska rester, kinesiska restsatsen
  • Slumptalsgenerering:Linjär kongruensgenerator (LCG)
  • Hashfunktioner:Tillämpning av modulär aritmetik i hashtabeller
  • Tävlingsprogrammering:Snabb exponentiering, modulär invers, talteoretiska problem

Algoritmkomplexitet:

  • Linjära kongruensekvationer:O(log m) (komplexitet för utökad euklidisk algoritm)
  • Exponentiella kongruensekvationer (brute force):O(n), där n är sökgränsen
  • Exponentiella kongruensekvationer (BSGS):O(√m), kräver extra utrymme

Viktiga satser:

  • Bezouts sats:Ekvationen ax + my = gcd(a, m) har alltid heltalslösningar
  • Fermats lilla sats:Om p är ett primtal och gcd(a, p) = 1, då a^(p-1) ≡ 1 (mod p)
  • Eulers sats:Om gcd(a, m) = 1, då a^φ(m) ≡ 1 (mod m)
  • Kinesiska restsatsen:Kan lösa system av kongruenser