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
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 fk > 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: , valamint k minimális
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
ahol 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:
Például
Mennyi a 32 szám 1296. hatványának maradéka 53-mal osztva?
Az 53 prímszám, így . Mivel és , ezért
Ennek eredményeképpen kapjuk a sokkal könnyebben kiszámolható
kongruenciát. A továbbiakban a számolás három lehetséges folytatását mutatjuk be.
1. módszer: és miatt
ami már kézzel könnyen kiszámolható. A keresett maradék lesz.
2. módszer: Vegyük észre, hogy , emiatt
A kapott kettőhatvány maradéka öt darab négyzetre emeléssel kiszámítható:
Tehát a keresett maradék.
3. módszer: Szorozzuk be az kongruenciát -nel. Innen , azonban az Euler–Fermat-tétel szerint , továbbá , tehát a lineáris kongruenciához jutunk. A bővített euklideszi algoritmus segítségével kapjuk, hogy , vagyis , ezért ha a kongruenciát (−11)-gyel beszorozzuk, akkor megkapjuk a megoldást: , vagyis 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 ); g = atoi( argv ); e = atoi( argv ); 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 ), atoi( argv ), atoi( argv ) ); return 0; }
Megjegyzések
Jegyzetek
Források
Kategória:Számelmélet