Moduloiminen

Moduloiminen on modulo-operaatio, jossa kokonaisluku a määritellään suhteessa positiiviseen lukuun n. Se tuottaa jäännöksen r, kun a jaetaan n:llä, niin että a = qn + r ja 0 ≤ r < n. Tällöin r = a mod n ja a ≡ r (mod n). Matematiikassa moduloa käytetään kuvaamaan näiden jäännösten luokkaa.

Notaatio ja peruskäsite ovat yleisesti seuraavat: a mod n tarkoittaa jäännöstä, jonka saadaan jakamalla a luvulla n. Suureilla a ja n voidaan kirjoittaa a ≡ r (mod n), missä r on a mod n. Moduloiminen antaa siten kiertoa- tai sykliarvon, jonka avulla voidaan käsitellä lukuja tasaisemmin tietyissä koodauksissa ja laskutoimituksissa.

Ominaisuudet ja laskentamallit: moduloiminen on suljettu, eli a mod n on aina kokonaisluku joukossa {0, 1, ..., n−1}. Yhteen- ja kertolaskussa pätee (a + b) mod n = (a mod n + b mod n) mod n sekä (a · b) mod n = (a mod n · b mod n) mod n. Eksaktit käänteislukujen olemassaolo modulo n määräytyy kirjaimellisesti, sillä a a^{-1} ≡ 1 (mod n) jos ja vain if gcd(a, n) = 1. Moduloiminen on keskeinen osa modularisaatiota, kuten modular exponentiation ja lukuteorian teoreemat.

Sovellukset: moduloimista käytetään kellomaisessa aika- ja tilasäätöissä, kryptografiassa (esim. RSA, Diffie–Hellman), kryptografisissa alkukoodauksissa, sekä eräissä hajautus- ja satunnaislukugeneraattoreissa. Se auttaa ratkaisemaan kongruensseja ja hallitsemaan syklisiä rakenteita.

Esimerkkejä: 29 mod 7 = 1; -3 mod 7 = 4 (ekviduottamus riippuen määritelmästä negatiivisista luvuista). Monissa ohjelmointikielissä modulo-operaatio ja jakojäännös eroavat negatiivisten lukujen tapauksessa, mikä on syytä huomioida.