On the Reduction of Composed Relations from the Number Field Sieve

A very important step in the number field sieve for computing dis­crete loga­rithms in finite fields is the combination of so called relations. These combina­tions are used in the final linear algebra step to find the discrete logarithm. From a practical point of view, it is highly desirable to find combinations with as few as possible non zero entries, since this property speeds up the linear alge­bra part. In this paper we present a new algorithm for computing combina­tions which shows significant im­pro­ve­m­ents in practice to existing other algorithms.