Remote Access Mathematics of Computation
Green Open Access

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
MathSciNet review: 2983036
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

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.

American Mathematical Society