Index Calculus Algorithm - The Algorithm

The Algorithm

Input: Discrete logarithm generator g, modulus q and argument h. Factor base {−1,2,3,5,7,11,...,p_r}, of length r+1.
Output: x such that gx ≡ h (mod q).

• relations ← empty_list
• for k = 1, 2, ...
  • Using an integer factorization algorithm optimized for smooth numbers, try to factor modulo q using the factor base, i.e. find 's such that
  • Each time a factorization is found:
    • Store k and the computed 's as a vector (this is a called a relation)
    • If this relation is linearly independent to the other relations:
      • Add it to the list of relations
      • If there are at least r+1 relations, exit loop
• Form a matrix whose rows are the relations
• Obtain the reduced echelon form of the matrix
  • 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
• for s = 0, 1, 2, ...
  • Try to factor over the factor base
  • When a factorization is found:
    • Output