4.3. Index calculus metoda

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 = {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 = pi c,   ci 0. Ukoliko smo u tome uspjeli, logaritmiramo dobivenu relaciju, te tako prikažemo k mod n kao linearnu kombinaciju logaritama: k 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 = pi d,   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 = ( di logg pi - 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( (ln p ln ln p) ).

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 log₆ 13 u grupi ₂₂₉^*.