Moduláris hatványozás

Moduláris hatványozásnak nevezzük a hatványozásnak a számelméleti alkalmazását. Konkrétan a hatványozás eredménye a hatvány osztási maradéka adott modulusra nézve. Leginkább a számítógépes titkosítási rendszerekben találkozhatunk vele, mivel ott gyakran kell nagy számok nagy kitevőjű hatványainak maradékait kiszámolni. Ilyen például a Diffie–Hellman-kulcscsere vagy az RSA-algoritmus.

Definíció

Egy f szám g alapú moduláris e-edik hatványának nevezzük azt az x számot, amire teljesül, hogy

$x\equiv f^{e}{\pmod {g}}.$

A definíció alapján ez egyszerűen egy gyűrűművelet, a hasznossága főleg az alkalmazásokban derül ki. A kiszámítás során ugyanis felhasználhatjuk, hogy egy szám hatványának maradéka a szám maradékának hatványa.

Kiszámítás

Definíció szerint

Hagyományosan kiszámítjuk a hatványt, majd maradékot képzünk. Ez azonban a gyakorlatban a nagy modulusok miatt kivitelezhetetlen.

Némileg felgyorsíthatja a számolást, ha van olyan k < e kitevő, hogy f^k > g, mert akkor ezt lehet a maradékával helyettesíteni, így csak az e - k kitevőre kell kiszámítani.

Ezt továbbgondolva a következőre jutunk:

• $f^{k}>g$, valamint k minimális
• $e=k\cdot q+r$
• $m\equiv f^{k}{\pmod {g}}$
• $f^{e}\equiv m^{q}\cdot f^{r}{\pmod {g}}$

Itt q és m biztosan kisebb, mint k illetve f, ezáltal a számítás némileg könnyebbé válik.

További segítséget jelenthet az Euler–Fermat-tétel, ami szerint ha a és m relatív prímek, akkor

$a^{\varphi (m)}\equiv 1{\pmod {m}},$

ahol $\varphi (m)$ az Euler-függvény. Ezt használva relatív prím f és g esetén az e kitevőt tovább lehet redukálni:

${\begin{aligned}r&=e{\bmod {\varphi (g)}},\\f^{e}&\equiv f^{r}{\pmod {g}}.\end{aligned}}$

Például

Mennyi a 32 szám 1296. hatványának maradéka 53-mal osztva?

Az 53 prímszám, így $\varphi (53)=52$. Mivel $1296\equiv 48{\pmod {52}}$ és $53\nmid 32$, ezért

$32^{1296}\equiv 32^{48}{\pmod {53}}.$

Ennek eredményeképpen kapjuk a sokkal könnyebben kiszámolható

$x\equiv 32^{48}{\pmod {53}}$

kongruenciát. A továbbiakban a számolás három lehetséges folytatását mutatjuk be.

1. módszer: $32^{11}\equiv 8{\pmod {53}}$ és $48=4\cdot 11+4$ miatt

$x\equiv 8^{4}\cdot 32^{4}{\pmod {53}},$

ami már kézzel könnyen kiszámolható. A keresett maradék $x=42$ lesz.

2. módszer: Vegyük észre, hogy $32=2^{5}$, emiatt

$32^{48}=2^{5\cdot 48}=2^{240}\equiv 2^{240{\bmod {5}}2}\equiv 2^{32}{\pmod {53}}.$

A kapott kettőhatvány maradéka öt darab négyzetre emeléssel kiszámítható:

${\begin{aligned}x&\equiv 2^{32}=((((2^{2})^{2})^{2})^{2})^{2}=(((4^{2})^{2})^{2})^{2}=(((16^{2})^{2})^{2}=\\&=(256^{2})^{2}\equiv (44^{2})^{2}=1936^{2}\equiv 28^{2}=784\equiv 42{\pmod {53}}.\end{aligned}}$

Tehát $x=42$ a keresett maradék.

3. módszer: Szorozzuk be az $x\equiv 32^{48}{\pmod {53}}$ kongruenciát $32^{4}$-nel. Innen $32^{4}x\equiv 32^{52}{\pmod {53}}$, azonban az Euler–Fermat-tétel szerint $32^{52}\equiv 1{\pmod {53}}$, továbbá $32^{4}\equiv 24{\pmod {53}}$, tehát a$24x\equiv 1{\pmod {53}}$ lineáris kongruenciához jutunk. A bővített euklideszi algoritmus segítségével kapjuk, hogy $5\cdot 53-11\cdot 24=1$, vagyis $-11\cdot 24\equiv 1{\pmod {53}}$, ezért ha a $24x\equiv 1{\pmod {53}}$ kongruenciát (−11)-gyel beszorozzuk, akkor megkapjuk a megoldást: $x\equiv -11\equiv 42{\pmod {53}}$, vagyis $x=42$ a keresett maradék.

Ha figyelembe vesszük, hogy a hatvány kiszámításának műveletigénye a naiv szorzási algoritmussal megközelítőleg másfélmillió lépés, eredményül pedig egy majdnem kétezer jegyű számot kapunk, amit maradékosan még el kell osztani 53-mal, belátható, hogy a fentebb vázolt gondolatmenetek bármelyike lényegesen javít a számítási időn.

Számítógépes módszerek

Mivel a számítások során sokjegyű számokat kell összeszoroznunk, a műveletigény közelítőleg a jegyek számának hatványának nagyságrendjébe esik. Ez ugyan mérsékelhető a fenti eljárások segítségével, de még mindig akkora a műveleti ideje, hogy a kézzel való számolás lehetetlenül hosszadalmas.

Számítógépek használatával azonban a hibalehetőségek csökkenése mellett a műveleti sebesség is hihetetlen mértékben megnő, így a számítás általában másodpercekig tart mindössze.

Pszeudokód

A számítógépes megoldás lehetséges egyszerűen ciklussal:

Be: f, g, e egészek
Legyen c = 1
Ciklus amíg e >= 1:
 Legyen c = c * f
 Legyen c = c mod g
Ciklus vége
Ki: c

Mivel minden ciklus helyettesíthető rekurzióval, a megvalósítás másik formája:

Be: f, g, e egészek
Eljárás SZÁMÍTÁS(a, b, c)
 Ha c == 0 akkor vissza 1
 egyébként vissza ( SZÁMÍTÁS(a, b, c-1) mod b )
Eljárás vége

Ez a természetes gondolkodáshoz is közelebb áll.

A kódokban a fentebb vázolt redukciós eljárásokat nem vettük figyelembe.

Megvalósítás C nyelven

Ciklussal

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
    int f, g, e, c;
 
    if( argc < 4 ) return 1; //Kevés az argumentum
    if( argc > 4 ) return 2; //Sok az argumentum
 
 
    f = atoi( argv[1] );
    g = atoi( argv[2] );
    e = atoi( argv[3] );
    c = 1;

    while ( e >= 1 )
    {
        c = ( c * f ) % g;
        e--;
    }
 
    printf c;

    return 0;
}

Rekurzióval

#include <stdio.h>
#include <stdlib.h>

int powmod( int f, int g, int e )
{
    if( e <1 ) return 1;
    
    return ( ( powmod( f, g, e-1 ) * f ) % g );
}

int main( int argc, char *argv[] )
{
    if( argc != 4 ) return 1; //Az argumentumszám nem megfelelő
    
    printf powmod( atoi( argv[1] ), atoi( argv[2] ), atoi( argv[3] ) );
    return 0;
}

Források

• I. N. Bronstejn (2009). Matematikai kézikönyv. TypoTex. ISBN 978-963-2790-79-4. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (súgó)
• Mátyás Ferenc (1997). A számelmélet elemei. Eger: Líceum kiadó. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (súgó)