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 számok 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, a Euler–Fermat-tétel, ami szerint

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

ahol $\varphi (m)$ az Euler-függvény, mivel ekkor a kitevőt tovább lehet redukálni:

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

Például

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

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

$32^{1296}\equiv 32^{4}8{\pmod {53}}.$

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

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

kongruenciát. Még természetesen ezt is lehet tovább egyszerűsíteni:

$32^{1}1\equiv 8{\pmod {53}}$

esetén $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$

Ha figyelembe vesszük, hogy a hatvány kiszámításának műveletigénye megközelítőleg másfélmillió lépés, eredményül pedig egy majdnem kétezer jegyű számot kapunk, amit el kell osztani 53-mal, belátható, hogy a fentebb vázolt gondolatmenet 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, K. A. Szemengyajev, G. Musiol, H. Mühlig. Matematikai kézikönyv. TypoTex (2009). ISBN 978-963-2790-79-4 
• Mátyás Ferenc, Kiss Péter. A számelmélet elemei. Eger: Líceum kiadó (1997)