Berreketa modular

Berreketa modularra modulu baten gainean egindako berreketa mota bat da. Konputazioaren zientzietan erabilgarria da, bereziki kriptografia asimetrikoaren arloan, non bai Diffie-Hellman gako trukaketan eta bai RSA sisteman erabiltzen den.

Berreketa modularra a zenbaki oso bat (oinarria) n maila batez (berretzaileaz) berretzen denean eta m zenbaki oso positibo batez (moduluaz) zatitzen denean geratzen den hondarra da; hau da, c = an mod m. Zatiketaren definizioaz, 0 ≤ c < m.

Adibidez, a = 4, n = 3 eta m = 11 emanda, 43 = 64 zati 11 egitean c = 9ko hondarra geratzen da.

Berreketa modularra n maila negatibo batekin egin daiteke a-ren d mod m biderketarekiko alderantzizko modularra aurkituz, algoritmo Euklidear luzatua erabiliz:

 c = an mod m = d-n mod m, non e<0 eta a ⋅ d ≡ 1 (mod m).

Berreketa modularra konputatzeaz erraza da, oso zifra handietarako bada ere. Hala eta guztiz ere, logaritmo diskretu modularra konputatzea, hau da, n berretzailea aurkitzea a, c eta m emanda, bzaila dela sinisten da. Zentzu bakarreko funtzio baten portaera honek algoritmo kriptografikoetan erabiltzeko hautagai bilakatzen du berreketa modularra.

Metodo zuzena 
Berretura modular bat kalkulatzeko metodorik zuzenena an zuzenki kalkulatzea da, eta ondoren m modulua aplikatzea. Adibidez, a=4, n=13 eta m=497 emanda:

 c ≡ 413 (mod 497)

Kalkulagailu bat erabili daiteke 413 konputatzeko, emaitza 67.108.864 da. Balio hau modulo 497 hartzean, c emaitza 445 dela determinatzen da.

Kontuan hartu a zifra bakarreko zenbakia dela eta n bikoa, baina an  balioa zortzi zifrakoa dela.

Kriptografia sendoan, askotan a gutxienez 1024 bitekoa da. Hartu a = 5 × 1076 eta n = 17, guztiz arrazoizko balioak. Adibide honetan a-k 77 zifra ditu eta n-k bi, baina an balioak 1.304 ditu. Halako kalkuluak posible dira ordenagailu modernoetan, baina zenbakien magnitudeak kalkuluen abiadura moteltzen du. Segurtasun hobea lortzeko a eta n handitzen diren heinean, an-ren balioa astun bilakatzen da.

Berreketa burutzeko behar den denbora ingurumenaren eta prozesadoreren menpe dago. Hemen deskribatutako metodoarekin O(n) biderketa egin behar dira.

Metodo efizientea memoriarekiko 
Zenbakiak txikiak mantentzeko operazio modular gehiago egin beharko dira, baina tamaina murrizteak operazio bakoitza azkartzen du, oro har denbora (eta memoria) aurreztuz.

Algoritmo honek hurrengo propietatea erabiltzen du:

 (a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m

Modifikatutako algoritmoa honakoa da:

 Ezarri  c = 1, n = 0.
 n'-ri 1 gehitu.
 Ezarri c = (c · a) mod m
 n´ < n bada, 2. urratsera joan, bestela c c ≡ an (mod m)-rako emaitza zuzena da.

3. urratsa egiten den bakoitzean, c ≡ an′ (mod m) egia da. Urrats hau n aldiz errepikatzerakoan, c bilatzen zen emaitza da. Laburbilduz, algoritmo honek n'-k banaka kontatzen ditu n baliora iritsi arte, oinarriarekin biderkatuz eta modulo operazio bat eginez iterazio bakoitzean, emaitza txikiak mantentzeko.

Aurreko adibide bera, a=4, n=13 eta m=497, aurkezten da. Algoritmoak 13 aldiz egiten du bigarren hurratsa:

 n′ = 1. c = (1 ⋅ 4) mod 497 = 4 mod 497 = 4.
 n′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16.
 n′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64.
 n′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256.
 n′ = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30.
 n′ = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120.
 n′ = 7. c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480.
 n′ = 8. c = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429.
 n′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225.
 n′ = 10. c = (225 ⋅ 4) mod 497 = 900 mod 497 = 403.
 n′ = 11. c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121.
 n′ = 12. c = (121 ⋅ 4) mod 497 = 484 mod 497 = 484.
 n′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445'''.

Ondorioz, 445 da emaitza finala, lehen metodoarekin bezala.

Aurreko metodoarekin bezala, honekin O(n) biderketa behar dira berreketa burutzeko. Hala eta guztiz ere, kalkulo hauetan erabilitako zenbakiak askoz txikiagoak direnez, konputazio denbora gutxienez O(n) faktore baten arabera txikitzen da metodo honekin.

Sasikodean, metodo hau honela burutu daiteke:Funtzioa berreketa_mod(oinarri, berretzaile, modulu)
    Baldin eta modulu = 1 Orduan
        Itzuli 0
    c :=1
    n_prima = 0 tik berretzaile-1 ra Egin
        c := (c * oinarri) mod modulu
    Itzuli c
Bukatu Funtzioa

 Eskuinetik ezkerrerako metodo bitarra 
Hirugarren metodo batek drastikoki murrizten du berreketa modularra burutzeko operazio kopurua, aurreko metodoaren memoria-aztarna bera utziz. Aurreko metodoa eta berreketa bitar deitutako printzipio orokorrago bat konbinatzen ditu.

Lehenin, n berretzailea notazio bitarrara konbertitu behar da:

 

Notazio honetan, n-ren luzera k bitekoa da. si 0 edo 1 izan daiteke edozein i-rentzat non 0 ≤ i < n. Definizioz, sn-1 = 1.an-ren balioa honela idatzi daiteke:

 

Ondorioz, c'' emaitza hurrengoa da:

Sasikodea 
Honakoa Bruce Schneierek egindako Kriptografia Aplikatuan oinarritutako sasikode adibide bat da, itzulia.Funtzioa berreketa_mod(oinarri, berretzaile, modulu)
    baldin eta modulu = 1 Orduan
        Itzuli 0
    Baieztatu :: (modulu - 1)*(modulu - 1) ez gainezka egin
    emaitza := 1
    oinari := oinarri mod modulu
    berretzaile > 0 Bitartean egin
        baldin eta (berretzaile mod 2 == 1) Orduan
            emaitza := (emaitza * oinarri) mod modulu
        berretzaile := berretzaile >> 1
        oinarri := (oinarri * oinarri) mod modulu
    Itzuli emaitza
Bukatu Funtzioa

Kanpo estekak 

Aritmetika modularra
Algoritmoak
Kriptografia