Beräkna modulär exponentiering, xy mod n, direkt. Ange basen, exponenten och modulen för att effektivt få resten med binär exponentiering.
Kalkylator för modulär exponentiering
Så använder du kalkylatorn
- I fältet x (bas) anger du basen (ett heltal).
- I fältet y (exponent) anger du exponenten (ett icke-negativt heltal).
- I fältet n (modul) anger du modulen (ett positivt heltal, n ≥ 1).
- Välj Beräkna. Värdet av xy mod n visas i fältet Resultat.
- Välj Rensa för att börja en ny beräkning.
Vad är modulär exponentiering?
Modulär exponentiering beräknar resten när xy divideras med n:
xy mod n = r
där r är resten när xy divideras med n, och 0 ≤ r < n.
Operationen är grundläggande inom talteori och kryptografi med öppen nyckel (bland annat RSA), där mycket stora potenser måste beräknas effektivt.
Snabb modulär exponentiering
Att beräkna xy direkt blir opraktiskt när exponenten är stor. Algoritmen för binär exponentiering löser problemet med O(log y) operationer genom att kvadrera basen upprepade gånger:
- Om y är jämnt: xy = (xy/2)2
- Om y är udda: xy = x × xy−1
Modulen används i varje steg, vilket håller mellanresultaten små.
Exempel på modulär exponentiering
| x (bas) | y (exponent) | n (modul) | xy mod n |
|---|---|---|---|
| 2 | 10 | 7 | 2 |
| 3 | 4 | 5 | 1 |
| 5 | 3 | 13 | 8 |
| 7 | 0 | 10 | 1 |
| 2 | 100 | 1000000007 | 976371285 |
Vanliga frågor
Vad är modulär exponentiering?
Modulär exponentiering beräknar xy mod n: resten när xy divideras med n. Metoden är central inom kryptografi och talteori.
Hur beräknar jag xy mod n?
Ange basen x, exponenten y och modulen n och välj Beräkna. Resultatet är resten när xy divideras med n, beräknad med snabb modulär exponentiering.
Varför används modulär exponentiering inom kryptografi?
Modulär exponentiering ligger till grund för RSA och Diffie–Hellman-protokollet. Beräkningen framåt är effektiv, men det är ytterst svårt att vända den genom det diskreta logaritmproblemet – en värdefull asymmetri för digital säkerhet.
Vad är 2¹⁰ mod 7?
2¹⁰ = 1024 och 1024 = 146 × 7 + 2. Alltså är 2¹⁰ mod 7 = 2.
Vad är algoritmen för binär exponentiering?
Det är en effektiv metod för att beräkna xy mod n genom att halvera exponenten upprepade gånger. Antalet operationer minskar från O(y) till O(log y), så även mycket stora potenser kan hanteras på bråkdelen av en sekund.
Relaterade kalkylatorer och guider
