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

No credit card required

## 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 = qx (modulo p).

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

No credit card required