New discrete logarithm computation for the medium prime case using the function field sieve (Q2158232): Difference between revisions

This manuscript presents a discrete logarithm computation in the field \(\mathrm{GF}(p^n)\) with prime \(p = 2111023\) and extension degree \(n = 50\), hence a \(1051\)-bit finite field. The algorithm used is the function field sieve with some improvements, including the pinpointing method to speed up relation generation, and a sieving technique using partial smoothness-divisibility during both relation generation and individual logarithm descent. Different from several previous record computations, the finite field is not defined by a Kummer extension, which would make the computation considerably easier. The paper first describes all steps of the function field sieve in the medium prime case and then explains the sieving technique in more detail. Thereafter, the concrete discrete logarithm computation in the above mentioned field is presented. It is argued by experiments that more advanced filtering techniques seem to have no big favourable effect on the linear algebra problem. Moreover, a preliminary cost analysis for computing discrete logarithms in \(\mathrm{GF}(p^n)\) with~\(p\) a \(32\)-bit prime and \(n = 17\) using the function field sieve is given, which suggests the linear algebra step to be the most challenging and barely feasible. One should note however that an adaption of the number field sieve to medium primes is likely to perform better on such problem instances. The paper is well readable and explains the ideas and computational details very clearly.