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 = aⁿ mod m. Zatiketaren definizioaz, 0 ≤ c < m.

Adibidez, a = 4, n = 3 eta m = 11 emanda, 4³ = 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 = aⁿ 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 aⁿ zuzenki kalkulatzea da, eta ondoren m modulua aplikatzea. Adibidez, a=4, n=13 eta m=497 emanda:

c ≡ 4¹³ (mod 497)

Kalkulagailu bat erabili daiteke 4¹³ 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 aⁿ balioa zortzi zifrakoa dela.

Kriptografia sendoan, askotan a gutxienez 1024 bitekoa da. Hartu a = 5 × 10⁷⁶ eta n = 17, guztiz arrazoizko balioak. Adibide honetan a-k 77 zifra ditu eta n-k bi, baina aⁿ 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, aⁿ-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:

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

3. urratsa egiten den bakoitzean, c ≡ a^n′ (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:

$n=\sum _{i=0}^{k-1}s_{i}2^{i}$

Notazio honetan, n-ren luzera k bitekoa da. s_i 0 edo 1 izan daiteke edozein i-rentzat non 0 ≤ i < n. Definizioz, s_n-1 = 1.

aⁿ-ren balioa honela idatzi daiteke:

$a^{n}=a^{(\sum _{i=0}^{k-1}s_{i}2^{i})}=\prod _{i=0}^{k-1}a^{s_{i}2^{i}}$

Ondorioz, c emaitza hurrengoa da:

$c\equiv \prod _{i=0}^{k-1}a^{s_{i}2^{i}}{\pmod {m}}$

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

• Datuak: Q1228841