Modulo-laskin – Jäännöslaskin

Mitä modulo-operaatio on?

Modulo-operaatio (mod, tai %) palauttaa lopun, kun yksi luku jaetaan toisella. Modulo a:lle b:lle: jakaa a b:llä, ja tuloksena on lopu. Esimerkiksi 17 mod 5 = 2 (koska 17 = 3 × 5 + 2). Tulos on aina välillä [0, b-1] positiivisille arvoille.

Perusyhteys: a = q × b + r, missä q on jakojäännös (floor(a/b)) ja r on lopu (0 ≤ r < b). Modulo on yhteys jakolaskuun — jos a ÷ b = q lopun r, niin a mod b = r. Tässä laskuri käyttää oikeaa matemaattista modulo-määritelmää (aina ei-negatiivista positiiville jakajalle), eikä sitä signaattista jäännöstä, jota jotkut ohjelmointikielit käyttävät.

Modulaarinen aritmetiikka — aritmetiikka vakiollisella moduulilla, jossa luvut "kierretään" — muodostaa kellon aritmetiikan perustan. Kellon tunteja lasketaan mod 12 tai mod 24. Jos on 10 aamulla ja lisätään 5 tuntia: (10 + 5) mod 12 = 3 (PM). Tämä kierroslasku on keskeinen osa lukuteorian, kryptografia ja tietokoneiden algoritmeissa.

Modulo-esimerkit ja askeleittaiset ratkaisut

Modulo-operaation ymmärtäminen tulee intuitiiviseksi esimerkkien avulla. Jokaisen laskun muodossa on seuraava formula: jäännös = a - floor(a ÷ b) × b.

Huomaa, että 365 mod 7 = 1: tämä kertoo, että ei-vuoden on 52 täysi viikko plus 1 lisäpäivä, joten viikonpäivä siirtyy yhden vuoden aikana yhdellä. Vuodenpäivä (366 päivää) mod 7 = 2, siirtymä on kaksi.

Modulo-operaation sovellukset

Modulo-operaatio esiintyy ohjelmoinnissa ja matematiikassa. Parillisuustarkistus: jos n % 2 == 0, n on parillinen. Ympyrämäiset listat ja ring-buffers: indeksi = (nykyinen indeksi + 1) % array_size kiertää alkuun. Hash-taulukot: salkku = hash(key) % num_buckets määrittää mistä tahansa hash-arvon salkun indeksin, varmistamalla, ettei tapahdu leikkausrajapyyntö.

Ohjelmistotieteen kalenterilaskuissa käytetään mod 7 viikonpäivän aritmeettisessa laskussa. Zellerin fomula ja Doomsday-algoritmi molemmat perustuvat modulaariseen aritmeettiseen laskuun, jotta voidaan määrittää mikä päivä on viikonpäivä mistä tahansa päivästä. Tämä toimii, koska on 7 päivää viikossa — vakiollinen moduuli. Aikavyöhykkeiden offsetit käyttävät mod 24 kiertämään tunnit oikein yli keskipäivän rajapyyntöjen yli.

Ohjelmistotieteen digitaalisissa järjestelmissä modulo on käytössä kaikissa muistin osoitteiden yhteydessä. Sivutaulukoiden sisällöt, cache-setin valinta ja muistin karttavirtauskaistojen valinta kaikki perustuvat modulaariseen indeksointiin. CPU-instruktioiden joukko sisältää yleensä jäännös (modulo-tyyppinen) komennon yhdessä jakolaskun kanssa, ja SIMD-vektoreiden komennet käyttävät modulaarista indeksointia kääntämiseen.

Ohjelmistotieteen virheenetsinnässä käytetään syklisiä redundanssitarkistuksia (CRC) ja tarkistuksia (checksum) polynomiaalisen modulaarisen aritmeettisen laskun avulla GF(2). Luottokorttien numeroita tarkistetaan Luhn-algoritmin (mod 10) avulla. ISBN-10 -kirjanumerot käyttävät mod 11. Tämä tarkistus havaitsee transponointi- ja yksittäisen sarakkeen virheet numeroiden koodissa.

Modulo kryptografia

Modulaarinen aritmetiikka on nykyisen avoimen avainkryptografian matemaattinen perusta. Kolme tärkeintä kryptografista algoritmiä — RSA, Diffie-Hellman ja elliptinen käyräkryptografia — perustuvat operaatioihin, jotka suoritetaan modulaarisen suureen suureen.

RSA-salaus käyttää modulaarista potenssiin: salataan viesti M julkisen avaimen (e, n) avulla, lasketaan C = M^e mod n. Salataksesi, lasketaan M = C^d mod n, missä d on salainen avain. Turvallisuus perustuu n:n (suuriin semiprimiin) jakamisen vaikeuteen — tiedostamalla vain n, p ja q:n on laskettavaa tietokonetta, jossa avaimen koko on yli 2048 bittiä.

Diffie-Hellmanin avaimenvaihto sallii kahden osapuolen välisen salaisen avaimen luomisen epäluotettavalla kanavalla: Alice lähettää A = g^a mod p, Bob lähettää B = g^b mod p. Kumpikaan osapuoli ei voi paljastaa salaisen avaimen ilman ratkaistuaan diskreettista logaritmiikkaa.

Tämän järjestelmän turvallisuus perustuu modulaarisen potenssin yksisuuntaiseen luonteeseen: lasketaan g^a mod p on nopea (käyttäen toistuvaa neliintämistä, O(log a) kertolaskuja), mutta kääntäminen — löytää g^a mod p — on uskotaan vaativan eksponentiaalista aikaa suurille p:lle.

Modulo negatiivisten lukujen kanssa ja ääriolosuhteet

Modulo-olosuhteet negatiivisten lukujen kanssa vaihtelevat ohjelmointikielen mukaan, mikä aiheuttaa monia vaikeasti löydettäviä virheitä. Ymmärrys siitä on tärkeää ohjelmistokehittäjille.

Matematiikassa modulo aina palauttaa ei-negatiivisen tuloksen: -7 mod 3 = 2 (koska -7 = -3×3 + 2, ja 0 ≤ 2 < 3). Tämä laskuri käyttää matemaattista määritelmää.

Turvallinen tapa varmistaa ei-negatiivinen tulos mikä tahansa kielellä: ((a % b) + b) % b. Tämä käsittää negatiiviset syötteen arvot oikein ja käytetään sisäisesti laskurimme. Tämä malli on tärkeää, kun käytetään moduloa taulukon indeksointiin tai kalenterin päivien laskuun, missä negatiiviset tulokset aiheuttaisivat virheitä.

Ääriolosuhteita muistaa: (1) Minkä tahansa luvun mod 1 = 0 — jakaminen 1:llä jättää jäännäisen. (2) Minkä tahansa luvun mod itseään = 0. (3) 0 mod minkä tahansa ei-nollaisen lukun = 0. (4) Jakaminen (ja modulo) nollalla on määrittelemätön — aina validoi jakaja ennen moduolaskua. Laskurimme näyttää selkeän virheilmoituksen, jos moduolasku on nollalla.

Modulo- ja jakojakotestit

Modulon yksi käytännön sovellus on jakojakotestaus ilman täysjakoista. Lukua a on jaettava b:llä, jos ja vain jos a mod b = 0. Tämä mahdollistaa nopeat jakojakotarkistukset:

Jaettavuussäännöt ovat lyhenteitä modulaarikertalaskennan ominaisuuksista. Desimaalien summa- ja jakojakosäännöt 3:lle ja 9:lle toimivat, koska 10 ≡ 1 (mod 3) ja 10 ≡ 1 (mod 9), mikä tarkoittaa, että kunkin desimaalin sijaintiarvo on sivuva jakojakotarkistuksessa 3:lle tai 9:lle. Näitä sääntöjä opetetaan peruskoulussa ilman modulaarikertalaskennan yhteyttä, mutta taustalla on modulaarikertalaskenta.

Modulaarikertolaskenta: Nopea Potenssi Mod

Laskee suoraan a^b mod n, ensin laskee a^b, sitten ottaa mod n, on epäkäytännöllistä suurille potensseille – a^100 voi olla tuhansia desimaleja. Modulaarikertolaskenta käyttää identiteettiä (a×b) mod n = ((a mod n) × (b mod n)) mod n pitämään välivaiheet pieninä.

Nopea algoritmi käyttää toistuvaa neliöintiä (binääripotenssi):

• Kirjoita b binäärisinä: esim. b=13 = 1101₂
• Laske a, a², a⁴, a⁸ jne. kunkin mod n
• Multiploidaan potensseja vastaavat luvut: a¹³ = a⁸ × a⁴ × a¹ (mod n)

Tämä pienentää kertolaskuja b:sta O(log₂ b) asti. B = 2048-bittinen RSA-eksponentti (~10^600), tämä on ero triljoonien kertolaskujen ja vain ~2000 välillä. Ilman tämän optimoinnin RSA-salaus olisi täysin epäkäytännöllinen.