New discrete logarithm computation for the medium prime case using the function field sieve (Q2158232)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New discrete logarithm computation for the medium prime case using the function field sieve |
scientific article |
Statements
New discrete logarithm computation for the medium prime case using the function field sieve (English)
0 references
26 July 2022
0 references
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.
0 references
finite field
0 references
discrete logarithm
0 references
function field sieve
0 references