Laske a^b mod n
Syötä kantaluku, eksponentti ja jakaja kokonaislukuina. Suuretkin eksponentit lasketaan nopeasti.
Esimerkit:
Modulaarinen potenssi
Laske modulaarinen potenssi a^b mod n nopealla neliöi-ja-kerro-menetelmällä – toimii myös erittäin suurilla eksponenteilla.
Modulaarinen potenssi – a^b mod n tehokkaasti
Modulaarisen potenssin laskuri laskee lausekkeen a^b mod n eli potenssin a^b jakojäännöksen luvulla n. Laskuri käyttää neliöi-ja-kerro-menetelmää, joka toimii nopeasti myös erittäin suurilla eksponenteilla – juuri tätä operaatiota tarvitaan esimerkiksi RSA-salauksessa. Tulos lasketaan tarkasti suurillakin luvuilla.
Mitä modulaarinen potenssi on?
Modulaarinen potenssi yhdistää tavallisen potenssiin korottamisen ja jäännöslaskennan. Lauseke kirjoitetaan muodossa:
tulos = a^b mod n
Se kertoo, mikä on a^b:n jakojäännös jaettaessa n:llä. Tulos on aina väliltä 0 … n−1. Esimerkiksi 3⁴ mod 5 = 81 mod 5 = 1.
Miksi suora laskutapa ei riitä
Jos potenssi a^b laskettaisiin ensin kokonaan ja vasta sitten otettaisiin jakojäännös, luku kasvaisi valtavan suureksi. Esimerkiksi salauksessa eksponentti voi olla satoja numeroita pitkä, jolloin a^b ei mahtuisi mihinkään muistiin. Ratkaisu on ottaa jakojäännös jokaisen välivaiheen jälkeen, jolloin luvut pysyvät pieninä.
Neliöi-ja-kerro-menetelmä
Tehokkain tapa perustuu eksponentin binääriesitykseen. Tulosta neliöidään joka askeleella, ja kun binääriluvussa on ykkönen, tulokseen kerrotaan kantaluku – aina modulo n:
x² mod n ja (x · a) mod n
Menetelmä tarvitsee vain noin log₂(b) vaihetta, joten sen nopeus on aivan eri luokkaa kuin b:n yksittäisen kertolaskun ketju.
Vaiheittainen esimerkki
Lasketaan 4¹³ mod 497. Eksponentti 13 on binäärinä 1101.
- Aloitetaan tuloksesta 1 ja kantaluvusta 4.
- Käydään binääriluvun bitit läpi neliöiden ja tarvittaessa kertoen, ja otetaan joka vaiheessa jakojäännös 497:llä.
- Lopputulos on 445.
Tarkistus: 4¹³ = 67 108 864, ja 67 108 864 mod 497 = 445. Sama tulos saadaan siis murto-osassa askeleita ilman, että käsitellään kahdeksannumeroista lukua.
Modulaarinen potenssi ja kryptografia
Modulaarinen potenssi on monien julkisen avaimen salausmenetelmien perusta. RSA-salauksessa viesti salataan ja puretaan nostamalla se potenssiin modulo suuri luku n. Diffie–Hellman-avaintenvaihdossa osapuolet laskevat saman jaetun salaisuuden modulaaristen potenssien avulla. Menetelmän turvallisuus perustuu siihen, että vaikka potenssi on helppo laskea, käänteinen operaatio (diskreetti logaritmi) on käytännössä mahdoton suurilla luvuilla.
Modulaariaritmetiikan ominaisuuksia
- Tulon jäännös: (a · b) mod n = ((a mod n) · (b mod n)) mod n.
- Potenssin jäännös: a^b mod n = (a mod n)^b mod n, joten kantaluku voidaan pienentää heti.
- Fermat'n pieni lause: jos n on alkuluku eikä a ole jaollinen n:llä, niin a^(n−1) mod n = 1.
Kokeile myös näitä palveluita
Mainos
Usein kysytyt kysymykset
Mitä modulaarinen potenssi tarkoittaa?
Modulaarinen potenssi tarkoittaa potenssin a^b jakojäännöstä luvulla n eli lauseketta a^b mod n. Se vastaa kysymykseen, mikä on a^b:n jakojäännös, kun se jaetaan n:llä. Esimerkiksi 3^4 mod 5 = 81 mod 5 = 1.
Miksi käytetään neliöi-ja-kerro-menetelmää?
Suoraan laskettuna a^b kasvaa valtavan suureksi jo pienillä eksponenteilla. Neliöi-ja-kerro-menetelmä pitää jokaisen välituloksen pienempänä kuin n ottamalla jakojäännöksen jokaisen vaiheen jälkeen. Näin lasketaan vain noin log₂(b) kerto- ja neliöintioperaatiota, mikä tekee laskennasta erittäin nopeaa.
Miten neliöi-ja-kerro toimii?
Eksponentti b kirjoitetaan binäärilukuna. Tulosta neliöidään jokaisella askeleella, ja aina kun binääriluvun kohdalla on ykkönen, tulokseen kerrotaan kantaluku. Jokaisen kerto- ja neliöintivaiheen jälkeen otetaan jakojäännös modulo n, jolloin luvut pysyvät pieninä.
Mihin modulaarista potenssia käytetään?
Modulaarinen potenssi on monien salausmenetelmien ydintoiminto. Esimerkiksi RSA-salauksessa sekä salaus että purku perustuvat lausekkeeseen viesti^avain mod n. Sitä käytetään myös Diffie–Hellman-avaintenvaihdossa ja monissa lukuteoreettisissa algoritmeissa.
Mitä jos kantaluku on suurempi kuin modulus?
Sillä ei ole väliä: laskenta toimii silti, koska ensimmäinen vaihe ottaa kantaluvusta jakojäännöksen modulo n. Esimerkiksi 12^2 mod 5 = 144 mod 5 = 4, mikä on sama kuin (12 mod 5)^2 mod 5 = 2^2 mod 5 = 4.
Oliko tästä laskurista apua?
