Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Special prime numbers and discrete logs in finite prime fields


Author: Igor A. Semaev
Journal: Math. Comp. 71 (2002), 363-377
MSC (2000): Primary 11Y16, 94A60
Published electronically: October 17, 2000
MathSciNet review: 1863007
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract:

A set $A$ of primes $p$ involving numbers such as $ab^t+c$, where $\vert a\vert,\vert b\vert,\vert c\vert=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[\frac13;(\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[\frac13;(\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$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 94A60

Retrieve articles in all journals with MSC (2000): 11Y16, 94A60


Additional Information

Igor A. Semaev
Affiliation: Profsoyuznaya ul. 43, korp. 2, kv. 723, 117420 Moscow, Russia
Email: semaev@box.ru

DOI: http://dx.doi.org/10.1090/S0025-5718-00-01308-9
PII: S 0025-5718(00)01308-9
Keywords: Cryptography, discrete logarithms, Number Field Sieve
Received by editor(s): July 16, 1998
Received by editor(s) in revised form: April 3, 2000
Published electronically: October 17, 2000
Article copyright: © Copyright 2000 American Mathematical Society