[Prethodna tema]   [Sljedeća tema]

4.3. Index calculus metoda

Najefikasniji poznati algoritmi za problem diskretnog algoritma u grupi Zp* zasnovani su na tzv. index calculus metodi. Sama metoda se može definirati za proizvoljnu grupu G, no njezina efikasnost bitno ovisi o svojstvima te grupe. Ponajprije, moramo biti u stanju izabrati relativno mali podskup F grupe G (tzv. faktorsku bazu) koji ima svojstvo za se velik broj elemenata iz G može efikasno prikazati kao produkt elemenata iz S.

Za efikasnost ove metode u grupi Zp* presudna su svojstva distribucije prostih brojeva, ponajprije činjenica da ih ima beskonačno mnogo. Preciznije, broj prostih brojeva koji su manji od realnog broja x asimptotski je jednak x / ln x. Činjenica da je vrlo teško naći eliptičku krivulju velikog ranga, najvažniji je ograničavajući faktor za primjenu ove metode na grupe eliptičkih krivulja nad konačnim poljem. Ovo je upravo i predstavljalo motivaciju za uvođenje eliptičkih krivulja u kriptografiju.

Opisat ćemo sada algoritam koji za cikličku grupu G reda n s generatorom g, računa diskretni logaritam logg h proizvoljnog elementa h grupe G.

Algoritam index calculus:

1. Izbor faktorske baze
Izaberemo podskup F = {p1, p2, ... , pm} od G sa svojstvom da se relativno velik broj elemenata iz G može prikazati kao produkt elemenata iz F.

2. Linearne relacije u logaritmima
Za slučajan broj k, 0 <= k <= n - 1, izračunamo gk, te ga pokušamo prikazati kao produkt elemenata iz F:

gk = prod pi ci,   ci >= 0.

Ukoliko smo u tome uspjeli, logaritmiramo dobivenu relaciju, te tako prikažemo k mod n kao linearnu kombinaciju logaritama:

k = suma ci logg pi (mod n).
Ponavljamo ovaj postupak sve dok ne dobijemo barem m takvih relacija. Obično se zadovoljavamo s m + 10 relacija, jer tada s velikom vjerojatnošću pripadni sustav od m + 10 jednadžbi s m nepoznanica ima jednstveno rješenje.

3. Rješavanje sustava:
Rješimo linearni sustav od, recimo, m + 10 jednadžbi s m nepoznanica, te tako dobijemo vrijednosti logg pi.

4. Računanje x = logg h:
Za slučajan broj k, 0 <= k <= n - 1, izračunamo h * gk, te ga pokušamo prikazati kao produkt elemenata iz F:

h * gk = prod pi di,   di >= 0.

Ukoliko nismo u tome uspjeli, onda izaberemo novi k, a ukoliko smo uspjeli, onda logaritmiramo dobivenu relaciju, te tako dobijemo da je

x = logg h = ( suma di logg pi - k ) (mod n).


U primjeni index calculus metode na grupu Zp*, koja je ciklička grupa reda n = p - 1, za faktorsku bazu F uzimamo prvih m prostih brojeva. Potom pokušavamo brojeve oblika r = gk prikazati kao produkt prvih m prostih brojeva. Jasno je da što veći m izaberemo, to su veća vjerojatnost da će se r moći rastaviti kao produkt prvih m prostih brojeva. S druge strane, veći m znači će rješavanje sustava u 3. koraku algoritma biti teže. Pokazuje se da je optimalan izbor ako odaberemo da je najveći element faktorske baze pm približno jednak

L(p) = exp( korijen(ln p ln ln p) ).

Na taj način, algoritam index calculus postaje subeksponencijalni algoritam za računanje diskretnog logaritma u grupi Zp*.


Zadatci:

  1. Koliko ima prirodnih brojeva manjih od 1000000 koji se mogu prikazati kao produkt prostih brojeva manjih od 100?

  2. Primjenom index calculus metode s faktorskom bazom {2, 3, 5, 7, 11}, izračunajte log6 13 u grupi Z229*.


[Prethodna tema]   [Sljedeća tema]
Web stranica seminara Andrej Dujella - osobna stranica