Dat un prim sigur $P$ si un generator $g$ care generează toate valorile din $1$ la $P-1$ cu
$$g^n \mod P$$
1.) Există acum o funcție $f$ care atribuie o valoare unică unui interval de membri
$$f(g^{i-a_i},...,g^{i+b_i}) = f(g^i) = v_{ia_ib_i}$$
2.) Având în vedere o astfel de valoare unică $v_{ia_ib_i}$ decalajul la următorul $g^{q_i}$ si anterior $g^{-q'_i}$ poate fi calculat/aproximat într-un timp destul de rapid (ore)
Exemplu:
Lăsați acele valori unice să fie membri ai grupului $g^k \equiv 0 \mod 10000$.
Atribuirea (1.) ar fi doar cea mai apropiată astfel de valoare.
Există acum o modalitate de a calcula cel mai mic offset $t$ pentru a găsi următoarea valoare unică $g^r \equiv 0 \mod 1000 $ cu
$$g^k\cdot g^t = g^r$$
Același lucru pentru valoarea unică anterioară (ambele cu $|t| \min$)
Mai multe detalii:
- numărul de valori unice va fi mult mai mic decât $P$
- va fi dat întotdeauna un număr unic aleatoriu. Calcularea sarcinii 1.) nu trebuie să fie rapid. (Bănuiesc că dacă există o soluție, nu poate fi rapidă, altfel rezolvarea dlog-ului ar fi ușoară)
- 2.) nu trebuie să fie un calcul exact.Un fel de căutare între un set mic de valori posibile este bine. Dar întotdeauna trebuie să conducă la valoarea unică foarte următoare/anterioră
- nu toți membrii grupului trebuie să fie atribuiți unei astfel de valori unice
-lungimea intervalului ($a+b+1$) ar trebui să fie diferit (în majoritatea cazurilor) pentru o valoare unică
Deci fiecare valoare cu care poate fi generată $g^{i-a_i}$ la $g^{i+b_i}$
este atribuit $f(g^i)$.
Cu excepția cazului în care atribuirea modifică intervalul ($a,b$) se modifică, de asemenea, doar cu unul. Prin urmare $g^{i+1}$:
$$a_{i+1} = a_i +1$$
$$b_{i+1} = b_i -1$$
($b = 0$ ar fi granița misiunii)
