Editing Index calculus algorithm (section)

== The algorithm ==
'''Input:''' Discrete logarithm generator <math>g</math>, modulus <math>q</math> and argument <math>h</math>.  Factor base <math>\{-1, 2, 3, 5, 7, 11, \ldots, p_r\}</math>, of length <math>r+1</math>.<br/>
'''Output:''' <math>x</math> such that <math>g^x=h \mod q</math>.

* relations ← empty_list
* for <math>k = 1, 2, \ldots</math>
** Using an [[integer factorization]] algorithm optimized for [[smooth numbers]], try to factor <math>g^k \bmod  q</math> (Euclidean residue) using the factor base, i.e. find <math>e_i</math>'s such that <math>g^k \bmod q= (-1)^{e_0}2^{e_1}3^{e_2}\cdots p_r^{e_r}</math>
** Each time a factorization is found:
*** Store <math>k</math> and the computed <math>e_i</math>'s as a vector <math>(e_0,e_1,e_2,\ldots,e_r,k)</math> (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 <math>r+1</math> 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 <math>-1</math> and the second element is the discrete log of <math>2</math> and so on
* for <math>s = 1, 2, \ldots</math>
** Try to factor <math>g^s h \bmod q= (-1)^{f_0}2^{f_1}3^{f_2}\cdots p_r^{f_r}</math> over the factor base
** When a factorization is found:
*** Output <math>x = f_0 \log_g(-1) + f_1 \log_g2 + \cdots + f_r \log_g p_r - s.</math>