Moduláris hatványozás
Matematika |
---|
A matematika alapjai |
|
Algebra |
|
Analízis |
|
Geometria |
|
Számelmélet |
Diszkrét matematika |
Alkalmazott matematika |
Általános |
Sablon:Matematika
|
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 számok miatt kivitelezhetetlen.[* 1]
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[* 2]
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
ahol az Euler-függvény, mivel ekkor a kitevőt tovább lehet redukálni:
- Például
Mennyi a 32 szám 1296. hatványának maradéka 53-mal osztva?
Mivel 53 prímszám, ezért . Mivel , ezért
Ennek eredményeképpen kapjuk a sokkal könnyebben kiszámolható
kongruenciát. Még természetesen ezt is lehet tovább egyszerűsíteni:
esetén miatt
ami már kézzel könnyen kiszámolható. A keresett maradék:
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; }
Megjegyzések
Jegyzetek
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)