Squaring in cyclotomic subgroups
Koray Karabina · Mathematics of Computation · 2012
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.