Modularna aritmetika

V matematiki je modularna aritmetika sistem aritmetike za cela števila, kjer se števila "ponovno vrtijo okoli", ko dosežejo določeno vrednost, ki se imenuje modulo (ali modul). Moderni približek modularni aritmetiki je uveljavil Carl Friedrich Gauss v svoji knjigi Disquisitiones Arithmeticae, ki jo je izdal leta 1801.

Ustaljen čas na tej se lahko izvaja z uporabo aritmetičnega modula 12.

Vsem poznana uporaba modularne aritmetike je 12-urna ura, kjer je dan razdeljen na dve 12-urni periodi. Če je sedaj ura 7:00, bo čez 8 ur enaka 3:00. Navadno seštevanje bi nam dalo rezultat 7 + 8 = 15, a to ne bo odgovor, ker se čas po uri "obrne naokoli" na vsakih 12 ur. Ker se številke na uri ponastavijo, ko pridejo do 12, ima ura aritmetični modul enak 12. Če to izrazimo s spodnjo definicijo, je 15 kongruentno 3 v modulu 12, torej je (24-urni) čas "15:00" enak času "3:00" na uri.

Definicije relacij v konguencah

uredi

Modularna aritmetika se lahko obravnava matematično z vpeljavo kongruenčne relacije na celih številih, ki se da združiti z operacijami na celih številih: seštevanje, odštevanje in množenje. Za naravno število n, sta dve števili a in b kongruentni v modulu n, če je njuna razlika ab celi večkratnik od n (torej če obstaja tako celo število k, da velja ab = kn). Ta kongruenčna relacija se običajno šteje, ko sta a in b celi števili, označi pa se jo z:

 

Oklepaji pomenijo, da (mod n) velja za celo enačbo, ne samo za desno stran (v tem primeru b). Včasih se uporablja tudi = namesto . Če se oklepaje izpusti, pomeni to v splošnem, da označuje "mod" operacijo modulo, ki se nanaša samo na desno stran, spremeni pa se tudi v enakost, da velja 0 ≤ a < n.

Število n se imenuje modul kongruence.

Kongruenčna relacija se lahko zapiše tudi kot

 

kar eksplicitno prikaže Evklidsko deljenje. Kaj pa če b ni ostanek števila a pri deljenju z n? Bolj natančno lahko relacijo ab mod n opišemo tako, da morata tako a, kot tudi b imeti enak ostanek pri deljenju z n. Torej

 
 

kjer je 0 ≤ r < n skupni delitelj. Če odštejemo ta dva izraza, pridemo do prejšnje relacije:

 

kjer definiramo k = pq.

Primeri

uredi

Na primer

 

ker je 38 − 14 = 24, kar je večkratnik od 12, ali, ekvivalentno, ker imata tako 38, kot tudi 14 enak ostanek 2 pri deljenju z 12.

Enako pravilo velja tudi za negativne vrednosti:

 

Ker se lahko pogosto pojavi več relacij, kjer so različni moduli naenkrat, smo v zgornji sistem vedno zapisali modulo. Kongruenčna relacija za dani modul velja za binarno relacijo.

Lastnosti

uredi

Kongruenčna relacija zadovolji vsem pogojem za ekvivalenčno relacijo:

  • Refleksivnost: aa (mod n)
  • Simetrija: ab (mod n) če ba (mod n) za vse a, b in n.
  • Tranzitivnost: Če ab (mod n) in bc (mod n), potem ac (mod n)

Če velja a1b1 (mod n) in a2b2 (mod n), ali če velja ab (mod n), potem:

  • a + kb + k (mod n) za katerokoli celo število k (kar se sklada s premikom)
  • k ak b (mod n) za katerokoli celo število k (kar je skladno s povečanjem)
  • a1 + a2b1 + b2 (mod n) (skladno s seštevanjem)
  • a1a2b1b2 (mod n) (skladno z odštevanjem)
  • a1 a2b1 b2 (mod n) (skladno z množenjem)
  • akbk (mod n) za katerokoli nenegativno celo število k (skladno s potenciranjem)
  • p(a) ≡ p(b) (mod n), za katerikoli polinom p(x) s celimi koeficienti (kar je skladno s polinomsko evaluacijo)

Če je ab (mod n), potem v splošnem ni pravilno kakb (mod n). A to velja, če velja sledeči pogoj:

Za pokrajšanje skupnih členov, poznamo sledeča pravila:

  • Če je a + kb + k (mod n) za katerokoli celo število k, potem je ab (mod n)
  • Če je k ak b (mod n) in sta si k in n tuji si števili, potem je ab (mod n)

Modularni multiplikativni inverz je definiran s sledečimi pravili:

  • Obstoj: obstaja celo število, ki je označeno z a–1, da velja aa–1 ≡ 1 (mod n) če in samo če je a tuje z n. To število a–1 se imenuje modularni multiplikativni inverz modula n.
  • Če je ab (mod n) in obstaja a–1, potem je a–1b–1 (mod n) (skladno z multiplikativnim inverzom in če ima a = b edinstven modul n)
  • Če je a xb (mod n) in a je tuje n, potem je rešitev te linearne kongruence podana z xa–1b (mod n)

Multiplikativni inverz xa–1 (mod n) se lahko učinkovito izračuna z uporabo Bézoutove identitete   za   z uporabo razširjenega Evklidovega algoritma. V posebnem, če je p praštevilo, potem sta si a in p tuji za vsak a, da velja 0 < a < p; torej multiplikativni inverz obstaja za vse a, ki niso kongruentni ničelnemu modulu p.

Nekaj nekaterih bolj naprednih lastnosti kongruenčnih relacij je zbranih tukaj:

  • Fermatov mali izrek: Če je p praštevilo in ne deli a, potem a p – 1 ≡ 1 (mod p).
  • Eulerjev izrek: Če sta si a in n tuji si števili, potem velja a φ(n) ≡ 1 (mod n), kjer je φ Eulerjeva funkcija fi
  • Preprosta posledica Fermatovega malega izreka je: če je p praštevilo, potem je a−1a p − 2 (mod p) multiplikativni inverz od 0 < a < p. Še bolj splošno iz Eulerjevega izreka: če sta si a in n tuji, potem je a−1a φ(n) − 1 (mod n).
  • Druga preprosta posledica je, da če velja ab (mod φ(n)), kjer je φ Eulerjeva fi funkcija, potem velja kakb (mod n), kjer je k tuje z n.
  • Wilsonov izrek: p je praštevilo, če in samo če velja (p − 1)! ≡ −1 (mod p).
  • Kitajski izrek o ostankih: Za katerakoli a in b ter tuji števili m in n, obstaja unikatno celo število x (mod mn), da velja xa (mod m) in xb (mod n). Velja tudi xb mn–1 m + a nm–1 n (mod mn), kjer je mn−1 inverz od m modulo n in nm−1 je inverz od n modulo m.
  • Lagrangeov izrek: Kongruenca f (x) ≡ 0 (mod p), kjer je p praštevilo in f (x) = a0 xn + ... + an je polinom s celimi koeficienti, da ima a0 ≠ 0 (mod p) največ n korenov.
  • Primitivni koren modula n: Število g je primitivni koren modula n, če obstaja za vsako celo število a, ki je tuje n, neko celo število k, da velja gka (mod n). Primitivni koren modula n obstaja če in samo če je n enak 2, 4, pk ali 2pk, kjer je p liho praštevilo in je k naravno število. Če obstaja primitivni koren modula n, potem obstaja natanko φ(φ(n)) takšnih primitivnih korenov, kjer je φ Eulerjeva fi funkcija.
  • Kvadratični ostanek: Celo število a je kvadratični ostanek modula n, če obstaja tako celo število x, da velja x2a (mod n). Eulerjev kriterij nam pravi, da če je p liho praštevilo in a ni večkratnik od p, potem je a kvadratični ostanek modula p če in samo če
 

Kongruenčni razredi

uredi

Kot katerakoli kongruenčna relacija, je kongruenčni modulo n ekvivalenčna relacija ter ekvivalenčni razred celega števila a, ki se označi z an, je množica {… , a − 2n, an, a, a + n, a + 2n, …}. Ta množica, ki jo sestavljajo cela števila, ki so kongruentna a po modulu n, se imenuje kongruenčni razred ali razred ostankov ali preprosto ostanek celega števila a, po modulu n. Če je modulo n razpoznaven iz besedila, se lahko ta ostanek označi z [a].

Primeri implementacij

uredi

Spodaj so tri dokaj hitre funkcije v jeziku C, dve za izvajanje modularnih množenj in ena za izvajanje modularnega potenciranja na neoznačenih celih (naravnih) številih, ki niso večja od 63 bitov.

Algoritemski način za izračunanje  :

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   uint64_t d = 0, mp2 = m >> 1;
   int i;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   for (i = 0; i < 64; ++i)
   {
       d = (d > mp2) ? (d << 1) - m : d << 1;
       if (a & 0x8000000000000000ULL)
           d += b;
       if (d >= m) d -= m;
       a <<= 1;
   }
   return d;
}

Na računalnikih, kjer je mogoča tudi razširjena natančnost z najmanj 64 biti mantise (kot recimo tip long double na večini x86 C prevajalnikih), se lahko uporabi sledeča implementacija, saj po trdih komponentah množenje plavajoče vejice vodi v obdržane najbolj zanesljive bite, medtem ko množenje celih števil vodi v obdržane najmanj zanesljive bite:

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   long double x;
   uint64_t c;
   int64_t r;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   x = a;
   c = x * b / m;
   r = (int64_t)(a * b - c * m) % (int64_t)m;
   return r < 0 ? r + m : r;
}

Spodnja je C funkcija za izvajanje modularnega potenciranja, ki uporablja funkcijo mul_mod, ki je bila implementirana zgoraj. Algoritemski način za izračunanje  :

uint64_t pow_mod(uint64_t a, uint64_t b, uint64_t m)
{
    uint64_t r = m==1?0:1;
    while (b > 0) {
        if (b & 1)
            r = mul_mod(r, a, m);
        b = b >> 1;
        a = mul_mod(a, a, m);
    }
    return r;
}

A da bi vse zgornje poti delovale, ne sme m prekoračiti 63 bitov.

Glej tudi

uredi

Sklici

uredi
  • John L. Berggren. "modular arithmetic". Encyclopædia Britannica.
  • Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001. See in particular chapters 5 and 6 for a review of basic modular arithmetic.
  • Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany"
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7ISBN 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868.
  • Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. ISBN 0-486-41449-3ISBN 0-486-41449-3.
  • Long, Calvin T. (1972). Elementary Introduction to Number Theory (2. izd.). Lexington: D. C. Heath and Company. LCCN 77171950.
  • Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. LCCN 71081766.
  • Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123.

Zunanje povezave

uredi