Modularna aritmetika

Iz testwiki
Pojdi na navigacijo Pojdi na iskanje
Ustaljen čas na tej se lahko izvaja z uporabo aritmetičnega modula 12.

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.

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 Predloga:Brez preloma, 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

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 Predloga:Matematična formula, sta dve števili Predloga:Matematična formula in Predloga:Matematična formula Predloga:Dfn, če je njuna razlika Predloga:Matematična formula celi večkratnik od Predloga:Matematična formula (torej če obstaja tako celo število Predloga:Matematična formula, da velja Predloga:Matematična formula). Ta kongruenčna relacija se običajno šteje, ko sta Predloga:Matematična formula in Predloga:Matematična formula celi števili, označi pa se jo z:

a≡b(modn).

Oklepaji pomenijo, da Predloga:Matematična formula velja za celo enačbo, ne samo za desno stran (v tem primeru b). Včasih se uporablja tudi Predloga:Matematična formula namesto Predloga:Matematična formula. Č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 Predloga:Matematična formula.

Število Predloga:Matematična formula se imenuje modul kongruence.

Kongruenčna relacija se lahko zapiše tudi kot

a=kn+b,

kar eksplicitno prikaže Evklidsko deljenje. Kaj pa če Predloga:Matematična formula ni ostanek števila Predloga:Matematična formula pri deljenju z Predloga:Matematična formula? Bolj natančno lahko relacijo Predloga:Matematična formula opišemo tako, da morata tako Predloga:Matematična formula, kot tudi Predloga:Matematična formula imeti enak ostanek pri deljenju z Predloga:Matematična formula. Torej

a=pn+r,
b=qn+r,

kjer je Predloga:Matematična formula skupni delitelj. Če odštejemo ta dva izraza, pridemo do prejšnje relacije:

a−b=kn,

kjer definiramo Predloga:Matematična formula

Primeri

Na primer

38≡14(mod12)

ker je Predloga:Matematična formula, 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:

−8≡7(mod5)2≡−3(mod5)−3≡−8(mod5).

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

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

Če velja Predloga:Matematična formula in Predloga:Matematična formula ali če velja Predloga:Matematična formula potem:

Če je Predloga:Matematična formula, potem v splošnem ni pravilno Predloga:Matematična formula. A to velja, če velja sledeči pogoj:

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

Modularni multiplikativni inverz je definiran s sledečimi pravili:

Multiplikativni inverz Predloga:Matematična formula se lahko učinkovito izračuna z uporabo Bézoutove identitete ax+ny=1 za x,y z uporabo razširjenega Evklidovega algoritma. V posebnem, če je Predloga:Matematična formula praštevilo, potem sta si Predloga:Matematična formula in Predloga:Matematična formula tuji za vsak Predloga:Matematična formula, da velja Predloga:Matematična formula; torej multiplikativni inverz obstaja za vse Predloga:Matematična formula, ki niso kongruentni ničelnemu modulu Predloga:Matematična formula.

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

ap−12≡1(modp).

Kongruenčni razredi

Kot katerakoli kongruenčna relacija, je kongruenčni modulo Predloga:Matematična formula ekvivalenčna relacija ter ekvivalenčni razred celega števila Predloga:Matematična formula, ki se označi z Predloga:Matematična formula, je množica Predloga:Matematična formula. Ta množica, ki jo sestavljajo cela števila, ki so kongruentna Predloga:Matematična formula po modulu Predloga:Matematična formula, se imenuje kongruenčni razred ali razred ostankov ali preprosto ostanek celega števila Predloga:Matematična formula, po modulu Predloga:Matematična formula. Če je modulo Predloga:Matematična formula razpoznaven iz besedila, se lahko ta ostanek označi z Predloga:Matematična formula.

Primeri implementacij

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

a⋅b(modm)

:

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 Predloga:Matematična formula, ki je bila implementirana zgoraj. Algoritemski način za izračunanje

ab(modm)

:

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 Predloga:Matematična formula prekoračiti 63 bitov.

Glej tudi

Predloga:Div col

Predloga:Div col end

Sklici

Predloga:Sklici

Viri

Zunanje povezave

Pridobljeno iz »https://sl.wiki.beta.math.wmflabs.org/w/index.php?title=Modularna_aritmetika&oldid=2875«