Modulaarinen potenssi

Laske modulaarinen potenssi a^b mod n nopealla neliöi-ja-kerro-menetelmällä – toimii myös erittäin suurilla eksponenteilla.

Laske a^b mod n

Syötä kantaluku, eksponentti ja jakaja kokonaislukuina. Suuretkin eksponentit lasketaan nopeasti.

Esimerkit:

Tulokset

  • Tulosta
  • Linkitä

    • 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.

    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

    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?

    Kokeile näitä laskureita

    Matriisin potenssiPotenssin potenssiMassaprosenttilaskuriMassaprosentti molaarisuudeksiTasapainovakiolaskuriGibbsin energia -laskuriProsenttiyksikkölaskuriKaltevuusprosentti

    Linkitä tämä laskuri

    Kopioi koodi ja liitä se omalle sivustollesi.
    Kaikki Raha ja talousPalkka- ja verolaskuritSäästö- ja budjettilaskuritAsumiskustannuslaskuritLaina- ja korkolaskuritSijoitus- ja tuottolaskuritPankki- ja maksulaskuritYritystalouden laskurit
    Kaikki Aika ja päivämäärätNimipäivätPäivälaskuritKalenteri ja viikotJuhlat ja pyhätLomakalenteritAikavyöhykkeetAikajanat ja historia
    Kaikki Auto ja liikkuminenKustannukset ja polttoaineMatka ja aikaRahoitus
    Kaikki Koti ja rakentaminenRakennus ja remonttiEnergia ja sähköBudjetti ja kustannuksetKeittiö ja reseptitPiha ja puutarha
    Kaikki YksikkömuunnoksetPituus ja painoTilavuus ja keittiöLämpö ja energiaData ja teknologiaVaatteet ja kengät
    Kaikki Matematiikka ja tiedePeruslaskentaProsentit ja suhteetMurtoluvut ja desimaalitLukujonot ja peruslaskutaitoGeometria ja muodotFunktiot ja yhtälötDerivoinnit ja integraalitMatriisit ja lineaarialgebraTilastot ja todennäköisyysTrigonometria ja hyperboliset funktiotEdistyneet laskutLukujärjestelmät ja muunnoksetFysiikkaSähkö ja elektroniikkaKemiaTietotekniikka ja data
    Kaikki Arjen hyötytyökalutTeksti ja laskentaAjan ja työn laskuritSatunnaisuusHauskat ja sosiaaliset
    Kaikki Digi- ja koodityökalutKoodausmuuntimetData-formaatitHash-generaattoritLukujärjestelmätVäritKuvat ja tiedostot
    Kaikki Terveys ja kuntoiluPaino ja mittasuhteetRavinto ja energiaLiikunta ja sykeUni ja lepoRaskaus ja hedelmällisyysTestit ja hyvinvointi
    Kaikki Viihde ja vapaa-aikaPelit ja pisteetRakkaus ja horoskoopitLemmikitNimigeneraattorit ja testitAjanhallinta & tapahtumat

    Suositut laskurit

    ALV-laskuri Prosenttilaskuri Asuntolainalaskuri Yleinen lainalaskuri Nettopalkkalaskuri Painoindeksi BMI