Modulaariaritmetiikan käänteisluku

Modulaariaritmetiikan käänteisluku on modulaari- eli jakojäännösaritmetiikan keskeisiä käsitteitä.

Kokonaisluvut ${\displaystyle a}$ ja ${\displaystyle b}$ ovat toistensa käänteislukuja modulo ${\displaystyle n}$, missä ${\displaystyle n}$ on nollasta eroava kokonaisluku, jos

${\displaystyle ab\equiv 1\quad ({\mbox{mod }}n)}$

Modulaariaritmetiikan käänteislukuja voidaan käyttää mm. kongruenssiyhtälöitä ratkaistaessa.

Kongruenssista ${\displaystyle ab\equiv 1\quad ({\mbox{mod }}n)}$ seuraa, että ${\displaystyle {\mbox{gcd}}(a,n)={\mbox{gcd}}(b,n)=1}$. Toisin sanoen luvut ${\displaystyle a}$ ja ${\displaystyle n}$ (samoin kuin luvut ${\displaystyle b}$ ja ${\displaystyle n}$) ovat keskenään jaottomia.

Tämä on välttämätön ja riittävä ehto käänteisluvun olemassaololle.

Modulaariaritmetiikan käänteislukuja voidaan laskea mm. käyttämällä Eulerin lausetta, Fermat'n pientä lausetta tai laajennettua Eukleideen algoritmia.

Laajennettu Eukleideen algoritmi antaa modulaariaritmetiikan käänteislukujen laskemiseen yleispätevän ja tehokkaan laskumenetelmän.

Jos ${\displaystyle n}$ on alkuluku, merk. ${\displaystyle p}$, niin

${\displaystyle a^{p-1}\equiv 1\quad ({\mbox{mod }}p)}$

ts.

${\displaystyle a^{p-2}a\equiv 1\quad ({\mbox{mod }}p)}$

Luku ${\displaystyle a^{p-2}}$ on siis eräs luvun ${\displaystyle a}$ käänteisluku modulo ${\displaystyle p}$.

Luvun ${\displaystyle a^{p-2}}$ pienin ei-negatiivinen jakojäännös modulo ${\displaystyle p}$ voidaan laskea tehokkaasti modulaariaritmetiikan potenssiinkorotusalgoritmia käyttäen.

Menetelmän rajoituksena on se, että moduulin tulee olla alkuluku.

Jos ${\displaystyle {\mbox{gcd}}(a,n)=1}$, niin Eulerin lauseen mukaan

${\displaystyle a^{\varphi (n)}\equiv 1\quad ({\mbox{mod }}n)}$

ts.

${\displaystyle a^{\varphi (n)-1}a\equiv 1\quad ({\mbox{mod }}n)}$

Luku ${\displaystyle a^{\varphi (n)-1}}$ on siis eräs luvun ${\displaystyle a}$ käänteisluku modulo ${\displaystyle n}$.

Luvun ${\displaystyle a^{\varphi (n)-1}}$ pienin ei-negatiivinen jakojäännös modulo ${\displaystyle n}$ voidaan laskea tehokkaasti modulaariaritmetiikan potenssiinkorotusalgoritmia käyttäen.

Menetelmän rajoituksena on se, että Eulerin funktion ${\displaystyle \varphi (n)}$ arvon laskemiseksi luvun ${\displaystyle n}$ alkutekijöihin jaon pitää yleensä olla tunnettu.

Olkoot ${\displaystyle m}$ ja ${\displaystyle n}$ kokonaislukuja, ${\displaystyle 0<m<n}$ ja ${\displaystyle {\mbox{gcd}}(m,n)=1}$. Luvun ${\displaystyle m}$ käänteisluku modulo ${\displaystyle n}$, merk. ${\displaystyle {\mbox{INV}}(m,n)}$ saadaan tällöin rekursiivisesti seuraavasti:

1. Jos ${\displaystyle m=1}$, niin ${\displaystyle {\mbox{INV}}(m,n)=1}$

2. Muulloin

${\displaystyle {\mbox{INV}}(m,n)={\frac {1+n(m-{\mbox{INV}}({\mbox{MOD}}(n,m),m))}{m}}}$

missä ${\displaystyle {\mbox{MOD}}(n,m)}$ on funktio, joka antaa luvun ${\displaystyle n}$ pienimmän ei-negatiivisen jakojäännöksen luvulla ${\displaystyle m}$ jaettaessa.

Esimerkiksi Mathematica-ohjelmistossa modulaariaritmetiikan käänteisluvun laskeva funktio voitaisiin tätä rekursiota käyttäen määrittää yhdellä rivillä:

${\displaystyle {\mbox{Inv}}[m\_,n\_]:={\mbox{If}}[m==1,1,(1+n*(m-{\mbox{Inv}}[{\mbox{Mod}}[n,m],m]))/m]}$

Mathematica-ohjelmistosta löytyy tähän tarkoitukseen kuitenkin myös valmiiksi ohjelmoitu funktio.