Special prime numbers and discrete logs in finite prime fields
Igor Semaev · Mathematics of Computation · 2000
A set $A$ of primes $p$ involving numbers such as $ab^t+c$, where $|a|,|b|,|c|=O(1)$ and $t\to \infty$, is defined. An algorithm for computing discrete logs in the finite field of order $p$ with $p\in A$ is suggested. Its heuristic expected running time is $L_p[\frac 13;(\frac {32}{9})^{1/3}]$ for $(\frac {32}{9})^{1/3}=1.526\dotsb$, where $L_p[\alpha ;\beta ]=\exp ((\beta +o(1))\ln ^\alpha p(\ln \ln p)^{1-\alpha })$ as $p\to \infty$, $0<\alpha <1$, and $0<\beta$. At present, the most efficient algorithm for computing discrete logs in the finite field of order $p$ for general $p$ is Schirokauer’s adaptation of the Number Field Sieve. Its heuristic expected running time is $L_p[\frac 13;(\frac {64}{9})^{1/3}]$ for $(\frac {64}{9})^{1/3}=1.9229\dotsb$. Using $p\in A$ rather than general $p$ does not enhance the performance of Schirokauer’s algorithm. The definition of the set $A$ and the algorithm suggested in this paper are based on a more general congruence than that of the Number Field Sieve. The congruence is related to the resultant of integer polynomials. We also give a number of useful identities for resultants that allow us to specify this congruence for some $p$.