Index calculus algorithm

From Wikipedia, the free encyclopedia

In group theory, the index calculus algorithm is an algorithm for computing discrete logarithms. This is the best known algorithm for certain groups, such as \mathbb{Z}_m^* (the multiplicative group modulo m).

[edit] Description

Roughly speaking, the discrete log problem asks us to find an x such that g^x \equiv h \pmod{n}, where g, h, and the modulus n are given.

The algorithm (described in detail below) applies to the group \mathbb{Z}_q^* where q is prime. It requires a factor base as input. This factor base is usually chosen to be the number -1 and a number of consecutive primes starting from 2. From the point of view of efficiency, we want this factor base to be small, but in order to solve the discrete log for a large group we require the factor base to be (relatively) large. In practical implementations of the algorithm, those conflicting objectives are compromised one way or another.

The algorithm is performed in two stages. The first stage involves gathering a number of relations between the factor base and powers of the generator g. Once enough relations are gathered, we can compute the discrete log of each of the elements in the factor base. The second stage begins by multiplying h by consecutive powers of g until it can be factorised over the factor base. Once that can be done, we can work out x via a simple algebraic manipulation.

[edit] The algorithm

Input: Factor base {-1,2,3,...,p}, g, h, q
Output: x such that g^x \equiv h \pmod{q}

  1. k = 0
  2. l = 0
  3. Increment k by 1 (i.e. if k was n, now k = n + 1)
  4. Compute gk
  5. Factorise gk using the factor base, i.e. find ki's such that g^k = (-1)^{k_0}2^{k_1}3^{k_2}...p^{k_r} if the factor base has r + 1 elements
    • If gk can not be factorised using the factor base, return to step 3
  6. Store k and the computed ki's as a vector vl = (k0,k1,k2,...,kr,k) (this is a called a relation)
  7. Check to see if this relation is linearly independent of the other relations
    • if not, discard it and go to step 3
    • if yes, keep it. l <- l + 1 (l keeps track of the number of relations we have)
      • if l < r, go to step 3
      • if l ≥ r (r + 1 is the number of elements in the factor base), go to next step
  8. Form a matrix whose rows are the vi's
  9. Obtain the reduced echelon form of the matrix and declare the first element in the last column is the discrete log of -1 and the second element is the discrete log of 2 and so on
    • if this cannot be done go back to step 3
  10. s = 0
  11. s <- s + 1
  12. Compute hgs
  13. Try to factorise hgs over the factor base
    • if this can not be done go back to step 11
    • if this can be done, and hg^s = (-1)^{s_0}2^{s_1}3^{s_1}...p^{s_r}, then declare x = s0logg( − 1) + s1logg2 + ... + srloggp − s

[edit] External links

Retrieved from "http://en.wikipedia.org../../../i/n/d/Index_calculus_algorithm.html"
In other languages