O'Reilly logo

Computer Security and Cryptography by Alan G. Konheim

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required