University of Waterloo
In this paper, the authors propose new squaring formulae for cyclotomic subgroups of certain finite fields. Their 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. Their algorithms can be adapted to accelerate the final exponentiation step of pairing computations.