Computer Security and Cryptography

14.5 THE INDEX-CALCULUS METHOD

Let q be a generator of a cyclic group = {1, 2, …, p − 1} of order p − 1 and y = q^x (modulo p).

Proposition 14.5 (The Index-Calculus Algorithm): Initialization: Select a factor base = {p₁, p₂, …, p_s} consisting of elements of . is chosen so that a significant proportion of the elements of can be expressed in the form with n_i ≥ 0.

14.5a	Select a random k with 0 ≤ k < n and compute qk (modulo p).
14.5b	Try to write qk (modulo p) as a product with ci, ≥ 0: if unsuccessful, return to Step 14.5a and choose another value for k; if successful, write k = [c1 logq p1 + [c2 logq p2 + … + [cs logq ps](modulo p − 1).
14.5c	Repeat Steps 14.5a–b until a sufficient number of linear relations as above are found in order to solve the system of equations to determine ...