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)

 

Computing special powers in finite fields


Authors: Joachim von zur Gathen and Michael Nöcker
Journal: Math. Comp. 73 (2004), 1499-1523
MSC (2000): Primary 68Q40; Secondary 11Y16
Published electronically: September 26, 2003
MathSciNet review: 2047098
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study exponentiation in nonprime finite fields with very special exponents such as they occur, for example, in inversion, primitivity tests, and polynomial factorization. Our algorithmic approach improves the corresponding exponentiation problem from about quadratic to about linear time.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 68Q40, 11Y16

Retrieve articles in all journals with MSC (2000): 68Q40, 11Y16


Additional Information

Joachim von zur Gathen
Affiliation: Fakultät für Elektrotechnik, Informatik, Mathematik, Universität Paderborn, D-33095 Paderborn, Germany
Email: gathen@upb.de

Michael Nöcker
Affiliation: Bückeburger Str. 12, D-59174 Kamen, Germany
Email: noecker@upb.de

DOI: http://dx.doi.org/10.1090/S0025-5718-03-01599-0
PII: S 0025-5718(03)01599-0
Received by editor(s): July 28, 2002
Received by editor(s) in revised form: December 9, 2002
Published electronically: September 26, 2003
Article copyright: © Copyright 2003 American Mathematical Society