14.5 THE INDEX-CALCULUS METHOD

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

Proposition 14.5 (The Index-Calculus Algorithm): Initialization: Select a factor base image = {p1, p2, …, ps} consisting of elements of image. image is chosen so that a significant proportion of the elements of image can be expressed in the form image with ni ≥ 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 image 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 ...

Get Computer Security and Cryptography now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.