Laske modulaarinen potenssi xy mod n nopeasti. Syötä kantaluku, eksponentti ja moduli, niin saat jakojäännöksen tehokkaasti binäärisen potenssiinkorotuksen avulla.
Modulaarisen potenssiinkorotuksen laskuri
Näin käytät laskuria
- Syötä x (kantaluku) -kenttään kantaluku (kokonaisluku).
- Syötä y (eksponentti) -kenttään eksponentti (epänegatiivinen kokonaisluku).
- Syötä n (moduli) -kenttään moduli (positiivinen kokonaisluku, n ≥ 1).
- Valitse Laske. Arvo xy mod n näkyy Tulos-kentässä.
- Aloita uusi lasku valitsemalla Tyhjennä.
Mitä modulaarinen potenssiinkorotus tarkoittaa?
Modulaarisessa potenssiinkorotuksessa lasketaan jakojäännös, joka saadaan jakamalla xy luvulla n:
xy mod n = r
missä r on jakojäännös, kun xy jaetaan luvulla n, ja 0 ≤ r < n.
Tämä laskutoimitus on keskeinen lukuteoriassa ja julkisen avaimen salauksessa (muun muassa RSA:ssa), joissa hyvin suuria potensseja on laskettava tehokkaasti.
Nopea modulaarinen potenssiinkorotus
Arvon xy laskeminen suoraan muuttuu epäkäytännölliseksi eksponentin kasvaessa. Binäärinen potenssiinkorotus ratkaisee ongelman O(log y) -operaatiolla neliöimällä kantalukua toistuvasti:
- Jos y on parillinen: xy = (xy/2)2
- Jos y on pariton: xy = x × xy−1
Moduli otetaan jokaisessa vaiheessa, joten välitulokset pysyvät pieninä.
Esimerkkejä modulaarisesta potenssiinkorotuksesta
| x (kantaluku) | y (eksponentti) | n (moduli) | xy mod n |
|---|---|---|---|
| 2 | 10 | 7 | 2 |
| 3 | 4 | 5 | 1 |
| 5 | 3 | 13 | 8 |
| 7 | 0 | 10 | 1 |
| 2 | 100 | 1000000007 | 976371285 |
Usein kysytyt kysymykset
Mitä modulaarinen potenssiinkorotus tarkoittaa?
Modulaarisessa potenssiinkorotuksessa lasketaan xy mod n eli jakojäännös, joka saadaan jakamalla xy luvulla n. Menetelmä on tärkeä kryptografiassa ja lukuteoriassa.
Miten lasken xy mod n?
Syötä kantaluku x, eksponentti y ja moduli n ja valitse Laske. Tuloksena saat jakojäännöksen, kun xy jaetaan luvulla n; laskenta tehdään nopealla modulaarisella potenssiinkorotuksella.
Miksi modulaarista potenssiinkorotusta käytetään kryptografiassa?
Modulaarinen potenssiinkorotus on RSA:n ja Diffie–Hellman-avaimenvaihdon perusta. Laskenta yhteen suuntaan on tehokasta, mutta sen kääntäminen diskreetin logaritmin ongelman avulla on erittäin vaikeaa. Tämä epäsymmetria on hyödyllinen tietoturvassa.
Paljonko on 2¹⁰ mod 7?
2¹⁰ = 1024 ja 1024 = 146 × 7 + 2. Siis 2¹⁰ mod 7 = 2.
Mikä on binäärisen potenssiinkorotuksen algoritmi?
Se on tehokas tapa laskea xy mod n puolittamalla eksponentti toistuvasti. Operaatioiden määrä vähenee O(y):stä O(log y):hyn, joten valtavatkin potenssit voidaan käsitellä sekunnin murto-osassa.
Aiheeseen liittyvät laskurit ja oppaat
