Index calculus metoda

[Prethodna tema] [Sljedeća tema]

4.3. Index calculus metoda

Najefikasniji poznati algoritmi za problem diskretnog algoritma u grupi

^* 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 ^* 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 log_g h proizvoljnog elementa h grupe G.

Algoritam index calculus:
1. Izbor faktorske baze
Izaberemo podskup F = {p₁, p₂, ... , p_m} 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 g^k, te ga pokušamo prikazati kao produkt elemenata iz F:
g^k = prod p_i ^c, c_i 0.
Ukoliko smo u tome uspjeli, logaritmiramo dobivenu relaciju, te tako prikažemo k mod n kao linearnu kombinaciju logaritama:
k suma c_i log_g p_i (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 log_g p_i.
4. Računanje x = log_g h:
Za slučajan broj k, 0 k n - 1, izračunamo h g^k, te ga pokušamo prikazati kao produkt elemenata iz F:
h g^k = prod p_i ^d, d_i 0.
Ukoliko nismo u tome uspjeli, onda izaberemo novi k, a ukoliko smo uspjeli, onda logaritmiramo dobivenu relaciju, te tako dobijemo da je
x = log_g h = ( suma d_i log_g p_i - k ) (mod n).

U primjeni index calculus metode na grupu ^*, koja je ciklička grupa reda n = p - 1, za faktorsku bazu F uzimamo prvih m prostih brojeva. Potom pokušavamo brojeve oblika r = g^k 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 p_m 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

^*.

Zadatci:

Koliko ima prirodnih brojeva manjih od 1000000 koji se mogu prikazati kao produkt prostih brojeva manjih od 100?
Primjenom index calculus metode s faktorskom bazom {2, 3, 5, 7, 11}, izračunajte log₆ 13 u grupi ₂₂₉^*.

[Prethodna tema] [Sljedeća tema]

Web stranica seminara

Andrej Dujella - osobna stranica