Modulaariaritmetiikan käänteisluku

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

Kokonaisluvut ja ovat toistensa käänteislukuja modulo , missä on nollasta eroava kokonaisluku, jos

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

Kongruenssista seuraa, että . Toisin sanoen luvut ja (samoin kuin luvut ja ) 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.

Laskeminen Fermat'n pienen lauseen avulla muokkaa

Jos   on alkuluku, merk.  , niin

 

ts.

 

Luku   on siis eräs luvun   käänteisluku modulo  .

Luvun   pienin ei-negatiivinen jakojäännös modulo   voidaan laskea tehokkaasti modulaariaritmetiikan potenssiinkorotusalgoritmia käyttäen.

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

Laskeminen Eulerin lauseen avulla muokkaa

Jos  , niin Eulerin lauseen mukaan

 

ts.

 

Luku   on siis eräs luvun   käänteisluku modulo  .

Luvun   pienin ei-negatiivinen jakojäännös modulo   voidaan laskea tehokkaasti modulaariaritmetiikan potenssiinkorotusalgoritmia käyttäen.

Menetelmän rajoituksena on se, että Eulerin funktion   arvon laskemiseksi luvun   alkutekijöihin jaon pitää yleensä olla tunnettu.

Laskeminen laajennetun Eukleideen algoritmin avulla muokkaa

Olkoot   ja   kokonaislukuja,   ja  . Luvun   käänteisluku modulo  , merk.   saadaan tällöin rekursiivisesti seuraavasti:

1. Jos  , niin  

2. Muulloin

 

missä   on funktio, joka antaa luvun   pienimmän ei-negatiivisen jakojäännöksen luvulla   jaettaessa.

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

 

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