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)

 

Squaring in cyclotomic subgroups


Author: Koray Karabina
Journal: Math. Comp. 82 (2013), 555-579
MSC (2010): Primary 94A60, 12E20, 14G50
Published electronically: June 27, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We propose new squaring formulae for cyclotomic subgroups of the multiplicative group of certain finite fields. Our formulae use a compressed representation of elements having the property that decompression can be performed at a very low cost. The squaring formulae lead to new exponentiation algorithms in cyclotomic subgroups which outperform the fastest previously-known exponentiation algorithms when the exponent has low Hamming weight. Our algorithms can be adapted to accelerate the final exponentiation step of pairing computations.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 94A60, 12E20, 14G50

Retrieve articles in all journals with MSC (2010): 94A60, 12E20, 14G50


Additional Information

Koray Karabina
Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1
Email: kkarabin@uwaterloo.ca

DOI: http://dx.doi.org/10.1090/S0025-5718-2012-02625-1
PII: S 0025-5718(2012)02625-1
Keywords: Cyclotomic subgroups, squaring, exponentiation, pairing-based cryptography
Received by editor(s): October 22, 2010
Received by editor(s) in revised form: August 22, 2011
Published electronically: June 27, 2012
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.